آزمایشگاه آزاد؛ بدون نیاز به ورود
مسابقهٔ مرتب‌سازی؛ مقایسه‌ها رو بسنج
سه روش یک فهرست رو مرتب می‌کنن، اما تعداد مقایسه‌هاشون همیشه یکی نیست. اندازه و ترتیب شروع رو عوض کن و نمودار رو ببین.
آزمایش رو شروع کناز فهرست مرتب‌شده با ۸ عنصر شروع کن؛ بعد ترتیب رو به معکوس تغییر بده و تعداد مقایسه‌های سه الگوریتم رو مقایسه کن.
آزمایشگاه در حال آماده شدنه…
حالا خودت امتحان کن
هر بار فقط یک چیز رو تغییر بده تا اثرش رو ببینی. قبل از اجرا، نتیجه رو حدس بزن.
ترتیب شروع رو عوض کن
اندازهٔ فهرست رو روی ۸ بذار؛ یک بار «مرتب‌شده» و بعد «معکوس» رو انتخاب کن. تعداد مقایسه‌ها رو برای هر سه روش بخون.
حدست چیه؟ کدوم روش با فهرست مرتب‌شده مقایسه‌های کمتری انجام می‌ده؟
توضیح نتیجه رو ببین
در این اجرا، مرتب‌سازی درجی برای ترتیب مرتب ۷ مقایسه و برای ترتیب معکوس ۲۸ مقایسه انجام می‌ده. حبابی در هر دو حالت ۲۸ مقایسه داره؛ مرتب‌سازی سریع هم به‌خاطر انتخاب عنصر آخر به‌عنوان محور، در این دو حالت ۲۸ مقایسه می‌شماره.
وقتی فهرست بزرگ‌تر می‌شه
ترتیب رو روی «تصادفی» نگه دار؛ اندازه رو اول ۸ و بعد ۱۲ عنصر کن. عدد مقایسه‌های هر الگوریتم رو یادداشت کن.
حدست چیه؟ با اضافه شدن ۴ عنصر، تعداد مقایسه‌ها برای هر سه روش چه تغییری می‌کنه؟
توضیح نتیجه رو ببین
در نمونهٔ ثابت این شبیه‌ساز، مقایسه‌های حبابی از ۲۸ به ۶۶، درجی از ۲۲ به ۴۱ و سریع از ۱۴ به ۲۸ می‌رسه. این عددها شمارش یک اجرا هستن؛ زمان واقعی اجرا رو اندازه نمی‌گیرن.
اثر عنصر محوری در مرتب‌سازی سریع
اندازه رو روی ۱۰ بذار؛ مرتب‌سازی سریع رو یک بار با ترتیب «مرتب‌شده» و یک بار با «تصادفی» مقایسه کن.
حدست چیه؟ برای روش سریع، کدوم ترتیب مقایسه‌های بیشتری می‌سازه؟
توضیح نتیجه رو ببین
در این مدل، روش سریع با ترتیب مرتب‌شده ۴۵ مقایسه و با نمونهٔ تصادفی ۲۳ مقایسه داره؛ چون هر بار آخرین عضو رو محور می‌گیره. این نتیجه دربارهٔ همین انتخاب محوره، نه همهٔ نسخه‌های مرتب‌سازی سریع.
پشت این حرکت چه خبره؟
مقایسه و جابه‌جایی دو چیزن
مقایسه یعنی بررسی ترتیب دو مقدار؛ جابه‌جایی یعنی تغییر جای عنصرها. یک الگوریتم ممکنه مقایسه‌های زیادی داشته باشه ولی جابه‌جایی کمی انجام بده، یا برعکس.
مرتب‌سازی حبابی
C_bubble = n*(n-1)/2
روش حبابی همسایه‌ها رو مقایسه می‌کنه و اگر ترتیبشون غلط باشه جابه‌جاشون می‌کنه. این پیاده‌سازی در هر فهرست n عضوی، n ضربدر n منهای یک تقسیم بر دو مقایسه انجام می‌ده؛ حتی اگه فهرست از اول مرتب باشه.
مرتب‌سازی درجی
روش درجی هر عضو رو بین بخش مرتب‌شدهٔ قبلی جا می‌ده. فهرست مرتب می‌تونه مقایسه‌های کمی بخواد، ولی در ترتیب معکوس هر عضو باید از تعداد زیادی عضو رد بشه.
محور در مرتب‌سازی سریع
T_quick_average = O(n*log(n)); T_quick_worst = O(n^2)
این پیاده‌سازی آخرین عضو هر بخش رو محور می‌گیره. برای بعضی ورودی‌ها تقسیم خوبی می‌سازه؛ اما ترتیب مرتب می‌تونه بخش‌ها رو نامتوازن کنه و تعداد مقایسه‌ها رو بالا ببره.
سؤالت رو بپرس، جوابش رو هم ببین
وقتی توی چت دربارهٔ یک مفهوم درس می‌خونی، دستیار هوش مصنوعی می‌تونه شبیه‌سازی مرتبط رو کنار توضیحش نشون بده. پارامترها رو تغییر می‌دی و با کمک توضیح بعدی، نتیجه رو بهتر می‌فهمی.
شروع یادگیری با چتبرای ادامه در چت، وارد مسیر شروع و ورود می‌شی. نتیجهٔ این آزمایش به چت منتقل نمی‌شه.
نمونهٔ نمایشی از آموزش در چت
پس مرتب‌سازی سریع همیشه از بقیه سریع‌تره؟
نه. این شبیه‌ساز زمان واقعی رو اندازه نمی‌گیره و نسخهٔ سریعش همیشه آخرین عضو رو محور می‌گیره. با فهرست مرتب، همین انتخاب می‌تونه تعداد مقایسه‌ها رو زیاد کنه؛ روش یا ورودی دیگه نتیجهٔ متفاوتی می‌ده.
سؤال‌های رایج
چرا مرتب‌سازی درجی با فهرست مرتب مقایسهٔ کمی داره؟
چون هر عضو بعدی از قبل جای درستشه؛ در این مدل برای هر عضو فقط یک بررسی لازم می‌شه.
چرا حبابی برای فهرست مرتب هم ۲۸ مقایسه داره؟
در این پیاده‌سازی حلقه‌ها تعداد ثابتی مقایسه انجام می‌دن و اگر ورودی مرتب باشه زود متوقف نمی‌شن.
چرا مرتب‌سازی سریع روی فهرست مرتب مقایسه‌های زیادی داره؟
چون این نسخه همیشه آخرین عضو رو محور می‌گیره؛ روی ورودی مرتب، بخش‌های بعدی نامتوازن می‌شن. نسخه‌های دیگه ممکنه محور متفاوتی بردارن.
عدد جابه‌جایی یعنی چند ثانیه طول کشیده؟
نه؛ فقط شمارندهٔ کارهای الگوریتمه. شبیه‌ساز زمان اجرا یا سرعت دستگاه رو اندازه نمی‌گیره.
چرا ترتیب تصادفی دوباره همون نتیجه رو می‌ده؟
این شبیه‌ساز برای ساخت نمونه از یک ترتیب درهم‌ریختهٔ ثابت استفاده می‌کنه تا نتیجه‌ها قابل تکرار باشن؛ هر بار یک فهرست تازه نمی‌سازه.