برای مرتب‌سازی در پایتون، هم به ابزارهای آماده نیاز دارید و هم به شناخت الگوریتم‌ها. در پروژه‌های روزمره، ابزارهای آماده داده‌هایی مثل نمرات دانشجویان، قیمت‌ها یا اسامی را به‌سرعت مرتب می‌کنند. در مصاحبه‌های شغلی یا هنگام کار با ساختارهای داده خاص نیز باید منطق الگوریتم‌های پایه را بشناسید. استفاده نادرست از متدهای داخلی پایتون گاهی باعث از دست رفتن لیست اولیه، دریافت خروجی None یا بروز خطای TypeError هنگام کار با داده‌های ناهمگون می‌شود.
شناخت روش‌های چیدمان داده و تفاوت عملکرد آن‌ها از مباحث پایه در مسیر آموزش پایتون است. این ۸ روش کاربردی، ۳ رویکرد مبتنی بر ابزارهای توکار پایتون (sort، sorted و سفارشی‌سازی با پارامتر key) و ۵ روش مبتنی بر الگوریتم‌های کلاسیک علوم کامپیوتر را در بر می‌گیرند. الگوریتم پیش‌فرض پایتون برای مرتب‌سازی نیز Timsort است که شناخت آن به درک رفتار این ابزارها کمک می‌کند.
ابزارهای توکار مرتب‌سازی در پایتون: تفاوت sort() و sorted()
پایتون دو ابزار اصلی برای مرتب کردن داده‌ها دارد. هر دو نتیجه یکسانی تولید می‌کنند، اما رفتارشان با داده اولیه متفاوت است. انتخاب بین متد اختصاصی لیست و تابع عمومی پایتون به نوع داده ورودی و نیاز شما به حفظ ساختار اولیه بستگی دارد.
روش اول: مرتب‌سازی درجا با متد list.sort()
متد sort() فقط برای لیست‌ها تعریف شده است و مرتب‌سازی را به‌صورت درجا (in-place) انجام می‌دهد. یعنی لیست اصلی را تغییر می‌دهد و لیست جدیدی نمی‌سازد. اگر به ترتیب اولیه لیست نیازی ندارید، این روش کمی کارآمدتر است.
این متد، مانند سایر متدهای تغییر درجا نظیر دستور append در پایتون، برای جلوگیری از سردرگمی مقدار None را برمی‌گرداند. بنابراین نباید خروجی آن را داخل دستور print یا یک متغیر جدید قرار دهید:
numbers = [34, -10, 7, 56, 3, 87, 12, 0]
numbers.sort()
print(numbers)
# output: [-10, 0, 3, 7, 12, 34, 56, 87]متد sort() در این کد روی متغیر numbers فراخوانی شده است. پایتون مقادیر عددی لیست را از کوچک‌ترین مقدار (عدد منفی ۱۰) تا بزرگ‌ترین مقدار (عدد ۸۷) در همان فضای حافظه جابه‌جا می‌کند. وقتی در خط سوم لیست اصلی را چاپ می‌کنیم، خروجی چینش جدید را نمایش می‌دهد.
اگر اعضای لیست رشته باشند، متد sort() آن‌ها را بر اساس ترتیب حروف الفبا مرتب می‌کند:
names = ['kevin', 'amir', 'bob', 'jack', 'xander']
print(names.sort())
# output: None
print(names)
# output: ['amir', 'bob', 'jack', 'kevin', 'xander']قرار دادن عبارت names.sort() داخل دستور print تنها مقدار None را در خروجی چاپ می‌کند. با این حال، خود لیست names تغییر کرده است. در دستور چاپ بعدی، اسامی به ترتیب حروف الفبای انگلیسی، از amir تا xander، مرتب شده‌اند.
روش دوم: ساخت لیست مرتب جدید با تابع sorted()
تابع توکار sorted() داده اولیه را بدون تغییر حفظ می‌کند و یک لیست جدید حاوی عناصر مرتب‌شده برمی‌گرداند. برخلاف sort() که مختص لیست است، sorted() هر نوع شیء پیمایش‌پذیر (iterable)، مانند لیست، تاپل (tuple)، مجموعه (set)، رشته و دیکشنری را به‌عنوان ورودی می‌پذیرد.
برای استفاده از خروجی این تابع، باید آن را در یک متغیر جدید ذخیره کنید:
numbers = [6, 9, 3, 1]
sorted_numbers = sorted(numbers)
print(sorted_numbers)
# output: [1, 3, 6, 9]
print(numbers)
# output: [6, 9, 3, 1]در این کد، لیست numbers به تابع sorted() داده شده و خروجی آن در متغیر sorted_numbers ذخیره شده است. با چاپ هر دو متغیر، می‌بینیم که متغیر جدید اعداد مرتب‌شده از ۱ تا ۹ را دارد. لیست اولیه numbers نیز با همان ترتیب نامرتب قبلی دست‌نخورده باقی مانده است.
تفاوت‌های اصلی این دو ابزار در جدول زیر آمده است:
| ویژگی | متد list.sort() | تابع sorted() |
|---|---|---|
| تغییر داده اصلی | لیست اصلی را به‌صورت درجا تغییر می‌دهد. | داده اصلی را دست‌نخورده نگه می‌دارد. |
| مقدار بازگشتی | مقدار None برمی‌گرداند. | یک لیست مرتب‌شده جدید برمی‌گرداند. |
| انواع داده قابل‌پذیرش | فقط روی لیست‌ها (list) کار می‌کند. | تمام اشیاء پیمایش‌پذیر (لیست، تاپل، ست، رشته، دیکشنری) را می‌پذیرد. |
| سرعت و کارایی | کمی کارآمدتر (به دلیل عدم ساخت کپی جدید). | کمی مصرف حافظه بیشتر برای ساخت لیست جدید. |
مرتب‌سازی نزولی با پارامتر reverse
هر دو ابزار به‌طور پیش‌فرض داده‌ها را صعودی، یعنی از کوچک به بزرگ و از A تا Z، مرتب می‌کنند؛ زیرا مقدار پیش‌فرض پارامتر reverse برابر با False است. برای مرتب‌سازی نزولی، از بزرگ به کوچک، کافی است پارامتر بولی reverse=True را به متد sort() یا تابع sorted() بدهید:
numbers = [34, -10, 7, 56, 3, 87, 12, 0]
numbers.sort(reverse=True)
print(numbers)
# output: [87, 56, 34, 12, 7, 3, 0, -10]
names = ["Mona", "Omid", "Sara", "Ehsan"]
sorted_names_desc = sorted(names, reverse=True)
print(sorted_names_desc)
# output: ['Sara', 'Omid', 'Mona', 'Ehsan']در بخش اول کد، اعداد لیست numbers به‌صورت درجا از بزرگ‌ترین عدد (۸۷) تا کوچک‌ترین عدد (منفی ۱۰) چیده شده‌اند. در بخش دوم، اسامی از انتهای حروف الفبا (حرف S در Sara) به سمت ابتدای الفبا (حرف E در Ehsan) مرتب و در متغیر جدید ذخیره شده‌اند.
پارامتر reverse=True با متد list.reverse() متفاوت است. متد reverse() داده‌ها را بر اساس حروف الفبا یا مقدار عددی مرتب نمی‌کند؛ فقط ترتیب فعلی عناصر لیست را از انتها به ابتدا برعکس می‌کند:
thislist = ["banana", "Orange", "Kiwi", "cherry"]
thislist.reverse()
print(thislist)
# output: ['cherry', 'Kiwi', 'Orange', 'banana']روش سوم: سفارشی‌سازی مرتب‌سازی برای رشته، دیکشنری و ساختارهای مرکب
هر دو ابزار list.sort() و sorted() پارامتری به نام key می‌پذیرند که معیار مقایسه عناصر را مشخص می‌کند. مقدار key باید یک تابع یا شیء فراخوانی‌پذیر باشد که یک آرگومان می‌گیرد و کلیدی برای مرتب‌سازی برمی‌گرداند. این روش سرعت بالایی دارد؛ زیرا پایتون پیش از انجام مقایسه‌ها، تابع کلید را دقیقاً یک بار برای هر رکورد ورودی فراخوانی می‌کند.
مرتب‌سازی رشته در پایتون (بر اساس طول و بدون حساسیت به حروف)
مرتب‌سازی پیش‌فرض به بزرگی و کوچکی حروف حساس (case-sensitive) است و تمام حروف بزرگ انگلیسی را پیش از حروف کوچک قرار می‌دهد:
thislist = ["banana", "Orange", "Kiwi", "cherry"]
thislist.sort()
print(thislist)
# output: ['Kiwi', 'Orange', 'banana', 'cherry']برای مرتب‌سازی رشته در پایتون بدون حساسیت به بزرگی و کوچکی حروف، می‌توانید متدهای نوع داده str در پایتون، مانند str.lower یا str.casefold، را به پارامتر key بدهید. متد str.lower کاراکترهای استاندارد را برای مقایسه به حروف کوچک تبدیل می‌کند. متد str.casefold نسخه قوی‌تر و کامل‌تری است و برای یکسان‌سازی حروف در مقایسه‌های بدون حساسیت، حتی برای کاراکترهای خاص یونیکد، به کار می‌رود. در این فرایند، خود رشته‌های داخل لیست تغییر نمی‌کنند و فقط در لحظه مقایسه به حروف کوچک تبدیل می‌شوند:
thislist = ["banana", "Orange", "Kiwi", "cherry"]
thislist.sort(key=str.lower)
print(thislist)
# output: ['banana', 'cherry', 'Kiwi', 'Orange']
words = "This is a test string from Andrew".split()
print(sorted(words, key=str.casefold))
# output: ['a', 'Andrew', 'from', 'is', 'string', 'test', 'This']اگر بخواهید رشته‌ها را به‌جای ترتیب الفبایی، بر اساس تعداد کاراکترهایشان مرتب کنید، تابع توکار len را به پارامتر key بدهید:
names = ['kevin', 'amir', 'bob', 'jack', 'xander', 'al']
print(sorted(names, key=len))
# output: ['al', 'bob', 'amir', 'jack', 'kevin', 'xander']پایتون در این حالت ابتدا طول هر رشته را محاسبه کرده و سپس عناصر را از کوتاه‌ترین رشته (al با ۲ کاراکتر) تا بلندترین رشته (xander با ۶ کاراکتر) مرتب می‌کند.
همین الگو برای اعداد هم کاربرد دارد. با key=abs می‌توانید اعداد را بر اساس قدر مطلق آن‌ها، بدون توجه به علامت منفی، مرتب کنید. همچنین می‌توانید تابعی بنویسید که معیار مرتب‌سازی آن میزان نزدیکی اعداد به عدد ۵۰ باشد:
numbers = [34, -10, 7, -56, 3, -87, 12, 0]
print(sorted(numbers, key=abs))
# output: [0, 3, 7, -10, 12, 34, -56, -87]
def myfunc(n):
return abs(n - 50)
thislist = [100, 50, 65, 82, 23]
thislist.sort(key=myfunc)
print(thislist)
# output: [50, 65, 23, 82, 100]تابع سفارشی myfunc با دستور abs(n – ۵۰) فاصله هر عدد از ۵۰ را محاسبه می‌کند. به همین دلیل، عدد ۵۰ با فاصله صفر در ابتدای لیست قرار می‌گیرد و پس از آن ۶۵ با فاصله ۱۵ می‌آید. عدد ۱۰۰ نیز با فاصله ۵۰ در انتهای لیست قرار می‌گیرد.
مرتب‌سازی دیکشنری در پایتون (کلیدها، آیتم‌ها و لیستی از دیکشنری‌ها)
ساختار کلید-مقدار در دیکشنری در پایتون پیمایش‌پذیر است. اگر یک دیکشنری را مستقیماً به تابع sorted() بدهید، پایتون کلیدهای آن را پیمایش کرده و لیستی از کلیدهای مرتب‌شده برمی‌گرداند:
d = {1: 'D', 2: 'B', 3: 'B', 4: 'E', 5: 'A'}
print(sorted(d))
# output: [1, 2, 3, 4, 5]در پروژه‌های واقعی معمولاً با لیستی از دیکشنری‌ها یا تاپل‌ها روبه‌رو می‌شویم؛ مثلاً فهرستی از دانشجویان که باید بر اساس نمره یا سن مرتب شوند. برای این کار می‌توانیم یک تابع معمولی تعریف کنیم که کلید موردنظر را استخراج کند:
students = [
{"name": "Nazanin", "score": 15},
{"name": "Negar", "score": 18.5},
{"name": "Alireza", "score": 16.5},
{"name": "Mohsen", "score": 18}
]
def get_score(student):
return student['score']
students.sort(reverse=True, key=get_score)
print(students)
# output: [{'name': 'Negar', 'score': 18.5}, {'name': 'Mohsen', 'score': 18}, {'name': 'Alireza', 'score': 16.5}, {'name': 'Nazanin', 'score': 15}]تابع get_score هر بار یکی از دیکشنری‌های داخل لیست students را دریافت کرده و مقدار کلید score آن را برمی‌گرداند. متد sort از این مقدار برای مرتب کردن دیکشنری‌ها بر اساس نمره، از بیشترین به کمترین، استفاده می‌کند.
برای استخراج اندیس تاپل‌ها، کلید دیکشنری‌ها یا ویژگی اشیاء کلاس‌ها، استفاده از تابع لامبدا در پایتون رایج‌تر از تعریف تابع با def است:
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
print(sorted(student_tuples, key=lambda student: student[2]))
# output: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]عبارت بی‌نام lambda student: student[۲] به پایتون می‌گوید که برای مقایسه هر تاپل، عنصر سوم آن را در نظر بگیرد. این عنصر در اندیس ۲ قرار دارد و نشان‌دهنده سن دانشجو است.
اگر لیستی از دیکشنری‌ها با کلیدهای متفاوت داشته باشید، فراخوانی مستقیم sorted() خطای TypeError می‌دهد؛ زیرا مقایسه مستقیم دیکشنری با دیکشنری مجاز نیست. برای رفع این خطا هنگام مرتب‌سازی دیکشنری در پایتون، باید هر دیکشنری را با d.items() به لیستی مرتب از آیتم‌ها تبدیل کنید:
data = [{'a': 1}, {'b': 2}]
print(sorted(data, key=lambda d: sorted(d.items())))
# output: [{'a': 1}, {'b': 2}]مرتب‌سازی چندسطحی و سریع با ماژول operator
استخراج عناصر با اندیس یا نام ویژگی کاری پرتکرار است. به همین دلیل، پایتون در ماژول operator توابع کمکی itemgetter() و attrgetter() را دارد که نوشتن تابع کلید را ساده‌تر و اجرای آن را سریع‌تر می‌کنند. برای فراخوانی این توابع، از دستور import در پایتون استفاده می‌کنیم:
- itemgetter() به عناصر تاپل، لیست یا دیکشنری بر اساس اندیس یا کلید دسترسی پیدا می‌کند.
- attrgetter() برای دسترسی به اشیاء دارای ویژگی‌های نام‌دار، مانند کلاس‌های معمولی، dataclass یا named tuple، به کار می‌رود.
from operator import itemgetter, attrgetter
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
class Student:
def __init__(self, name, grade, age):
self.name = name
self.grade = grade
self.age = age
def __repr__(self):
return repr((self.name, self.grade, self.age))
student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
print(sorted(student_tuples, key=itemgetter(2)))
# output: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]
print(sorted(student_objects, key=attrgetter('age')))
# output: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]این توابع مرتب‌سازی در چند سطح را هم ممکن می‌کنند. برای مثال، می‌توانیم دانشجویان همین مثال را ابتدا بر اساس نمره (grade) و در صورت برابری نمره، بر اساس سن (age) مرتب کنیم:
from operator import itemgetter, attrgetter
student_tuples = [
('john', 'A', 15),
('jane', 'B', 12),
('dave', 'B', 10),
]
class Student:
def __init__(self, name, grade, age):
self.name = name
self.grade = grade
self.age = age
def __repr__(self):
return repr((self.name, self.grade, self.age))
student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
print(sorted(student_tuples, key=itemgetter(1, 2)))
# output: [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]
print(sorted(student_objects, key=attrgetter('grade', 'age')))
# output: [('john', 'A', 15), ('dave', 'B', 10), ('jane', 'B', 12)]نمره هر دو دانشجوی dave و jane برابر با ‘B’ است. به همین دلیل، پایتون به سراغ معیار دوم، یعنی سن، رفته و dave با سن ۱۰ را پیش از jane با سن ۱۲ قرار می‌دهد.
۵ روش الگوریتمی برای مرتب‌سازی در پایتون
شناخت الگوریتم‌های مرتب‌سازی بخشی از دانش عمومی برنامه‌نویسی و یکی از مباحث ثابت مصاحبه‌های شغلی است. از طرف دیگر، متد sort() فقط روی لیست‌های پایتون کار می‌کند. بنابراین اگر بخواهید داده‌ها را در سایر ساختارهای ذخیره داده پیاده‌سازی و مرتب کنید، در مسیر طراحی الگوریتم باید منطق این الگوریتم‌ها را بشناسید.
روش چهارم: مرتب‌سازی حبابی (Bubble Sort)
مرتب‌سازی حبابی در پایتون یکی از ساده‌ترین الگوریتم‌هاست و معمولاً در دوره‌های مقدماتی علوم کامپیوتر آموزش داده می‌شود. این روش شباهت زیادی به الگوریتم مرتب‌سازی تعویضی دارد و به این ترتیب کار می‌کند:
- الگوریتم لیست را پیمایش کرده و عناصر مجاور را دو به دو مقایسه می‌کند.
- اگر دو عنصر مجاور ترتیب نادرستی داشته باشند، الگوریتم جای آن‌ها را با یکدیگر تعویض (swap) می‌کند.
- با هر بار پیمایش کامل آرایه، بزرگ‌ترین عنصرِ بخش مرتب‌نشده مانند یک حباب به موقعیت صحیح خود در انتهای لیست می‌رود.
- برای بهینه‌سازی کد، اگر در یک دور پیمایش هیچ جابه‌جایی رخ ندهد، فرایند متوقف می‌شود؛ زیرا آرایه مرتب شده است.
- چون این عملیات بارها روی بخش مرتب‌نشده تکرار می‌شود، پیچیدگی زمانی آن در بدترین حالت برابر با [فرمول] است.
روش پنجم: مرتب‌سازی انتخابی (Selection Sort)
الگوریتم مرتب‌سازی انتخابی در پایتون بر مقایسه تکیه دارد. با وجود سادگی، در اغلب موارد بهتر از مرتب‌سازی حبابی عمل می‌کند. مراحل اجرای آن به این ترتیب است:
- الگوریتم آرایه ورودی را به دو زیرمجموعه تقسیم می‌کند: زیرمجموعه مرتب‌شده که در ابتدا خالی است و زیرمجموعه نامرتب که منتظر مرتب‌سازی است.
- در گام اول، کوچک‌ترین عنصر زیرمجموعه نامرتب را پیدا کرده و با اولین عنصر جابه‌جا می‌کند تا در انتهای زیرمجموعه مرتب قرار بگیرد.
- در گام بعدی، کوچک‌ترین عنصر باقی‌مانده، یعنی دومین عنصر کوچک کل لیست، را انتخاب کرده و به انتهای بخش مرتب منتقل می‌کند.
- این چرخه تا انتقال تمام عناصر به زیرمجموعه مرتب ادامه پیدا می‌کند.
روش ششم: مرتب‌سازی درجی (Insertion Sort)
مرتب‌سازی درجی در پایتون از هر دو روش حبابی و انتخابی سریع‌تر و ساده‌تر است. عملکرد آن به روشی شباهت دارد که افراد به‌طور غریزی برای مرتب کردن کارت‌های بازی در دست خود استفاده می‌کنند:
- اگر طول آرایه ورودی ۰ یا ۱ باشد، تابع بلافاصله بازمی‌گردد؛ زیرا آرایه ۰ یا ۱ عنصری از پیش مرتب است.
- برای آرایه‌های بزرگ‌تر، الگوریتم عنصر اول را مرتب فرض می‌کند و پیمایش را از عنصر دوم آغاز می‌کند.
- الگوریتم عنصر دوم را با عنصر اول مقایسه کرده و اگر کوچک‌تر باشد، آن‌ها را جابه‌جا می‌کند.
- سپس به سراغ عنصر سوم رفته، آن را با دو عنصر اول مقایسه می‌کنیم و در موقعیت درستش در بخش مرتب‌شده قرار می‌دهیم.
- این تکرار تا قرار گرفتن تمام عناصر ورودی در جایگاه صحیح خود ادامه می‌یابد.
روش هفتم: مرتب‌سازی ادغامی (Merge Sort)
الگوریتم مرتب‌سازی ادغامی در پایتون بر پایه رویکرد «تقسیم و حل» (Divide and Conquer) کار می‌کند. اجرای آن دو مرحله اصلی دارد:
- تقسیم پیوسته: الگوریتم لیست نامرتب را به‌طور بازگشتی از وسط به دو نیم تقسیم می‌کند تا به [فرمول] زیرمجموعه برسیم که هرکدام دقیقاً ۱ عنصر دارند ( [فرمول] تعداد عناصر لیست اصلی است).
- ادغام مکرر: این بخش مرحله «حل» است. تابع merge(arr, l, m, r) زیرمجموعه‌ها را دو به دو ترکیب می‌کند تا زیرمجموعه‌های جدید و مرتبی بسازد. هنگام ادغام، تابع عناصر ابتدایی دو زیرمجموعه را مقایسه کرده و عنصر کوچک‌تر را در لیست ترکیبی قرار می‌دهد. این ادغام گام‌به‌گام ادامه می‌یابد تا یک آرایه کامل و مرتب تشکیل شود.
نسخه دیگری از این الگوریتم به نام ۳-way Merge Sort نیز وجود دارد. در این نسخه، آرایه در هر مرحله به‌جای دو نیمه به سه بخش مساوی تقسیم می‌شود تا عمق بازگشت کاهش یابد.
روش هشتم: مرتب‌سازی سریع (Quick Sort)
مرتب‌سازی سریع در پایتون نیز مانند روش ادغامی از رویکرد «تقسیم و حل» استفاده می‌کند. پیاده‌سازی آن کمی پیچیده‌تر است، اما نسخه استانداردش در اغلب موارد سریع‌تر از مرتب‌سازی ادغامی عمل می‌کند و میانگین زمان اجرای آن O(n log n) است. بدترین حالت به روش انتخاب محور بستگی دارد. انتخاب محور تصادفی یا میانه‌ی چند عنصر احتمال وقوع این حالت را کم می‌کند؛ اما اگر همیشه عنصر اول یا آخر محور باشد و ورودی از قبل مرتب باشد، پیچیدگی به [فرمول] می‌رسد. این روش در ۳ مرحله انجام می‌شود:
- انتخاب محور: الگوریتم یک عنصر از آرایه را به‌عنوان محور (Pivot) انتخاب می‌کند.
- عملیات افراز (Partitioning): الگوریتم تمام عناصر آرایه را با محور می‌سنجد و عناصر کوچک‌تر از محور را به سمت چپ و عناصر بزرگ‌تر را به سمت راست آن منتقل می‌کند. در پایان این گام، عنصر محور دقیقاً در موقعیت نهایی و درست خود در آرایه مرتب قرار می‌گیرد.
- اجرای بازگشتی: الگوریتم با کمک تابع بازگشتی در پایتون دو مرحله قبل را جداگانه روی زیرمجموعه‌های سمت چپ (مقادیر کوچک‌تر) و سمت راست (مقادیر بزرگ‌تر) تکرار می‌کند تا کل آرایه مرتب شود.
پایتون در پشت صحنه از چه الگوریتمی استفاده می‌کند؟ (Timsort و پایداری)
وقتی متد sort() یا تابع sorted() را صدا می‌زنید، پایتون از الگوریتم Timsort استفاده می‌کند. تیم پیترز (Tim Peters) این الگوریتم را در سال ۲۰۰۲ طراحی کرد. Timsort یک الگوریتم ترکیبی (Hybrid) برگرفته از مرتب‌سازی ادغامی (Merge Sort) و مرتب‌سازی درجی (Insertion Sort) است. کارایی بالای آن روی داده‌های واقعی به این دلیل است که دنباله‌های متوالیِ از پیش مرتب‌شده، موسوم به runs، را در داده‌ها شناسایی کرده و با رویکرد ادغامی بهینه‌شده ترکیب می‌کند.
مرتب‌سازی در پایتون ویژگی پایداری (Stability) دارد. پایداری تضمین می‌کند که اگر چند رکورد کلید یکسانی داشته باشند، ترتیب اولیه آن‌ها پس از مرتب‌سازی حفظ می‌شود:
from operator import itemgetter
data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
print(sorted(data, key=itemgetter(0)))
# output: [('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]در این کد، هر دو رکورد ‘blue’ کلید اول یکسانی دارند. پس از مرتب‌سازی نیز (‘blue’, ۱) همچنان قبل از (‘blue’, ۲) قرار می‌گیرد. حتی با فعال کردن پارامتر reverse=True، این پایداری حفظ می‌شود.
پایداری اجازه می‌دهد مرتب‌سازی‌های پیچیده با جهت‌های متفاوت، مثلاً نمره به‌صورت نزولی و سن به‌صورت صعودی، را در چند گام متوالی انجام دهید. برای این کار، ابتدا داده‌ها را بر اساس کلید فرعی (سن) و سپس بر اساس کلید اصلی (نمره) مرتب می‌کنید:
from operator import attrgetter
class Student:
def __init__(self, name, grade, age):
self.name = name
self.grade = grade
self.age = age
def __repr__(self):
return repr((self.name, self.grade, self.age))
student_objects = [
Student('john', 'A', 15),
Student('jane', 'B', 12),
Student('dave', 'B', 10),
]
s = sorted(student_objects, key=attrgetter('age')) # گام اول: کلید فرعی (صعودی)
result = sorted(s, key=attrgetter('grade'), reverse=True) # گام دوم: کلید اصلی (نزولی)
print(result)
# output: [('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]الگوریتم Timsort این مرتب‌سازی‌های چندمرحله‌ای را با کارایی بالایی انجام می‌دهد؛ زیرا از ترتیب ایجادشده در گام قبلی استفاده می‌کند.
رفع خطای TypeError هنگام مرتب‌سازی داده‌های ناهمگون
در پایتون، روال‌های مرتب‌سازی برای مقایسه دو شیء از عملگر < استفاده می‌کنند. اگر داده‌های داخل یک لیست از انواع غیرقابل‌مقایسه باشند، پایتون خطای TypeError پرتاب می‌کند. برای جلوگیری از این خطا در مجموعه داده‌های واقعی، از این راهبردها استفاده کنید:
- ترکیب عدد و رشته: مقایسه‌های بین‌نوعی، مثلاً عدد ۱۰ با رشته ’۱۱’، خطا ایجاد می‌کنند. اگر فقط رفع خطا مدنظر است و ترتیب عددی اهمیتی ندارد، می‌توانید همه عناصر را با map به رشته تبدیل کنید. البته رشته‌ها حرف‌به‌حرف مقایسه می‌شوند و ’۱۰’ پیش از ‘۲’ قرار می‌گیرد. اگر ترتیب عددی لازم است، مقدار key را float یا int بگذارید تا هر عنصر فقط برای مقایسه به عدد تبدیل شود. این روش زمانی مناسب است که همه‌ی رشته‌ها عددی باشند:data = [۱۰, ’۱۱’, ۲, ‘۳’]print(sorted(map(str, data)))# output: [’۱۰’, ’۱۱’, ‘۲’, ‘۳’]print(sorted(data, key=float))# output: [۲, ‘۳’, ۱۰, ’۱۱’]
- وجود مقدار None در داده‌ها: مقدار None با سایر انواع داده قابل‌مقایسه نیست. پیش از مرتب‌سازی، آن را با یک عبارت ژنراتور حذف کنید:data = [۳, None, ۱, ۲]print(sorted(x for x in data if x is not None))# output: [۱, ۲, ۳]
- وجود مقدار NaN در اعداد اعشاری: طبق استاندارد IEEE-۷۵۴، مقدار NaN در مقایسه با هر چیزی، حتی خودش، نامرتب است. با کمک isnan و filterfalse آن را فیلتر کنید:from math import isnanfrom itertools import filterfalsedata = [۳.۰, float(‘nan’), ۱.۰]print(sorted(filterfalse(isnan, data)))# output: [۱.۰, ۳.۰]
- مرتب‌سازی لیستی از مجموعه‌ها (Sets): عناصر داخل مجموعه (set) ترتیب قطعی ندارند. پیش از مرتب‌سازی لیست بیرونی، هر مجموعه را به یک لیست مرتب تبدیل کنید:s = {۳, ۱, ۲}print(sorted(s))# output: [۱, ۲, ۳]
برای یادگیری عمیق‌تر ساختار داده‌ها، مدیریت خطاها و تسلط بر کتابخانه‌های استاندارد، می‌توانید از دوره‌های تخصصی مکتب‌خونه استفاده کنید.
