مرتب‌سازی گورزاد

شبه‌کد این الگوریتم را در زیر می‌بینید:

 function gnomeSort(a[0..size-1]) {
  i := 1
  j := 2
  while i < size
    if a[i-1] >= a[i]
        i := j
        j := j + 1 
    else
        swap a[i-1] and a[i]
        i := i - 1
        if i = 0
          i := 1
 }

و همین کد را به زبان پایتون در زیر می‌بینید:

 def gnomeSort(a) :
  i = 1
  j = 2
  while i < len(a) :
     if a[i - 1] >= a[i] :
        i = j
        j += 1
     else :
        a[i], a[i - 1] = a[i - 1], a[i]
        i-=1
        if i == 0 :
           i = 1

مثال: اگر بخواهیم آرایه [4, 2, 7, 3] را مرتب کنیم، در هر اجرای حلقه، مراحل زیر اتفاق می‌افتد: [4, 2, 7, 3] (حالت اولیه. i، یک و j، دو است.)
[4, 2, 7, 3] (تغییر نکرد ولی الان i، دو و j، سه است)
[4, 7, 2, 3] ([a[i-1 و [a[i، جابجا شدند. الان i، دو و j، سه است.)
[7, 4, 2, 3] ([a[i-1 و [a[i، جابجا شدند. هنوز هم i، یک و j، سه است.)
[7, 4, 2, 3] (اتفاقی نیفتاد ولی الان i، سه و j، چهار است.)
[7, 4, 3, 2] ([a[i-1 و [a[i تعویض شدند. الان i، چهار و j، پنج است.)
در اینجا، اجرای حلقه، خاتمه می‌یابد، زیرا i، کمتر از چهار نیست.

این الگوریتم همیشه اولین جایی که دو عنصر مجاور در ترتیب غلط هستند را پیدا می‌کند و جایشان را عوض می‌کند. این الگوریتم از این حقیقت بهره می‌برد که انجام یک جابجایی، فقط می‌تواند یک زوج مجاور جدید با ترتیب معکوس نسبت به قبل از انجام جابجایی، ایجاد می‌کند، و پس از انجام جابجایی، همین موقعیت را دوباره بررسی می‌کند.

• مرتب‌ساز Gnome