برنامه‌نویسیایستگاه ۱۸ از ۳۰
مرتب‌سازی و پیچیدگی زمانی · برنامه‌نویسی، ایستگاه ۱۸
پرسشی که ایستگاه با آن شروع می‌شود
یک موتورِ جستجو در کسری از ثانیه میلیاردها صفحه را مرتب می‌کند؛ چطور؟
معمولاً پایهٔ هفتمحدود ۱۰۲ دقیقه در ۴ جلسهٔ کوتاه
سرعت را تسلط تعیین می‌کند، نه سن.
فرزندتان در این ایستگاه چه یاد می‌گیرد
- مرتب‌سازی انتخابی و درجی
- sort آماده و کلید مرتب‌سازی
- مفهوم O(n) و O(n²)
- چرا الگوریتم سریع مهم است
درس‌های این ایستگاه
- مرتب‌سازیِ انتخابی (حدود ۲۴ دقیقه)
- مرتب‌سازیِ درجی (حدود ۲۵ دقیقه)
- مرتب‌سازیِ آماده‌ی پایتون و کلید (حدود ۲۶ دقیقه)
- پیچیدگیِ زمانی: O(n) و O(n²) (حدود ۲۷ دقیقه)
ایده‌های کلیدی
مرتب‌سازیِ درجی
بخشِ چپ همیشه مرتب است؛ عددِ بعدی بزرگ‌ترها را یکی‌یکی هُل می‌دهد تا جایش باز شود. تعدادِ هُل‌ها برابرِ جفت‌های نامرتب است و روی ردیفِ تقریباً مرتب زود تمام می‌شود.مرتب‌سازیِ آماده: sort، sorted و کلید
t.sort()خودِ t را مرتب می‌کند وNoneپس می‌دهد؛sorted(t)لیستِ تازه می‌دهد.key=fبه ترتیبِf(…)می‌چیند و کلیدهای برابر ترتیبِ قبلی را نگه می‌دارند.پیچیدگیِ زمانی
کار چطور با n بزرگ می‌شود؟ n دو برابر: O(n) دو برابر، O(n به توانِ 2) چهار برابر. اول بشمار، بعد بنویس؛ گاهی اول مرتب کن، بعد همسایه‌ها را ببین.
از درس‌های همین ایستگاه
یک مثال حل‌شده
همان‌طور که در درس دیده می‌شود، این‌جا با همهٔ قدم‌ها.
مسئله
دو دسته کارتِ عدد داریم که هر کدام از قبل مرتب است: دستهٔ اول[3, 8, 12] و دستهٔ دوم [5, 6, 15]. می‌خواهیم یک دستهٔ مرتب بسازیم. روشِ «ادغام»: هر بار فقط دو کارتِ رویِ دسته‌ها را مقایسه کن و کوچک‌تر را به دستهٔ تازه بفرست. چند مقایسه لازم است؟راه‌حل، قدم‌به‌قدم
در درس، قدم‌ها یکی‌یکی باز می‌شوند و فرزندتان پیش از هر قدم خودش حدس می‌زند.
- قدم ۱: کارت‌های رو ۳ و ۵اند. ۳ کوچک‌تر است و می‌رود. مقایسهٔ ۱.
- قدم ۲: ۸ و ۵: ۵ می‌رود (مقایسهٔ ۲). ۸ و ۶: ۶ می‌رود (مقایسهٔ ۳). ۸ و ۱۵: ۸ می‌رود (مقایسهٔ ۴). ۱۲ و ۱۵: ۱۲ می‌رود (مقایسهٔ ۵).
- قدم ۳: دستهٔ اول تمام شد، پس ۱۵ بی‌مقایسه می‌رود. دستهٔ تازه: ۳، ۵، ۶، ۸، ۱۲، ۱۵؛ با ۵ مقایسه.
- قدم ۴: چرا درست است؟ چون هر دسته مرتب است، کوچک‌ترینِ کارت‌های مانده همیشه رویِ یکی از دو دسته است. هر مقایسه یک کارت را سرِ جایش می‌فرستد؛ پس برای n کارت حداکثر n − ۱ مقایسه لازم است: O(n).
- قدم ۵: اگر همین ۶ کارت را از اول با مرتب‌سازیِ انتخابی مرتب می‌کردیم، ۵ + ۴ + ۳ + ۲ + ۱ = ۱۵ مقایسه لازم بود. مرتب بودنِ دو تکه کار را خیلی کم می‌کند؛ مرتب‌سازیِ آمادهٔ پایتون هم از همین ادغام کمک می‌گیرد.
یک نمونهٔ کوچک
ابزار این ایستگاه را امتحان کنید
از درس «مرتب‌سازیِ انتخابی»
نمونه در حال آماده شدن است…
پیش و پس از این ایستگاه
پیش‌نیازها
- ایستگاه ۱۵: جستجوی کامل
- ریاضی،ایستگاه ۱۶: جایگشت و ترکیب
- ایستگاه ۱۷: تابع و تجزیه‌ی مسئلهپیشنهادی، نه اجباری
ایستگاه‌هایی که به این تکیه می‌کنند
- ایستگاه ۱۹: الگوریتم حریصانه
- ایستگاه ۲۱: جمع پیشوندی و شبکه‌های دوبعدی
روش یادگیری فکرستان و همهٔ ایستگاه‌های این مسیر: برنامه‌نویسی برای کودکان
شروع با فکرستان
حساب را پدر یا مادر می‌سازد و رضایتش را همان‌جا ثبت می‌کند. فرزندتان با نام مستعار وارد می‌شود و با چند پرسش کوتاه، نقطهٔ شروعِ هر مسیر پیدا می‌شود.