برنامه‌نویسیایستگاه ۵ از ۳۰
مرتب‌سازی دستی و مقایسه · برنامه‌نویسی، ایستگاه ۵
پرسشی که ایستگاه با آن شروع می‌شود
پستچی‌ها هزاران نامه را چطور به‌سرعت مرتب می‌کنند؟
معمولاً پایهٔ چهارمحدود ۵۹ دقیقه در ۴ جلسهٔ کوتاه
سرعت را تسلط تعیین می‌کند، نه سن.
فرزندتان در این ایستگاه چه یاد می‌گیرد
- مقایسه و جابه‌جایی
- مرتب‌سازی حبابی با کارت‌ها
- شبکه‌ی مرتب‌سازی (Unplugged)
- تعداد مقایسه‌ها
درس‌های این ایستگاه
- مقایسه کن، جابه‌جا کن (حدود ۱۴ دقیقه)
- مرتب‌سازی حبابی (حدود ۱۶ دقیقه)
- شبکهٔ مرتب‌سازی (حدود ۱۵ دقیقه)
- جفت‌های نامرتب (حدود ۱۴ دقیقه)
ایده‌های کلیدی
دوتا‌دوتا
کامپیوتر هر بار فقط دو چیز را مقایسه می‌کند و اگر جایشان غلط بود، جابه‌جا می‌کند.حباب
در هر گذرِ حبابی، بزرگ‌ترینِ باقی‌مانده تا تهِ ردیف می‌رود؛ یک گذرِ بی‌جابه‌جایی یعنی تمام.جفتِ نامرتب
هر جابه‌جاییِ کنار هم تعدادِ جفت‌های نامرتب را دقیقاً یکی کم یا زیاد می‌کند؛ پس کمترین جابه‌جایی = تعداد جفت‌های نامرتب.
از درس‌های همین ایستگاه
یک مثال حل‌شده
همان‌طور که در درس دیده می‌شود، این‌جا با همهٔ قدم‌ها.
مسئله
پستچی ۶ نامه دارد با این کدهای دورقمیِ محله، به همین ترتیب: ۳۱، ۱۲، ۳۴، ۲۷، ۱۵، ۲۳. او حبابی مرتب نمی‌کند. اول هر نامه را بر اساسِ رقمِ دهگانش در یکی از سه قفسهٔ «۱»، «۲» و «۳» می‌گذارد. بعد هر قفسه را جدا مرتب می‌کند و قفسه‌ها را به ترتیب پشتِ هم می‌چیند. ترتیبِ آخر چیست و چند مقایسه لازم شد؟راه‌حل، قدم‌به‌قدم
در درس، قدم‌ها یکی‌یکی باز می‌شوند و فرزندتان پیش از هر قدم خودش حدس می‌زند.
- قدم ۱: پخش کردن مقایسه نمی‌خواهد؛ پستچی فقط رقمِ اولِ هر کد را می‌خواند. قفسهٔ ۱: ۱۲ و ۱۵. قفسهٔ ۲: ۲۷ و ۲۳. قفسهٔ ۳: ۳۱ و ۳۴.
- قدم ۲: هر قفسه دو نامه دارد و با یک مقایسه مرتب می‌شود. قفسه‌های ۱ و ۳ مرتب‌اند. در قفسهٔ ۲، ۲۷ و ۲۳ جابه‌جا می‌شوند. روی هم ۳ مقایسه و ۱ جابه‌جایی.
- قدم ۳: قفسه‌ها را پشتِ هم می‌چینیم: ۱۲، ۱۵، ۲۳، ۲۷، ۳۱، ۳۴. هر کدِ قفسهٔ ۱ از هر کدِ قفسهٔ ۲ کوچک‌تر است؛ پس لازم نبود آن‌ها را با هم مقایسه کنیم.
- قدم ۴: رباتِ حبابی برای ۶ کارت اگر همهٔ گذرها را برود، ۵ + ۴ + ۳ + ۲ + ۱ = ۱۵ مقایسه می‌کند.
- قدم ۵: راهش این بود: کار را با یک نشانهٔ ساده (رقمِ دهگان) به دسته‌های کوچک بشکن و هر دسته را جدا مرتب کن. هر چه دسته‌ها کوچک‌تر، مقایسه‌ها کمتر.
یک نمونهٔ کوچک
ابزار این ایستگاه را امتحان کنید
از درس «مقایسه کن، جابه‌جا کن»
نمونه در حال آماده شدن است…
پیش و پس از این ایستگاه
پیش‌نیازها
ایستگاه‌هایی که به این تکیه می‌کنند
روش یادگیری فکرستان و همهٔ ایستگاه‌های این مسیر: برنامه‌نویسی برای کودکان
شروع با فکرستان
حساب را پدر یا مادر می‌سازد و رضایتش را همان‌جا ثبت می‌کند. فرزندتان با نام مستعار وارد می‌شود و با چند پرسش کوتاه، نقطهٔ شروعِ هر مسیر پیدا می‌شود.