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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
مرتب‌سازی گورزاد
Sorting gnomesort anim.gif
تجسم مرتب‌سازی گورزاد
کلاس الگوریتم مرتب‌سازی
داده ساختار آرایه
بدترین زمان اجرا O(n^2)
بهترین زمان اجرا O(n)
زمان اجرای متوسط O(n^2)
بدترین پیچیدگی حافظه O(1) کمکی
بهینه نه

مرتب‌سازی گورزاد (به انگلیسی: 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، کمتر از چهار نیست.

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

لینک به بیرون[ویرایش]