۵ الگوریتم مرتب سازی در پایتون — راهنمای کاربردی

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

مرتب‌سازی حبابی (Bubble Sort)

مرتب‌سازی حبابی یکی از الگوریتم‌هایی است که معمولاً در دوره‌های مقدماتی کلاس‌های علوم رایانه ارائه می‌شود، چون به روشنی طرز کار مرتب‌سازی را نشان می‌دهد و همزمان درک آن نیز ساده و آسان است.

فیلم آموزش الگوریتم های مرتب سازی در زبان برنامه نویسی پایتون با مثال (رایگان) در فرادرس

کلیک کنید

مراحل مرتب‌سازی حبابی از طریق یک لیست و مقایسه عناصر مجاور صورت می‌گیرد. در این فرایند وقتی عناصر در ترتیب نادرستی باشند، با هم دیگر تعویض می‌شوند. این عملیات روی آرایه‌ها تا زمانی که هیچ دو عنصر مجاوری در ترتیب نادرست نباشند، ادامه می‌یابد. از آنجا که مرتب‌سازی حبابی به طور مکرر روی بخش مرتب نشده لیست انجام می‌یابد، مقدار پیچیدگی آن در بدترین حالت برابر با $$O(n^2)$$ است.

1def bubble_sort(arr):
2    def swap(i, j):
3        arr[i], arr[j] = arr[j], arr[i]
4
5    n = len(arr)
6    swapped = True
7    
8    x = -1
9    while swapped:
10        swapped = False
11        x = x + 1
12        for i in range(1, n-x):
13            if arr[i - 1] > arr[i]:
14                swap(i - 1, i)
15                swapped = True
16                    
17return arr

مرتب‌سازی انتخابی (Selection Sort)

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

1def selection_sort(arr):        
2    for i in range(len(arr)):
3        minimum = i
4        
5        for j in range(i + 1, len(arr)):
6            # Select the smallest value
7            if arr[j] < arr[minimum]:
8                minimum = j
9
10        # Place it at the front of the 
11        # sorted end of the array
12        arr[minimum], arr[i] = arr[i], arr[minimum]
13            
14return arr

مرتب‌سازی درجی (Insertion Sort)

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

1def insertion_sort(arr, simulation=False):
2        
3    for i in range(len(arr)):
4        cursor = arr[i]
5        pos = i
6        
7        while pos > 0 and arr[pos - 1] > cursor:
8            # Swap the number down the list
9            arr[pos] = arr[pos - 1]
10            pos = pos - 1
11        # Break and do the final swap
12        arr[pos] = cursor
13
14return arr

مرتب‌سازی ادغامی (Merge Sort)

مرتب‌سازی ادغامی یک نمونه کاملاً عالی از الگوریتم تقسیم و حل (Divide and Conquer) محسوب می‌شود. در این روش مرتب سازی صرفاً از 2 مرحله آن الگوریتم استفاده می‌شود که شامل تقسیم پیوسته و ادغام مکرر است.

تقسیم پیوسته

در این مرحله لیست نامرتب به طور پیوسته تقسیم می‌شود تا این که به N زیرمجموعه برسیم. در این حالت هر زیرمجموعه 1 عنصر دارد که نامرتب است و N تعداد عناصر لیست اصلی است.

ادغام مکرر

این همان مرحله حل در الگوریتم تقسیم و حل است و در آن زیرمجموعه‌ها دو به دو با هم ادغام می‌شوند تا زیرمجموعه‌های جدید مرتبی را شکل بدهند. این کار تا زمانی که همه زیرمجموعه‌ها با هم ادغام شوند و یک آرایه کامل مرتب تشکیل دهند ادامه می‌یابد.

1def merge_sort(arr):
2    # The last array split
3    if len(arr) <= 1:
4        return arr
5    mid = len(arr) // 2
6    # Perform merge_sort recursively on both halves
7    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
8
9    # Merge each side together
10    return merge(left, right, arr.copy())
11
12
13def merge(left, right, merged):
14
15    left_cursor, right_cursor = 0, 0
16    while left_cursor < len(left) and right_cursor < len(right):
17      
18        # Sort each one and place into the result
19        if left[left_cursor] <= right[right_cursor]:
20            merged[left_cursor+right_cursor]=left[left_cursor]
21            left_cursor += 1
22        else:
23            merged[left_cursor + right_cursor] = right[right_cursor]
24            right_cursor += 1
25            
26    for left_cursor in range(left_cursor, len(left)):
27        merged[left_cursor + right_cursor] = left[left_cursor]
28        
29    for right_cursor in range(right_cursor, len(right)):
30        merged[left_cursor + right_cursor] = right[right_cursor]
31
32return merged

مرتب‌سازی سریع (Quick Sort)

مرتب‌سازی سریع نیز یک الگوریتم «تقسیم و حل» مانند مرتب‌سازی ادغامی است. با این که این روش کمی پیچیده‌تر است؛ اما در اغلب موارد، پیاده‌سازی استاندارد آن به طور قابل توجهی سریع‌تر از مرتب‌سازی ادغامی عمل می‌کند و به ندرت به پیچیدگی بدترین حالت خود یعنی $$O(n^2)$$ می‌رسد. این روش مرتب‌سازی 3 مرحله به صورت زیر دارد.

1. در ابتدا یک عنصر از آرایه انتخاب می‌کنیم که آن را محور (pivot) آرایه می‌نامیم.
2. همه عناصر کوچک‌تر از محور را به سمت چپ آن انتقال می‌دهیم. سپس همه عناصر بزرگ‌تر از محور را به سمت راست آن انتقال می‌دهیم. این کار عملیات افراز نامیده می‌شود.
3. دو مرحله فوق را به صورت بازگشتی و جداگانه روی هر یک از زیرمجموعه‌های عناصر به صورت مقادیر بزرگ‌تر و کوچک‌تر از آخرین محور اجرا می‌کنیم.

1def partition(array, begin, end):
2    pivot_idx = begin
3    for i in xrange(begin+1, end+1):
4        if array[i] <= array[begin]:
5            pivot_idx += 1
6            array[i], array[pivot_idx] = array[pivot_idx], array[i]
7    array[pivot_idx], array[begin] = array[begin], array[pivot_idx]
8    return pivot_idx
9
10def quick_sort_recursion(array, begin, end):
11    if begin >= end:
12        return
13    pivot_idx = partition(array, begin, end)
14    quick_sort_recursion(array, begin, pivot_idx-1)
15    quick_sort_recursion(array, pivot_idx+1, end)
16
17def quick_sort(array, begin=0, end=None):
18    if end is None:
19        end = len(array) - 1
20    
21return quick_sort_recursion(array, begin, end)

اگر این مطلب برای شما مفید بوده است و علاقه‌مند به یادگیری بیشتر در این زمینه هستید، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش های برنامه نویسی پایتون
• آموزش ساختمان داده ها
• مجموعه آموزش‌های مهندسی نرم افزار
• معرفی تکنیک های مرتب سازی (Sorting Techniques) — ساختار داده و الگوریتم ها
• آموزش روش تقسیم و حل در طراحی الگوریتم
• مرتب سازی نتایج (Sorting Results) در MySQL — راهنمای جامع
• آموزش آرایه ها در زبان برنامه نویسی C

==