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

از ویکی‌پدیا، دانشنامهٔ آزاد.

مرتب‌ساز گورزاد (به انگلیسی: Gnome sort) یکی از الگوریتم‌های مرتب‌سازی است که شبیه مرتب‌ساز درجی است، با این تفاوت که انتقال عنصر به موقعیت مناسبش، توسط تعدادی جابجایی صورت می‌گیرد؛ مثل مرتب‌ساز حبابی. کد این الگوریتم ساده است و نیازی به حلقه‌های تودرتو ندارد. زمان اجرای الگوریتم، (O(n² است، ولی در عمل با سرعت مرتب‌ساز درجی می‌تواند اجرا شود.

نام انگلیسی این مرتب‌ساز یعنی Gnome به معنی گورزاد است. گورزادها موجوداتی تخیلی هستند که آدمک‌های آن‌ها در باغچه‌های هلندیان قرار داده می‌شود و روش مرتب‌سازی گلدان، گِرد آن‌ها مشابهتی با این گونه مرتب‌سازی دارد.

[ویرایش] الگوریتم

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

 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