Bubble Sort
1
2
3
4
5
6
7
8
9
def bubble_sort(arr=[4, 9, 2, 5, 7]):
for i in range(1, len(arr)):
for j in range(1, len(arr)):
if arr[j-1] > arr[j]:
arr[j-1], arr[j] = arr[j], arr[j-1]
return arr
print("bubble sort:", bubble_sort())
1
bubble sort: [2, 4, 5, 7, 9]
Selection Sort
1
2
3
4
5
6
7
8
9
def selection_sort(arr=[8, 4, 7, 2, 3]):
for i in range(0, len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
arr[i], arr[j] = arr[j], arr[i]
return arr
print("selection sort:", selection_sort())
1
selection sort: [2, 3, 4, 7, 8]
Insertion Sort
1
2
3
4
5
6
7
8
9
10
11
12
def insertion_sort(arr=[8, 9, 3, 1, 6]):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
return arr
print("insertion sort:", insertion_sort())
1
insertion sort: [1, 3, 6, 8, 9]
Shell Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def gap_insertion_sort(arr, start, gap):
for target in range(start+gap, len(arr), gap):
val = arr[target]
idx = target
while idx > start:
if arr[idx-gap] > val:
arr[idx] = arr[idx-gap]
else:
break
idx -= gap
arr[idx] = val
def shell_sort(arr=[8, 4, 2, 3, 7]):
gap = len(arr)//2
while gap > 0:
for start in range(0, gap):
gap_insertion_sort(arr, start, gap)
gap = gap//2
return arr
print("shell sort:", shell_sort())
1
shell sort: [2, 3, 4, 7, 8]
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
def merge_sort(arr=[3, 2, 5, 9, 6]):
if len(arr) > 1:
mid = len(arr)//2
larr, rarr = arr[:mid], arr[mid:]
merge_sort(larr); merge_sort(rarr)
li, ri, i = 0, 0, 0
while li < len(larr) and ri < len(rarr):
if larr[li] < rarr[ri]:
arr[i] = larr[li]
li += 1
else:
arr[i] = rarr[ri]
ri += 1
i += 1
if li != len(larr):
arr[i:] = larr[li:]
else:
arr[i:] = rarr[ri:]
return arr
print("merge sort:", merge_sort())
1
merge sort: [2, 3, 5, 6, 9]
Quick Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def quick_sort(arr=[8, 1, 7, 2, 5]):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
larr, rarr, marr = [], [], []
for i in range(0, len(arr)):
if arr[i] < pivot:
larr.append(arr[i])
elif arr[i] > pivot:
rarr.append(arr[i])
elif arr[i] == pivot:
marr.append(arr[i])
return quick_sort(larr)+marr+quick_sort(rarr)
print("quick sort:", quick_sort())
1
quick sort: [1, 2, 5, 7, 8]