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

آموزش پایتون

مرتب‌سازی و جستجو در پایتون: sort، sorted و جستجوی دودویی

۹ دقیقه مطالعه · ۳۰ مهر ۱۴۰۵

فهرست مطالب
  1. sorted و sort: کدام را کی به کار ببریم؟
  2. key و reverse: مرتب‌سازی با معیار دلخواه
  3. مرتب‌سازی رکوردها: لیست دیکشنری‌ها و تاپل‌ها
  4. جستجوی خطی: خانه‌به‌خانه
  5. جستجوی دودویی: هر بار نصف لیست
  6. مرتب‌سازی حبابی با دست
  7. مرتب‌سازی انتخابی با دست
  8. کدام روش سریع‌تر است؟ پیچیدگی زمانی
  9. سؤال‌های پرتکرار

برای مرتب‌سازی در پایتون دو ابزار آماده داریم: تابع sorted() که یک لیست مرتب‌شده‌ی تازه برمی‌گرداند و متد list.sort() که خود لیست را مرتب می‌کند و None برمی‌گرداند. هر دو با reverse=True نزولی مرتب می‌کنند و با key بر اساس هر معیاری، مثل طول کلمه یا نمره‌ی دانش‌آموز. برای جستجو، in و index() لیست را خانه‌به‌خانه می‌گردند (جستجوی خطی)، اما در یک لیست مرتب، جستجوی دودویی با هر مقایسه نیمی از لیست را کنار می‌گذارد و بسیار سریع‌تر است.

در این مقاله اول ابزارهای آماده‌ی پایتون را یاد می‌گیریم: فرق sorted و sort، کار با key و reverse و مرتب کردن رکوردهایی مثل لیست دانش‌آموزها. بعد جستجوی خطی و دودویی را خودمان می‌نویسیم، دو الگوریتم معروف مرتب‌سازی حبابی و انتخابی را با دست پیاده می‌کنیم و در پایان با یک جدول ساده می‌بینیم کدام روش سریع‌تر است و چرا.

sorted و sort: کدام را کی به کار ببریم؟

scores = [17, 12, 20, 15]
ordered = sorted(scores)
print(ordered)
print(scores)

scores.sort()
print(scores)
[12, 15, 17, 20]
[17, 12, 20, 15]
[12, 15, 17, 20]

sorted(scores) یک لیست تازه ساخت و لیست اصلی دست‌نخورده ماند. اما scores.sort() خود لیست را عوض کرد. یک اشتباه بسیار رایج این است که نتیجه‌ی sort() را در متغیر بریزیم:

nums = [3, 1, 2]
result = nums.sort()
print(result)
print(nums)
None
[1, 2, 3]

sort() چیزی برنمی‌گرداند (یعنی None)، چون کارش را روی خود لیست انجام داده است. پس هیچ‌وقت ننویسید nums = nums.sort()؛ این کار لیست را با None جایگزین می‌کند.

ویژگیsorted(x)x.sort()
چه برمی‌گرداند؟لیست مرتب‌شده‌ی تازهNone
لیست اصلیدست‌نخورده می‌ماندعوض می‌شود
روی چه چیزهایی کار می‌کند؟هر چیز قابل پیمایش: لیست، تاپل، رشته، دیکشنریفقط لیست
کی مناسب است؟وقتی نسخه‌ی اصلی را هم لازم داریدوقتی فقط نسخه‌ی مرتب را می‌خواهید

sorted روی هر چیزی که بشود رویش حلقه زد کار می‌کند؛ مثلاً sorted("python") حرف‌های کلمه را مرتب می‌کند و sorted روی یک دیکشنری، کلیدهایش را مرتب‌شده برمی‌گرداند. جواب sorted همیشه یک لیست است.

key و reverse: مرتب‌سازی با معیار دلخواه

پارامتر reverse=True ترتیب را نزولی (از بزرگ به کوچک) می‌کند. پارامتر key یک تابع می‌گیرد و پایتون به‌جای خود عنصرها، جواب آن تابع را مقایسه می‌کند:

words = ["banana", "Kiwi", "apple", "fig"]
print(sorted(words))
print(sorted(words, key=str.lower))
print(sorted(words, key=len))
print(sorted(words, key=len, reverse=True))
['Kiwi', 'apple', 'banana', 'fig']
['apple', 'banana', 'fig', 'Kiwi']
['fig', 'Kiwi', 'apple', 'banana']
['banana', 'apple', 'Kiwi', 'fig']

در خط اول Kiwi اول آمده، چون پایتون رشته‌ها را با کد حرف‌ها مقایسه می‌کند و همه‌ی حرف‌های بزرگ انگلیسی کد کوچک‌تری از حرف‌های کوچک دارند. key=str.lower همه را موقتاً کوچک می‌کند تا ترتیب الفبایی درست شود؛ خود کلمه‌ها عوض نمی‌شوند. key=len هم کلمه‌ها را بر اساس طولشان مرتب می‌کند. دقت کنید که اسم تابع را بدون پرانتز می‌دهیم (len، نه len())، چون خود پایتون آن را برای هر عنصر صدا می‌زند.

مرتب‌سازی رکوردها: لیست دیکشنری‌ها و تاپل‌ها

در برنامه‌های واقعی معمولاً عددهای تنها را مرتب نمی‌کنیم، بلکه رکوردها را؛ مثل دانش‌آموزهایی که هر کدام اسم و نمره دارند. اینجا key با یک lambda (تابع کوچک یک‌خطی) کار را راحت می‌کند:

students = [
    {"name": "Sara", "score": 18},
    {"name": "Ali", "score": 15},
    {"name": "Reza", "score": 18},
    {"name": "Mina", "score": 20},
]

by_score = sorted(students, key=lambda s: s["score"], reverse=True)
for s in by_score:
    print(s["name"], s["score"])
Mina 20
Sara 18
Reza 18
Ali 15

lambda s: s["score"] یعنی «از هر دانش‌آموز، نمره‌اش را بده». سارا و رضا هر دو ۱۸ گرفته‌اند و سارا اول آمده، چون در لیست اصلی هم قبل از رضا بود. مرتب‌سازی پایتون پایدار (stable) است؛ یعنی عنصرهای مساوی ترتیب قبلی‌شان را حفظ می‌کنند.

اگر بخواهید در نمره‌های مساوی، اسم‌ها الفبایی باشند، key یک تاپل برگرداند. پایتون اول عضو اول تاپل را مقایسه می‌کند و اگر مساوی بود، سراغ عضو دوم می‌رود:

students = [
    {"name": "Sara", "score": 18},
    {"name": "Ali", "score": 15},
    {"name": "Reza", "score": 18},
    {"name": "Mina", "score": 20},
]

ranked = sorted(students, key=lambda s: (-s["score"], s["name"]))
print([s["name"] for s in ranked])

games = [("Ali", 120), ("Sara", 150), ("Reza", 90)]
print(max(games, key=lambda g: g[1]))
['Mina', 'Reza', 'Sara', 'Ali']
('Sara', 150)

علامت منفی در -s["score"] نمره‌ها را نزولی می‌کند، در حالی که اسم‌ها صعودی می‌مانند. خط آخر هم نشان می‌دهد max و min هم key می‌پذیرند: بهترین بازی را بدون مرتب کردن کل لیست پیدا کردیم. برای آشنایی بیشتر با لیست و دیکشنری، مقاله‌های لیست در پایتون و دیکشنری در پایتون را ببینید.

جستجوی خطی: خانه‌به‌خانه

ساده‌ترین روش جستجو این است که از اول لیست شروع کنیم و تک‌تک خانه‌ها را نگاه کنیم تا چیزی را که می‌خواهیم پیدا کنیم. به این روش جستجوی خطی (linear search) می‌گویند:

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

pets = ["cat", "dog", "fish", "parrot"]
print(linear_search(pets, "fish"))
print(linear_search(pets, "lion"))
print("dog" in pets, pets.index("dog"))
2
-1
True 1

تابع شماره‌ی خانه را برمی‌گرداند و اگر چیزی پیدا نشد، -1. همین که پیدا شد، return حلقه را تمام می‌کند و بقیه‌ی لیست را نمی‌گردد. ابزارهای آماده‌ی پایتون، یعنی in و index()، هم پشت صحنه همین کار را می‌کنند. فقط حواستان باشد که index() اگر چیزی پیدا نکند، خطای ValueError می‌دهد.

جستجوی خطی روی هر لیستی کار می‌کند، چه مرتب باشد چه نباشد. عیبش این است که در بدترین حالت باید همه‌ی خانه‌ها را نگاه کند. برای لیستی با یک میلیون عنصر، یعنی یک میلیون مقایسه.

جستجوی دودویی: هر بار نصف لیست

بازی حدس عدد را به یاد بیاورید: «عددی بین ۱ تا ۱۰۰ در ذهنم است». بهترین حدس اول ۵۰ است، چون با جواب «بزرگ‌تر» یا «کوچک‌تر» نیمی از عددها کنار می‌روند. جستجوی دودویی (binary search) دقیقاً همین است، اما فقط روی لیست مرتب کار می‌کند:

def binary_search(items, target):
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        print(f"look at index {mid}: {items[mid]}")
        if items[mid] == target:
            return mid
        if items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

nums = [3, 8, 12, 17, 21, 25, 30, 34, 41, 47]
print("result:", binary_search(nums, 41))
print("result:", binary_search(nums, 20))
look at index 4: 21
look at index 7: 34
look at index 8: 41
result: 8
look at index 4: 21
look at index 1: 8
look at index 2: 12
look at index 3: 17
result: -1

low و high مرز بخشی از لیست هستند که هنوز ممکن است جواب در آن باشد. هر بار وسط این بخش (mid) را نگاه می‌کنیم: اگر عدد وسط کوچک‌تر از هدف بود، نیمه‌ی چپ کنار می‌رود و اگر بزرگ‌تر بود، نیمه‌ی راست. برای پیدا کردن ۴۱ فقط سه خانه را نگاه کردیم و برای این‌که بفهمیم ۲۰ در لیست نیست، چهار خانه. جستجوی خطی برای ۴۱ باید نُه خانه را نگاه می‌کرد.

پایتون ماژول آماده‌ای به اسم bisect هم برای جستجوی دودویی دارد که علاوه بر پیدا کردن، می‌تواند عنصر تازه را در جای درستش در لیست مرتب بگذارد:

import bisect

nums = [3, 8, 12, 17, 21, 25, 30, 34, 41, 47]
i = bisect.bisect_left(nums, 34)
print(i, nums[i] == 34)
bisect.insort(nums, 20)
print(nums)
7 True
[3, 8, 12, 17, 20, 21, 25, 30, 34, 41, 47]

جستجوی دودویی روی لیست نامرتب جواب غلط می‌دهد، بدون این‌که خطایی نشان دهد. اگر قرار است در یک لیست زیاد جستجو کنید، یک بار مرتبش کنید و بعد از جستجوی دودویی استفاده کنید.

جستجوی دودویی را می‌شود بازگشتی هم نوشت؛ تابعی که خودش را برای نیمه‌ی باقی‌مانده صدا می‌زند. درباره‌ی این شیوه، مقاله‌ی تابع بازگشتی در پایتون را بخوانید.

مرتب‌سازی حبابی با دست

حالا که sorted را داریم، چرا مرتب‌سازی را خودمان بنویسیم؟ چون نوشتنش فکر الگوریتمی را تمرین می‌دهد و می‌فهمید چرا بعضی روش‌ها از بقیه سریع‌ترند. مرتب‌سازی حبابی (bubble sort) هر بار دو عنصر کنار هم را مقایسه می‌کند و اگر جابه‌جا بودند، جایشان را عوض می‌کند. در پایان هر دور، بزرگ‌ترین عنصر باقی‌مانده مثل یک حباب به ته لیست می‌رسد:

def bubble_sort(items):
    items = items[:]          # work on a copy
    n = len(items)
    for end in range(n - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        print("after a pass:", items)
        if not swapped:
            break
    return items

print(bubble_sort([5, 1, 4, 2, 8]))
after a pass: [1, 4, 2, 5, 8]
after a pass: [1, 2, 4, 5, 8]
after a pass: [1, 2, 4, 5, 8]
[1, 2, 4, 5, 8]

items[:] یک کپی می‌سازد تا لیست اصلی عوض نشود. خط items[i], items[i + 1] = items[i + 1], items[i] روش پایتونی جابه‌جا کردن دو مقدار است. متغیر swapped هم یک ترفند هوشمندانه است: اگر در یک دور کامل هیچ جابه‌جایی‌ای رخ نداد، لیست مرتب است و بقیه‌ی دورها لازم نیست. برای همین دور سوم آخرین دور بود.

مرتب‌سازی انتخابی با دست

مرتب‌سازی انتخابی (selection sort) مثل مرتب کردن کارت‌ها در دست است: کوچک‌ترین کارت را پیدا می‌کنید و اول می‌گذارید، بعد کوچک‌ترینِ بقیه را پیدا می‌کنید و دوم می‌گذارید و همین‌طور تا آخر:

def selection_sort(items):
    items = items[:]
    for i in range(len(items) - 1):
        smallest = i
        for j in range(i + 1, len(items)):
            if items[j] < items[smallest]:
                smallest = j
        items[i], items[smallest] = items[smallest], items[i]
    return items

print(selection_sort([29, 10, 14, 37, 13]))
[10, 13, 14, 29, 37]

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

کدام روش سریع‌تر است؟ پیچیدگی زمانی

برنامه‌نویس‌ها سرعت الگوریتم را با پیچیدگی زمانی و نماد Big-O توصیف می‌کنند؛ یعنی این‌که با بزرگ شدن ورودی (n)، تعداد کارها چطور زیاد می‌شود.

الگوریتمبدترین حالتلیست باید مرتب باشد؟نکته
جستجوی خطیO(n)نهساده؛ برای لیست‌های کوچک کافی است
جستجوی دودوییO(log n)بلهبرای لیست‌های بزرگ بسیار سریع
مرتب‌سازی حبابیO(n²)–آموزشی؛ لیست تقریباً مرتب را زود تمام می‌کند
مرتب‌سازی انتخابیO(n²)–آموزشی؛ جابه‌جایی کمی دارد
sorted و sortO(n log n)–ابزار آماده‌ی پایتون؛ انتخاب اول در عمل

این عددها در عمل یعنی چه؟ جدول زیر تعداد مقایسه‌ها را در بدترین حالت نشان می‌دهد:

تعداد عنصرهاجستجوی خطیجستجوی دودوییحبابی یا انتخابی
۱۰۱۰۴۴۵
۱۰۰۱۰۰۷۴٬۹۵۰
۱٬۰۰۰۱٬۰۰۰۱۰۴۹۹٬۵۰۰
۱٬۰۰۰٬۰۰۰۱٬۰۰۰٬۰۰۰۲۰حدود ۵۰۰ میلیارد

جستجوی دودویی در لیستی با یک میلیون عنصر، با حداکثر ۲۰ مقایسه به جواب می‌رسد. اما مرتب‌سازی حبابی برای همان لیست صدها میلیارد مقایسه لازم دارد؛ برای همین در برنامه‌های واقعی همیشه از sorted و sort استفاده می‌کنیم که از الگوریتمی به اسم Timsort استفاده می‌کنند و برای داده‌های واقعی بسیار بهینه‌اند. اگر به این موضوع علاقه دارید، دوره‌ی پایتون حرفه‌ای جلسه‌های پیچیدگی زمانی و Big-O، جست‌وجو و مرتب‌سازی را دارد که مرتب‌سازی ادغامی و درجی را هم پیاده می‌کنند. کدهای این مقاله را هم می‌توانید در ویرایشگر آنلاین پایتون اجرا کنید و لیست‌های خودتان را به آن‌ها بدهید. برای تمرین بیشتر کار با لیست‌ها، بخش لیست در تمرین‌خانه‌ی پایتون را ببینید.

سؤال‌های پرتکرار

فرق sort و sorted در پایتون چیست؟

sorted() یک لیست مرتب‌شده‌ی تازه برمی‌گرداند و نسخه‌ی اصلی را دست نمی‌زند، و روی هر چیز قابل پیمایشی کار می‌کند. list.sort() فقط برای لیست است، خود لیست را مرتب می‌کند و None برمی‌گرداند.

چطور یک لیست را در پایتون نزولی مرتب کنم؟

کافی است reverse=True را اضافه کنید: sorted(nums, reverse=True) یا nums.sort(reverse=True). برای عددها می‌توانید در key هم از علامت منفی استفاده کنید، که در مرتب‌سازی چندمعیاره به کار می‌آید.

چطور لیستی از دیکشنری‌ها را بر اساس یک کلید مرتب کنم؟

از key با یک lambda استفاده کنید؛ مثلاً sorted(students, key=lambda s: s["score"]). برای چند معیار، key را طوری بنویسید که یک تاپل برگرداند، مثل (-s["score"], s["name"]).

جستجوی دودویی چیست و کی می‌شود از آن استفاده کرد؟

روشی است که در هر قدم، وسط بخش باقی‌مانده‌ی لیست را نگاه می‌کند و نیمی از لیست را کنار می‌گذارد. فقط روی لیست مرتب درست کار می‌کند و در یک میلیون عنصر، حداکثر با ۲۰ مقایسه جواب را پیدا می‌کند.

سریع‌ترین روش مرتب‌سازی در پایتون کدام است؟

در عمل، همان sorted() و list.sort() که از الگوریتم Timsort استفاده می‌کنند و پیچیدگی‌شان O(n log n) است. این دو بسیار بهینه نوشته شده‌اند و تقریباً همیشه از هر مرتب‌سازی دست‌نویسی سریع‌ترند.

وقتی sorted هست، چرا مرتب‌سازی حبابی را یاد بگیرم؟

برای این‌که فکر الگوریتمی، حلقه‌های تودرتو و جابه‌جا کردن مقدارها را تمرین کنید و بفهمید چرا بعضی الگوریتم‌ها سریع‌ترند. این‌ها پایه‌ی مسابقه‌های برنامه‌نویسی و مصاحبه‌های کاری هستند. در برنامه‌های واقعی اما از sorted استفاده کنید.

همین حالا روی Battle Code تمرین کن

مقاله‌های دیگر

همه‌ی مقاله‌ها