یکم الگوریتم

تو این مطلب میخوایم خیلی خلاصه چندتا از الگوریتم های مرتب سازی و باهم ببینیم

الگوریتم های مرتب سازی و بر اساس نحوه مرتب سازی به ۲ دسته میشه تقسیم کرد

• مبتی بر مقایسه : با مقایسه بین کلید های عناصر ترتیب پیدا میشه

مثل مرتب سازی های : حبابی - انتخابی - درجی - ادغامی - سریع - هیپ - درختی - شل

• غیرمقایسه ای (خطی):بدون مقایسه کلیدهای عناصر باهم مرتب سازی انجام میشه

مثل مرتب سازی های : شمارشی - مبنایی - سطلی - لانه کبوتری

خب شروع میکنیم روش کار چندتا از این الگوریتم هارو ببینیم :)

مرتب سازی حبابی (Bubble sort):

یه ارایه نامرتب و بهش میدیم بعد توی طول ارایه حرکت میکنیم و یک عنصر را با عنصر مجاورش با هم مقایسه میکنیم و اگه تو ترتیبی که میخوایم مرتب کنیم نباشن میایم جاشونو با هم عوض میکنیم

شبه کد این الگوریتم

BUBBLESORT(A):

for i = 1 to A.length-1

for j = A.length downto i + 1

if 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] = temp

return array

این الگوریتم برای مجموعه داده‌های بزرگ مناسب نیست . پیچیدگی حالت میانگین و بدترین حالت آن برابر با (Ο(n2 است .

مرتب سازی درجی (insertion sort):

شما میتونید مثل یه بازی کارت در نظر بگیرید به این صورت که درست چپتون خالیه کارتارو یکی یکی بر میدارین میزارین تو مکان درست تو دست چپتون (درج میکنید) هر کارت جدیدم با کارتای قبلی تو دست چپتون مقایسه میشه تا مکان درستش انتخاب بشه خب خیلی قلمبه سلمبه بود :| برای توضیح طرز کار این الگوریتم اول به شکل نگاه کنید

الان میایم ۵ رو با ۸ مقایسه میکنیم خب ۵ کوچیک تره پس جاش باهاش عوض میشه الان ۵و ۸ شدن یه دسته که مرتب شدن . حالا میایم ۳ رو با دسته ۵ و ۸ مقایسه میکنیم و توی جای درست بین اون دسته درج میشه الان ۳ و۵و۸ باهم شدن یه دسته مرتب شده . حالا میایم ۲۱ به این دسته مقایسه میکنیم که ۲۱توی جای درستشه پس به دسته اضافه میشه و همین طور تا به اخر ادامه میدیم

شبه کد :

INSERTION-SORT(A)

for j = 2 to A.length

key = A[j]

// Insert A[j] to into the sorted

sequence A[1..j-1]

i = j - 1

while i>0 and A[i] > key

A[i+1] = A[i]

i = i-1

A[i+1] = key

کد الگوریتم:

def insertion_sort(array):

for i in range(1, len(array)):

value = array[i]

j = i - 1

while j >= 0 and value < array[j]:

array[j + 1] = array[j]

j -= 1

array[j + 1] = value

return array

این الگوریتم برای مجموعه داده‌های بزرگ مناسب نیست . پیچیدگی حالت میانگین و بدترین حالت آن برابر با (Ο(n2 است .

مرتب سازی انتخابی(selection sort):

میگردیم کوچیک ترین عنصر میزاریم مکان اول دوباره کوچیک ترین پیدا میکنیم میزاریم مکان دوم تا به اخر.

به ازای n عنصر n-1 مرحله داریم.

شبه کد :

void selectionsort(int,arr[],int n){

int i,j

m;

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 array

min_idx = i

for j in range(i+1, len(A)):

if A[min_idx] > A[j]:

min_idx = j

# Swap the found minimum element with

# the first element

A[i], A[min_idx] = A[min_idx], A[i]

# Driver code to test above

print (&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<r

2 q = (p+r)/2

3 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 array

mid = len(arr)//2

# Dividing the array elements

L = arr[:mid]

# into 2 halves

R = arr[mid:]

# Sorting the first half

mergeSort(L)

# Sorting the second half

mergeSort(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 += 1

else:

arr[k] = R[j]

j += 1

k += 1

# Checking if any element was left

while i < len(L):

arr[k] = L[i]

i += 1

k += 1

while j < len(R):

arr[k] = R[j]

j += 1

k += 1

# Code to print the list

def printList(arr):

for i in range(len(arr)):

print(arr[i], end=&quot &quot)

print()

# Driver Code

if __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 است و خب نسبت به بقیه خب خیلی بهتره :)

امیدوارم زیاد خسته کننده نبوده باشه و خوب توضیح داده شده باشه

راستی بیشتر کدارم از اینجا برداشتم .