بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 32: مرتبش کن! Sort It

می‌فهمیم چرا مرتب کردن مهم است و خودمان مثل یک ماشین، با جابه‌جا کردن‌های کوچک، یک لیست را مرتب می‌کنیم.

در این جلسه یاد می‌گیری

درس

چرا مرتب کردن؟ جدول لیگ، رتبه‌بندی بازی، دفتر حضور و غیاب... همه مرتب‌اند تا زود چیزی را پیدا کنیم. پایتون sorted را دارد، ولی امروز یاد می‌گیریم خودش «پشت پرده» چطور کار می‌کند.

scores = [40, 15, 90, 60]
print(sorted(scores))
print(sorted(scores, reverse=True))

پایه‌ی همه‌ی مرتب‌سازی‌ها «جابه‌جا کردن» است. پایتون یک ترفند قشنگ دارد: a, b = b, a دو مقدار را در یک خط عوض می‌کند. با خانه‌های لیست هم کار می‌کند.

a = 3
b = 8
a, b = b, a
print(a, b)
nums = [5, 2]
nums[0], nums[1] = nums[1], nums[0]
print(nums)

مرتب‌سازی حبابی: از اول لیست، هر دو خانه‌ی کنار هم را مقایسه کن؛ اگر ترتیبشان غلط بود جابه‌جایشان کن. بعد از یک دور کامل، بزرگ‌ترین عدد مثل حباب به آخر لیست می‌رسد!

nums = [5, 3, 8, 1]
for i in range(len(nums) - 1):
    if nums[i] > nums[i + 1]:
        nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)

یک دور کافی نیست. اگر همین دور را len - 1 بار تکرار کنیم، کل لیست مرتب می‌شود. این یعنی دو حلقه‌ی تودرتو.

nums = [5, 3, 8, 1]
for p in range(len(nums) - 1):
    for i in range(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
print(nums)

مرتب‌سازی انتخابی ایده‌ی دیگری است: کوچک‌ترین عدد را پیدا کن و بگذارش خانه‌ی اول. بعد از بقیه کوچک‌ترین را پیدا کن و بگذار خانه‌ی دوم، و همین‌طور تا آخر. درست مثل انتخاب بازیکن‌ها برای تیم!

nums = [29, 10, 14, 37]
for i in range(len(nums) - 1):
    small = i
    for j in range(i + 1, len(nums)):
        if nums[j] < nums[small]:
            small = j
    nums[i], nums[small] = nums[small], nums[i]
print(nums)

کلمه‌ها هم مرتب می‌شوند: < برای رشته‌ها یعنی «زودتر در الفبا». فقط حواست باشد که حرف بزرگ از حرف کوچک زودتر حساب می‌شود ("Z" < "a"). برای اینکه خودت بنویسی خوب است، ولی در کار واقعی sorted سریع‌تر و مطمئن‌تر است.

words = ["pear", "apple", "fig"]
print(sorted(words))
print(sorted(words, key=len))

مثال‌های این جلسه

چالش‌ها

  1. Swap Cards (آسان)
  2. Class List (آسان)
  3. High Scores (آسان)
  4. One Bubble Pass (متوسط)
  5. Already Sorted? (متوسط)
  6. Full Bubble Sort (متوسط)
  7. Count the Swaps (متوسط)
  8. Selection Steps (سخت)
  9. Short Words First (سخت)
  10. Podium (سخت)
  11. By Length (آسان)
  12. The Middle One (متوسط)
  13. Smart Bubble (سخت)
  14. Anagram Check (متوسط)

بیشتر بخوان

← جلسه‌ی 31: پیدایش کن! جلسه‌ی 33: تابعی که خودش را صدا می‌زند →