یکم الگوریتم

تو این مطلب میخوایم خیلی خلاصه چندتا از الگوریتم های مرتب سازی و باهم ببینیمالگوریتم های مرتب سازی و بر اساس نحوه مرتب سازی به ۲ دسته میشه تقسیم کردمبتی بر مقایسه : با مقایسه بین کلید های عناصر ترتیب پیدا میشهمثل مرتب سازی های : حبابی - انتخابی - درجی - ادغامی - سریع - هیپ - درختی - شلغیرمقایسه ای (خطی):بدون مقایسه کلیدهای عناصر باهم مرتب سازی انجام میشهمثل مرتب سازی های : شمارشی - مبنایی - سطلی - لانه کبوتریخب شروع میکنیم روش کار چندتا از این الگوریتم هارو ببینیم :)مرتب سازی حبابی (Bubble sort): یه ارایه نامرتب و بهش میدیم بعد توی طول ارایه حرکت میکنیم و یک عنصر را با عنصر مجاورش با هم مقایسه میکنیم و اگه تو ترتیبی که میخوایم مرتب کنیم نباشن میایم جاشونو با هم عوض میکنیمشبه کد این الگوریتمBUBBLESORT(A):for i = 1 to A.length-1for j = A.length downto i + 1if A[j] > A[j+1]exchange A[j] with A[j+1] و کد این الگوریتم :def bubble_sort(array):for i in range(0, len(array) - 1):for j in range(len(array) - 1):if (array[j] > array[j + 1]):temp = array[j]array[j] = array[j + 1]array[j + 1] = tempreturn arrayاین الگوریتم برای مجموعه داده‌های بزرگ مناسب نیست . پیچیدگی حالت میانگین و بدترین حالت آن برابر با (Ο(n2 است .مرتب سازی درجی (insertion sort):شما میتونید مثل یه بازی کارت در نظر بگیرید به این صورت که درست چپتون خالیه کارتارو یکی یکی بر میدارین میزارین تو مکان درست تو دست چپتون (درج میکنید) هر کارت جدیدم با کارتای قبلی تو دست چپتون مقایسه میشه تا مکان درستش انتخاب بشه خب خیلی قلمبه سلمبه بود :| برای توضیح طرز کار این الگوریتم اول به شکل نگاه کنیدالان میایم ۵ رو با ۸ مقایسه میکنیم خب ۵ کوچیک تره پس جاش باهاش عوض میشه الان ۵و ۸ شدن یه دسته که مرتب شدن . حالا میایم ۳ رو با دسته ۵ و ۸ مقایسه میکنیم و توی جای درست بین اون دسته درج میشه الان ۳ و۵و۸ باهم شدن یه دسته مرتب شده . حالا میایم ۲۱ به این دسته مقایسه میکنیم که ۲۱توی جای درستشه پس به دسته اضافه میشه و همین طور تا به اخر ادامه میدیمشبه کد :INSERTION-SORT(A)for j = 2 to A.lengthkey = A[j]// Insert A[j] to into the sortedsequence A[1..j-1]i = j - 1while i>0 and A[i] > keyA[i+1] = A[i]i = i-1A[i+1] = keyکد الگوریتم:def insertion_sort(array):for i in range(1, len(array)):value = array[i]j = i - 1while j >= 0 and value < array[j]:array[j + 1] = array[j]j -= 1array[j + 1] = valuereturn arrayاین الگوریتم برای مجموعه داده‌های بزرگ مناسب نیست . پیچیدگی حالت میانگین و بدترین حالت آن برابر با (Ο(n2 است .مرتب سازی انتخابی(selection sort):میگردیم کوچیک ترین عنصر میزاریم مکان اول دوباره کوچیک ترین پیدا میکنیم میزاریم مکان دوم تا به اخر.به ازای n عنصر n-1 مرحله داریم.شبه کد :void selectionsort(int,arr[],int n){int i,jm;for(i=0;i<n-1;i++){m=i;for(j=i+1;j<n;j++)if(arr[j]<arr[m])m=i;swap(&arr[m],&arr[i]);}} کد الگوریتم :for i in range(len(A)):# Find the minimum element in remaining# unsorted arraymin_idx = ifor j in range(i+1, len(A)):if A[min_idx] > A[j]:min_idx = j# Swap the found minimum element with# the first elementA[i], A[min_idx] = A[min_idx], A[i]# Driver code to test aboveprint (&quotSorted array&quot)for i in range(len(A)):print(&quot%d&quot %A[i]),این الگوریتم برای مجموعه داده‌های بزرگ مناسب نیست . پیچیدگی ان در حالت متوسط و بدترین حالت آن برابر با (Ο(n2 است .مرتب سازی ادغامی (merge sort):مرتب‌سازی ادغامی بر مبنای الگوریتم حل مسئله «تقسیم و حل» عمل می‌کند. یک ارایه نامرتب را در نظر می‌گیریم . در مرتب‌سازی ادغامی اول کل آرایه را به ۲ نیمه تقسیم میکنیم و بعد نیمه هارو دوباره به ۲ قسمت تقسیم میکنیم تا جایی که نشه تقسیم کرد. حالا این نیمه ها رو به صورت مرتب به همان روشی که تقسیم کردیم، با هم ترکیب می‌کنیم.شبه کد :MERGE-SORT(A,p,r)1 if p<r2 q = (p+r)/23 MERGE-SORT(A,p,q)4 MERGE-SORT(A,p+1,r)5 MERGE(A,p,q,r)کد الگوریتم :def mergeSort(arr):if len(arr) > 1:# Finding the mid of the arraymid = len(arr)//2# Dividing the array elementsL = arr[:mid]# into 2 halvesR = arr[mid:]# Sorting the first halfmergeSort(L)# Sorting the second halfmergeSort(R)i = j = k = 0# Copy data to temp arrays L[] and R[]while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1# Checking if any element was leftwhile i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1# Code to print the listdef printList(arr):for i in range(len(arr)):print(arr[i], end=&quot &quot)print()# Driver Codeif __name__ == '__main__':arr = [12, 11, 13, 5, 6, 7]print(&quotGiven array is&quot, end=&quot\n&quot)printList(arr)mergeSort(arr)print(&quotSorted array is: &quot, end=&quot\n&quot)printList(arr)پیچیدگی بدترین حالت برای این الگوریتم برابر با (Ο(n log n است و خب نسبت به بقیه خب خیلی بهتره :)امیدوارم زیاد خسته کننده نبوده باشه و خوب توضیح داده شده باشهراستی بیشتر کدارم از اینجا برداشتم .