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

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

تجسم مرتب‌سازی گورزاد
رده	الگوریتم مرتب‌سازی
ساختمان داده	آرایه
کارایی بدترین حالت	$O(n^{2})$
کارایی بهترین حالت	$O(n)$
کارایی متوسط	$O(n^{2})$
پیچیدگی فضایی	$O(1)$ کمکی

مرتب‌سازی گورزاد (به انگلیسی: Gnome sort) یکی از الگوریتم‌های مرتب‌سازی است که در سال ۲۰۰۰ میلادی توسط دکتر حمید سربازی‌آزاد (استاد مهندسی کامپیوتر در دانشگاه صنعتی شریف) با نام "مرتب سازی کند ذهن" (به انگلیسی: stupid 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