به نام خدا
در این مطلب قراره با شیوه کار دو الگوریتم مرتب سازی Insertion Sort & Merge Sort آشنا بشید و در ادامه کد پایتون این دو الگوریتم رو ببینید .
1_Insertion Sort یا مرتب سازی درجی :
ابتدا روش انجام این مرتب سازی رو ببینید
حالا اگه بخوایم همچین الگوریتمی رو توی برنامه پایتون خودمون پیاده سازی کنیم از قطعه کد زیر استفاده میکنیم:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#mohandesjan.ir def insertion_sort(arr, simulation=False): for i in range(len(arr)): cursor = arr[i] pos = i while pos > 0 and arr[pos - 1] > cursor: # Swap the number down the list arr[pos] = arr[pos - 1] #mohandesjan.ir pos = pos - 1 # Break and do the final swap arr[pos] = cursor return arr |
2_Merge Sort یا مرتب سازی ادغامی:
این الگوریتم نسبت به الگوریتم قبلی پیچیدگی کمتری دارد (بازده کار مرتب سازی ما با این الگوریتم بالاتر میره)
این الگوریتم از دو قسمت اصلی تشکیل شده
اولین قسمت اینه که تعداد عضو ها رو شروع میکنه به نصف کردن و این کارو تا جایی ادامه میده که تنها به یک عضو برسیم
در مرحله دوم از اون تک عضوی ها شروع میکنه به مرتب کردن داده ها تا جایی که همه داده ها مرتب بشن
شیوه کار این الگوریتم رو بطور واضح تری با تصویر زیر ببینید
بریم سراغ کد پایتون این الگوریتم:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
def merge_sort(arr): # The last array split if len(arr) <= 1: return arr mid = len(arr) // 2 # Perform merge_sort recursively on both halves left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:]) # Merge each side together return merge(left, right, arr.copy()) #mohandesjan.ir def merge(left, right, merged): left_cursor, right_cursor = 0, 0 while left_cursor < len(left) and right_cursor < len(right): # Sort each one and place into the result if left[left_cursor] <= right[right_cursor]: merged[left_cursor+right_cursor]=left[left_cursor] left_cursor += 1 else: merged[left_cursor + right_cursor] = right[right_cursor] right_cursor += 1 for left_cursor in range(left_cursor, len(left)): merged[left_cursor + right_cursor] = left[left_cursor] #mohandesjan.ir for right_cursor in range(right_cursor, len(right)): merged[left_cursor + right_cursor] = right[right_cursor] return merged |
سوالی داشتید همین پایین کامنت کنید
موفق باشید 🙂
I am so happy to read this. This is the type of manual that needs to be given and not the accidental misinformation that is at the other blogs. Appreciate your sharing this best doc. Suzanna Orlando Zel