Home > Algorithm > Thuật toán sắp xếp Gnome – Gnome Sort

Thuật toán sắp xếp Gnome – Gnome Sort

1. Giới thiệu

Thuật toán sắp xếp Gnome là một trong những thuật toán sắp xếp đơn giản nhất, thuộc nhóm các thuật toán có độ phức tạp thuật toán là O(n^2) như sắp xếp nổi bọt, sắp xếp chèn…. Điểm khác biệt ở chỗ sắp xếp Gnome chỉ sử dụng một vòng lặp thay vì 2 vòng lặp như các thuật toán trên.

2. Cài đặt

2.1 Code C#, Java : 

public int[] GnomeSort(int[] arr)
{
    int pos = 1; /* Vi tri bat dau so sanh, la phan tu thu 2 trong mang*/
    int temp;
    int length = arr.Length;
    while (pos < length)
    {
        /* So sanh voi phan tu phia truoc */
       if (arr[pos] >= arr[pos - 1])
       {
           /* Neu lon hon ( da dung thu tu sap xep ) thi tien len 1 vi tri*/
           pos++;
       }
       else
       {
           /* Nguoc lai thi hoan vi 2 phan tu*/
           temp = arr[pos];
           arr[pos] = arr[pos - 1];
           arr[pos - 1] = temp;
           /* Lui ve 1 vi tri de kiem tra lai, vi sau khi hoan vi, mang van co the chua dung thu tu*/
           pos--;
           if (pos == 0) /* Kiem soat khong cho pos nho hon 1 */
           {
               pos = 1;
           }
        }
    }
    return arr;
 }

2.2 Code C, C++ :

void gnome_sort(int *iArray,int iLength)
{
    int iPos = 1;
    int iTemp=0;
    while(iPos<iLength)
    {
        if(iArray[iPos]>=iArray[iPos-1])
        {
            iPos++;
        }
        else
        {
            iTemp=iArray[iPos];
            iArray[iPos]=iArray[iPos-1];
            iArray[iPos-1]=iTemp;
iPos--; if(iPos==0) { iPos=1; } } } }

Xem thêm cách cài đặt bằng cách ngôn ngữ khác tại http://rosettacode.org/wiki/Sorting_algorithms/Gnome_sort hoặc http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Gnome_sort

Advertisements
Categories: Algorithm
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: