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

معرفی

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

در این مقاله نگاهی به الگوریتم های مرتب سازی محبوب خواهیم داشت، روش کار آنها را درک می کنیم و آنها را در پایتون کدنویسی می کنیم. ما همچنین مقایسه می کنیم که آنها با چه سرعتی موارد را در یک لیست مرتب می کنند.

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

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

مرتب‌سازی حبابی چگونه کار می‌کند؟

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

پس از رسیدن به انتهای لیست، این کار را تکرار می کند process برای هر مورد اگرچه، این است بسیار ناکارآمد. چه می شود اگر فقط یک مجرد swap باید در آرایه ساخته شود؟ چرا هنوز باید \(n^{2}\) بار آن را تکرار کنیم، حتی اگر قبلا مرتب شده است؟

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

چگونه بفهمیم که مرتب سازی را به پایان رسانده ایم؟ اگر اقلام مرتب بودند، مجبور نبودیم swap هر بنابراین، هر زمان که ما swap مقادیری که یک پرچم را روی آنها قرار می دهیم True برای تکرار مرتب سازی process. اگر مبادله ای رخ نداد، پرچم باقی می ماند False و الگوریتم متوقف می شود.

چگونه مرتب سازی حباب را در پایتون پیاده سازی کنیم؟

با بهینه سازی، می توانیم مرتب سازی حباب را در پایتون به صورت زیر پیاده سازی کنیم:

def bubble_sort(nums):
    
    swapped = True
    while swapped:
        swapped = False
        for i in range(len(nums) - 1):
            if nums(i) > nums(i + 1):
                
                nums(i), nums(i + 1) = nums(i + 1), nums(i)
                
                swapped = True



random_list_of_nums = (5, 2, 1, 8, 4)
bubble_sort(random_list_of_nums)
print(random_list_of_nums)

الگوریتم در a اجرا می شود while حلقه، تنها زمانی شکسته می شود که هیچ موردی مبادله نشود. تنظیم کردیم swapped به True در ابتدا مطمئن شوید که الگوریتم حداقل یک بار اجرا می شود.

پیچیدگی زمانی مرتب سازی حباب

در بدترین سناریو (زمانی که لیست به ترتیب معکوس است)، این الگوریتم باید swap تک تک آیتم های آرایه ما swapped پرچم تنظیم خواهد شد True روی هر تکرار

بنابراین اگر داریم n عناصر موجود در لیست خود را خواهیم داشت n تکرار در هر مورد – بنابراین پیچیدگی زمانی مرتب‌سازی حبابی \(O(n^2)\) است.

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

این الگوریتم لیست را بخش می کند به دو بخش: مرتب شده است و طبقه بندی نشده. ما به طور مداوم کوچکترین عنصر از بخش مرتب نشده لیست را حذف می کنیم و آن را به بخش مرتب شده اضافه می کنیم.

چگونه انتخاب مرتب سازی کار می کند؟

در عمل، ما نیازی به ایجاد یک لیست جدید برای عناصر مرتب شده نداریم، کاری که انجام می دهیم این است که سمت چپ لیست را به عنوان بخش مرتب شده در نظر می گیریم. سپس کل لیست را برای کوچکترین عنصر جستجو می کنیم و swap آن را با عنصر اول.

اکنون می دانیم که اولین عنصر لیست مرتب شده است، کوچکترین عنصر از آیتم های باقی مانده را دریافت می کنیم و swap آن را با عنصر دوم. این تا زمانی تکرار می شود که آخرین مورد از لیست، عنصر باقی مانده برای بررسی باشد.

روش پیاده سازی Selection Sort در پایتون

def selection_sort(nums):
    
    for i in range(len(nums)):
        
        lowest_value_index = i
        
        for j in range(i + 1, len(nums)):
            if nums(j) < nums(lowest_value_index):
                lowest_value_index = j
        
        
        nums(i), nums(lowest_value_index) = nums(lowest_value_index), nums(i)



random_list_of_nums = (12, 8, 3, 20, 11)
selection_sort(random_list_of_nums)
print(random_list_of_nums)

ما آن را به عنوان i افزایش می یابد، ما باید موارد کمتری را بررسی کنیم.

پیچیدگی زمانی مرتب سازی انتخاب

ما به راحتی می توانیم پیچیدگی زمانی را با بررسی آن بدست آوریم for حلقه ها در الگوریتم Selection Sort. برای یک لیست با n عناصر، حلقه بیرونی تکرار می شود n بار.

حلقه داخلی تکرار می شود n-1 چه زمانی من برابر 1 است و سپس n-2 مانند من برابر 2 است و غیره.

میزان مقایسه است (n - 1) + (n - 2) + ... + 1، که به Selection Sort پیچیدگی زمانی \(O(n^2)\) می دهد.

مرتب سازی درج

مانند Selection Sort، این الگوریتم لیست را به قسمت های مرتب شده و مرتب نشده تقسیم می کند. روی بخش مرتب نشده تکرار می شود و عنصر مورد مشاهده را در موقعیت صحیح لیست مرتب شده قرار می دهد.

مرتب سازی درج چگونه کار می کند؟

ما فرض می کنیم که اولین عنصر لیست مرتب شده است. سپس به عنصر بعدی می رویم، بیایید آن را صدا کنیم x. اگر x بزرگتر از اولین عنصری است که آن را به همان صورت باقی می گذاریم. اگر x کوچکتر است، مقدار عنصر اول را در موقعیت دوم کپی می کنیم و سپس عنصر اول را روی آن قرار می دهیم x.

همانطور که به سایر عناصر بخش مرتب نشده می رویم، به طور مداوم عناصر بزرگتر را در قسمت مرتب شده به سمت بالا حرکت می دهیم تا زمانی که با عنصری کوچکتر از x یا به انتهای بخش مرتب شده برسید و سپس قرار دهید x در موقعیت صحیح خود

روش پیاده سازی مرتب سازی درج در پایتون

def insertion_sort(nums):
    
    for i in range(1, len(nums)):
        item_to_insert = nums(i)
        
        j = i - 1
        
        
        while j >= 0 and nums(j) > item_to_insert:
            nums(j + 1) = nums(j)
            j -= 1
        
        nums(j + 1) = item_to_insert



random_list_of_nums = (9, 1, 15, 28, 6)
insertion_sort(random_list_of_nums)
print(random_list_of_nums)

پیچیدگی زمانی مرتب سازی درج

در بدترین حالت، یک آرایه به ترتیب معکوس مرتب می شود. بیرونی for loop در تابع مرتب سازی درج همیشه تکرار می شود n-1 بار.

در بدترین حالت، درونی for loop خواهد شد swap یک بار، پس swap دو، و غیره. سپس تعداد مبادله ها خواهد بود 1 + 2 + ... + (n - 3) + (n - 2) + (n - 1) که به Insertion Sort پیچیدگی زمانی \(O(n^2)\) می دهد.

مرتب سازی پشته

این الگوریتم مرتب‌سازی محبوب، مانند مرتب‌سازی Insertion و Selection، فهرست را به بخش‌های مرتب‌شده و مرتب‌نشده تقسیم می‌کند. بخش مرتب نشده لیست را به یک ساختار داده Heap تبدیل می کند تا بتوانیم به طور موثر بزرگترین عنصر را تعیین کنیم.

مرتب سازی هیپ چگونه کار می کند؟

ما با تبدیل لیست به یک شروع می کنیم ماکس هیپ – یک درخت باینری که بزرگترین عنصر آن است root node. سپس آن مورد را در انتهای لیست قرار می دهیم. سپس ما خود را بازسازی می کنیم ماکس هیپ که اکنون یک مقدار کمتر دارد و بزرگترین مقدار جدید را قبل از آخرین مورد لیست قرار می دهد.

ما این را تکرار می کنیم process ساخت پشته تا زمانی که همه گره ها حذف شوند.

روش پیاده سازی مرتب سازی هیپ در پایتون

ما یک تابع کمکی ایجاد خواهیم کرد heapify برای پیاده سازی این الگوریتم:

def heapify(nums, heap_size, root_index):
    
    largest = root_index
    left_child = (2 * root_index) + 1
    right_child = (2 * root_index) + 2

    
    
    if left_child < heap_size and nums(left_child) > nums(largest):
        largest = left_child

    
    if right_child < heap_size and nums(right_child) > nums(largest):
        largest = right_child

    
    if largest != root_index:
        nums(root_index), nums(largest) = nums(largest), nums(root_index)
        
        heapify(nums, heap_size, largest)


def heap_sort(nums):
    n = len(nums)

    
    
    
    
    
    for i in range(n, -1, -1):
        heapify(nums, n, i)

    
    for i in range(n - 1, 0, -1):
        nums(i), nums(0) = nums(0), nums(i)
        heapify(nums, i, 0)



random_list_of_nums = (35, 12, 43, 8, 51)
heap_sort(random_list_of_nums)
print(random_list_of_nums)

پیچیدگی زمانی مرتب‌سازی هیپ

بیایید ابتدا به پیچیدگی زمانی آن نگاه کنیم heapify تابع. در بدترین حالت، بزرگترین عنصر هرگز این نیست root عنصر، این باعث یک تماس بازگشتی به heapify. در حالی که تماس های بازگشتی ممکن است بسیار گران به نظر برسند، به یاد داشته باشید که ما با یک درخت باینری کار می کنیم.

درخت دودویی را با 3 عنصر تجسم کنید، ارتفاع آن 2 است. حالا درخت دودویی را با 7 عنصر تجسم کنید، ارتفاع آن 3 است. درخت به صورت لگاریتمی رشد می کند تا n. این heapify تابع آن درخت را در زمان \(O(log(n))\) طی می کند.

این heap_sort تابع در آرایه \(n\) بارها تکرار می شود. بنابراین پیچیدگی کلی زمانی الگوریتم مرتب‌سازی هیپ \(O(nlog(n))\) است.

ادغام مرتب سازی

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

عناصر مجاور به جفت های مرتب شده تبدیل می شوند، سپس جفت های مرتب شده ادغام شده و با جفت های دیگر نیز مرتب می شوند. این process ادامه می یابد تا زمانی که یک لیست مرتب شده با تمام عناصر لیست ورودی مرتب نشده بدست آوریم.

مرتب سازی ادغام چگونه کار می کند؟

ما به صورت بازگشتی لیست را به نصف تقسیم می کنیم تا زمانی که لیست هایی با اندازه یک داشته باشیم. سپس هر نیمه را که تقسیم شده بود با هم ادغام می کنیم و آنها را در قسمت مرتب می کنیم process.

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

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

روش پیاده سازی Merge Sort در پایتون

def merge(left_list, right_list):
    sorted_list = ()
    left_list_index = right_list_index = 0

    
    left_list_length, right_list_length = len(left_list), len(right_list)

    for _ in range(left_list_length + right_list_length):
        if left_list_index < left_list_length and right_list_index < right_list_length:
            
            
            
            if left_list(left_list_index) <= right_list(right_list_index):
                sorted_list.append(left_list(left_list_index))
                left_list_index += 1
            
            
            else:
                sorted_list.append(right_list(right_list_index))
                right_list_index += 1

        
        
        elif left_list_index == left_list_length:
            sorted_list.append(right_list(right_list_index))
            right_list_index += 1
        
        
        elif right_list_index == right_list_length:
            sorted_list.append(left_list(left_list_index))
            left_list_index += 1

    return sorted_list


def merge_sort(nums):
    
    if len(nums) <= 1:
        return nums

    
    mid = len(nums) // 2

    
    left_list = merge_sort(nums(:mid))
    right_list = merge_sort(nums(mid:))

    
    return merge(left_list, right_list)



random_list_of_nums = (120, 45, 68, 250, 176)
random_list_of_nums = merge_sort(random_list_of_nums)
print(random_list_of_nums)

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

بنابراین، مرتب سازی ادغام به فضایی برای ایجاد یک لیست جدید به اندازه لیست ورودی نیاز دارد.

پیچیدگی زمانی مرتب سازی ادغام

بیایید ابتدا نگاهی به merge تابع. دو لیست می گیرد و تکرار می شود n بارها، کجا n اندازه ورودی ترکیبی آنها است.

این merge_sort تابع آرایه داده شده خود را به 2 تقسیم می کند و به صورت بازگشتی آرایه های فرعی را مرتب می کند. از آنجایی که ورودی بازگشتی نیمی از آنچه داده شده است، مانند درختان دودویی این باعث می شود که زمان لازم برای دریافت آن باشد process رشد لگاریتمی به n.

بنابراین پیچیدگی کلی زمانی الگوریتم Merge Sort \(O(nlog(n))\) است.

مرتب سازی سریع

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

مرتب سازی سریع چگونه کار می کند؟

مرتب سازی سریع با پارتیشن بندی لیست شروع می شود – انتخاب یک مقدار از لیست که در مکان مرتب شده آن قرار خواهد گرفت. این مقدار Pivot نامیده می شود. تمام عناصر کوچکتر از محور به سمت چپ آن منتقل می شوند. تمام عناصر بزرگتر به سمت راست آن منتقل می شوند.

با دانستن اینکه pivot در جای مناسب خود قرار دارد، به صورت بازگشتی مقادیر اطراف محور را مرتب می کنیم تا زمانی که کل لیست مرتب شود.

روش پیاده سازی مرتب سازی سریع در پایتون

def partition(nums, low, high):
    
    
    
    
    pivot = nums((low + high) // 2)
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while nums(i) < pivot:
            i += 1

        j -= 1
        while nums(j) > pivot:
            j -= 1

        if i >= j:
            return j

        
        
        nums(i), nums(j) = nums(j), nums(i)


def quick_sort(nums):
    
    def _quick_sort(items, low, high):
        if low < high:
            
            split_index = partition(items, low, high)
            _quick_sort(items, low, split_index)
            _quick_sort(items, split_index + 1, high)

    _quick_sort(nums, 0, len(nums) - 1)



random_list_of_nums = (22, 5, 1, 18, 99)
quick_sort(random_list_of_nums)
print(random_list_of_nums)

پیچیدگی زمانی مرتب سازی سریع

بدترین سناریو زمانی است که کوچکترین یا بزرگترین عنصر همیشه به عنوان محور انتخاب می شود. این باعث ایجاد پارتیشن هایی با اندازه می شود n-1، باعث تماس های بازگشتی می شود n-1 بار. این ما را به پیچیدگی زمانی در بدترین حالت \(O(n^2)\) هدایت می کند.

در حالی که این یک بدترین حالت وحشتناک است، مرتب سازی سریع به شدت مورد استفاده قرار می گیرد زیرا میانگین پیچیدگی زمانی آن بسیار سریعتر است. در حالی که partition تابع از تودرتو استفاده می کند while حلقه، مقایسه می کند روی تمام عناصر آرایه برای انجام مبادله های آن. به این ترتیب، پیچیدگی زمانی \(O(n)\) دارد.

با یک پیوت خوب، تابع مرتب سازی سریع آرایه را به دو نیم تقسیم می کند که به صورت لگاریتمی با \(n\) رشد می کند. بنابراین میانگین پیچیدگی زمانی الگوریتم مرتب‌سازی سریع \(O(nlog(n))\) است.

توابع مرتب سازی داخلی پایتون

در حالی که درک این الگوریتم‌های مرتب‌سازی مفید است، در اکثر پروژه‌های پایتون احتمالاً از توابع مرتب‌سازی که قبلاً در زبان ارائه شده است استفاده می‌کنید.

می‌توانیم فهرست خود را طوری تغییر دهیم که محتویات آن با فهرست مرتب شوند sort() روش:

apples_eaten_a_day = (2, 1, 1, 3, 1, 2, 2)
apples_eaten_a_day.sort()
print(apples_eaten_a_day) 

یا می توانیم از آن استفاده کنیم sorted() تابع ایجاد یک لیست مرتب شده جدید:

apples_eaten_a_day_2 = (2, 1, 1, 3, 1, 2, 2)
sorted_apples = sorted(apples_eaten_a_day_2)
print(sorted_apples) 

هر دو به ترتیب صعودی مرتب می‌شوند، اما شما می‌توانید به راحتی با تنظیم کردن به ترتیب نزولی مرتب کنید reverse پرچم به True:

apples_eaten_a_day.sort(reverse=True)
print(apples_eaten_a_day) 


sorted_apples_desc = sorted(apples_eaten_a_day_2, reverse=True)
print(sorted_apples_desc) 

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

این توابع مرتب سازی اجرا می کنند تیم مرتب کردن الگوریتم، الگوریتمی الهام گرفته از Merge Sort و Insertion Sort.

مقایسه سرعت

برای اینکه ایده ای از سرعت عملکرد آنها داشته باشیم، لیستی از 5000 عدد بین 0 تا 1000 را ایجاد می کنیم. سپس زمان بندی می کنیم که تکمیل هر الگوریتم چقدر طول می کشد. این کار 10 بار تکرار می شود تا بتوانیم با اطمینان بیشتری الگوی عملکرد را ایجاد کنیم.

این نتایج بود، زمان بر حسب ثانیه است:

اجرا کن	حباب	انتخاب	درج	پشته	ادغام	سریع
1	5.53188	1.23152	1.60355	0.04006	0.02619	0.01639
2	4.92176	1.24728	1.59103	0.03999	0.02584	0.01661
3	4.91642	1.22440	1.59362	0.04407	0.02862	0.01646
4	5.15470	1.25053	1.63463	0.04128	0.02882	0.01860
5	4.95522	1.28987	1.61759	0.04515	0.03314	0.01885
6	5.04907	1.25466	1.62515	0.04257	0.02595	0.01628
7	5.05591	1.24911	1.61981	0.04028	0.02733	0.01760
8	5.08799	1.25808	1.62603	0.04264	0.02633	0.01705
9	5.03289	1.24915	1.61446	0.04302	0.03293	0.01762
10	5.14292	1.22021	1.57273	0.03966	0.02572	0.01606
میانگین	5.08488	1.24748	1.60986	0.04187	0.02809	0.01715

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

ما همچنین متوجه شدیم که مرتب‌سازی سریع بسیار سریع است، تقریباً دو برابر سریع‌تر از Merge Sort و برای اجرا به فضای زیادی نیاز ندارد. به یاد بیاورید که پارتیشن ما مبتنی بود روی عنصر میانی لیست، پارتیشن های مختلف می توانند نتایج متفاوتی داشته باشند.

از آنجایی که Insertion Sort مقایسه‌های بسیار کمتری نسبت به Selection Sort انجام می‌دهد، پیاده‌سازی‌ها معمولاً سریع‌تر هستند، اما در این اجراها، Selection Sort کمی سریع‌تر است.

Insertion Sorts مبادله های بسیار بیشتری نسبت به Selection Sort انجام می دهد. اگر مبادله مقادیر به طور قابل توجهی زمان بیشتری نسبت به مقایسه مقادیر طول بکشد، آنگاه این نتیجه “برعکس” قابل قبول خواهد بود.

نتیجه

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

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