Gɴᴏᴍᴇ-Sᴏʀᴛ

الان که دارم این پست رو می‌گذارم ساعت نزدیک ۴ بامداد یکشنبه است. باید تکلیف ساختمان داده رو تا شنبه شب آپلود می‌کردم ولی هنوز حتی یه خط هم ننوشتم. خب استادش ناشیه و توی سامانه ددلاینی برای آپلود نذاشته. و من انگار هنوز از ترم پیش درس نگرفتم که تمرین‌ها رو به نزدیک ددلاین و بعد از ددلاین واگذار نکنم.

باید از مطالبی که استاد هفتهٔ قبل درس داده دوتا سوال دلخواه در بیارم و با جواب بفرستم. موضوع درس الگوریتم‌های مرتب‌سازی بود و نمادهای تحلیل زمان الگوریتم. [خب حالا اینا یعنی چی؟ فرض کنید یه دسته مدادرنگی داریم که بعضی‌هاشون کوتاه‌تر و بعضی‌هاشون بلندترن، و با یه ترتیب تصادفی توی جعبه چیده شدند. حالا چطور می‌تونیم با عملیات‌های مقایسه و جابجایی، این مدادها رو بر اساس طول مرتب کنیم؟ یه روش اینه که کوتاه‌ترین مداد رو پیدا کنیم و جاش رو با مداد اول عوض کنیم. بعد توی n-1 مداد باقی‌مونده کوتاه‌ترین رو پیدا کنیم و با مداد دوم جابجا کنیم و الخ... به این روش می‌گیم مرتب‌سازی انتخابی. حالا باید تحلیل کنیم که بر اساس تعداد مدادها و وضعیت اولیه مدادها، حداقل و حداکثر به چندتا عملیات نیاز پیدا می‌کنیم و این یعنی اجرای الگوریتم‌مون چقدر زمان می‌بره... به عنوان تمرین، می‌تونید فکر کنید که چه روش‌های دیگه‌ای برای مرتب‌کردن مدادرنگی‌ها به ذهن‌تون می‌رسه :)] 

توی ویکی‌پدیا دنبال یه الگوریتم می‌گشتم که نه اونقدر تحلیلش پیچیده باشه که توی نصف صفحه جا نشه و نه اونقدر ساده باشه که نمره نگیرم ازش. دنبال موردی بودم با مرتبهٔ زمانی n² و البته با یه ایدهٔ جدید. حبابی، انتخابی، درجی... اینا خیلی بدیهی بودند. شِل‌سورت، تیم‌سورت، کتابخانه‌ای... اینا هم بیش از حد پیچیده بودند. چشمم خورد به مرتب‌سازی گنوم. گفتم شاید ربطی به گنو/لینوکس داشته باشه. هرچند ربطی نداشت. از اونجا که تازه وارد لینوکس شدم، هر کلمه‌ای مرتبط باهاش توجهم رو جلب می‌کنه.

صفحه‌ی گنوم‌سورت رو توی ویکی‌پدیا باز کردم. چشمم خورد به کلمهٔ شریف. بیشترتر توجهم جلب شد. برگشتم بالای صفحه. نوشته بود این الگوریتم برای اولین‌بار توسط دانشمند رایانهٔ ایرانی ح. سین. الف. (استاد مهندسی و علوم کامپیوتر دانشگاه صنعتی شریف) در سال ۲۰۰۰ مطرح شده. no way! همین امروز صبح با دکتر سین. کلاس داشتم. یعنی من یکی از طراحان الگوریتم‌های مرتب‌سازی رو از نزدیک دیدم و باهاش کلاس هم دارم؟ :) خب باید بگم که تا پیش از این دکتر سین. جذاب‌ترین استاد این ترمم محسوب می‌شد و حالا با این کشف جایگاه ویژه‌تری هم پیدا کرده! 

دربارهٔ خود الگوریتم اگه بخوام بگم، مثال بارز اصل KISS هست: keep it simple, stupid! کل الگوریتم شامل یک حقله، یک شرط و یک متغییر برای پیمایشه. از این نظر با الگوریتم‌های معمولی که می‌شناسیم (دو حلقهٔ تودرتو یا اینکه تابع به صورت بازگشتی خودش رو صدا بزنه) ظاهر متفاوتی داره. اینم از شبه‌کدش:

Gnome-Sort(a[]):
    pos := 0
    while pos < length(a):
        if (pos == 0 or a[pos] >= a[pos-1]):
            pos := pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos := pos - 1

اگه از خوندن کد متوجه رفتارش نشدید، می‌تونید اینجا یه مثال تجسمی ازش ببینید: [کلیک]

اطلاعات بیشتر از صفحهٔ شخصی استاد میگه این الگوریتم رو وقتی توی انگلستان دانشجوی دکترا بوده توی خبرنامهٔ دانشکده منتشر کرده. خیلی برام جالبه که بدونم چطور اولین بار ایدهٔ این الگوریتم به ذهنش رسیده. آیا داشته روی الگوریتم‌های مرتب‌سازی فکر می‌کرده و دنبال کم‌کردن تعداد دستورها بوده؟ آیا کد مشابهی توی یه کتاب دیده و پارامترهاشو کم و زیاد کرده تا به این رسیده؟ یا اینکه یه روز صبح یهویی بیدار شده و این الگوریتم به ذهنش الهام شده؟!