Sort Algorithms
1. Bubble Sort
- Definition: A sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.
- Time Complexity: O(n²).
Non-Optimized Bubble Sort
def bubble_sort(A):
n = len(A)
for i in range(n):
for j in range(n-1):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
return A
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(bubble_sort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
Optimized Bubble Sort
def bubble_sort(A):
n = len(A)
for i in range(n):
swapped = False
for j in range(n-1):
if A[j] > A[j+1]:
A[j], A[j+1] = A[j+1], A[j]
swapped = True
if not swapped: # no swaps -> already sorted
break
return A
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(bubble_sort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
2. Insertion Sort
- Definition: A sorting algorithm that builds the sorted list one element at a time by inserting elements into their correct positions.
- Time Complexity: O(n²).
Insertion Sort With key
def insertion_sort(A):
for i in range(1, len(A)):
key = A[i]
j = i - 1
while j >= 0 and key < A[j]:
A[j+1] = A[j]
j -= 1
A[j+1] = key
return A
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(insertion_sort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
Alternative Insertion Sort
def insertion_sort(A):
for i in range(1, len(A)):
j = i
while A[j-1] > A[j] and j > 0:
A[j-1], A[j] = A[j], A[j-1]
j -= 1
return A
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(insertion_sort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
3. Quick Sort
- Definition: A divide-and-conquer algorithm that selects a pivot and partitions the list into smaller and larger elements, then recursively sorts the sublists.
- Time Complexity: O(n log n) on average.
With List Comprehension
def quicksort(A):
if len(A) <= 1:
return A
pivot = A[len(A) // 2]
left = [x for x in A if x < pivot]
middle = [x for x in A if x == pivot]
right = [x for x in A if x > pivot]
return quicksort(left) + middle + quicksort(right)
# main
data = [4, 7, 1, 5, 2, 8, 3]
print(quicksort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
Without List Comprehension
def quicksort(A):
if len(A) <= 1: # terminating cases (0 or 1 item)
return A
pivot = A[len(A) // 2] # midpoint
left = []
middle = []
right = []
for element in A:
if element < pivot:
left.append(element)
elif element == pivot:
middle.append(element)
else:
right.append(element)
return quicksort(left) + middle + quicksort(right) # recursive cases
# main
data = [4, 7, 1, 5, 2, 8, 3]
print(quicksort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
Without List Comprehension Simplified
def quicksort(A):
if len(A) <= 1: # terminating cases (0 or 1 item)
return A
pivot = A[len(A) // 2] # midpoint
left = [] # items less than pivot
right = [] # items more than pivot
for element in A:
if element < pivot:
left.append(element)
elif element > pivot:
right.append(element)
return quicksort(left) + [pivot] + quicksort(right) # recursive cases
# main
data = [4, 7, 1, 5, 2, 8, 3]
print(quicksort(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
4. Merge Sort
- Definition: A divide-and-conquer algorithm that splits the list into halves, sorts each half, and merges them.
- Time Complexity: O(n log n).
Iterative Merge Sort
def merge_sorti(A):
n = len(A)
if n <= 1:
return A
left = merge_sorti(A[:n//2])
right = merge_sorti(A[n//2:])
i = j = k = 0
sorted_list = [None] * n
while i < len(left) and j < len(right):
if left[i] < right[j]:
sorted_list[k] = left[i]
i += 1
else:
sorted_list[k] = right[j]
j += 1
k += 1
while i < len(left):
sorted_list[k] = left[i]
i += 1
k += 1
while j < len(right):
sorted_list[k] = right[j]
j += 1
k += 1
return sorted_list
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(merge_sorti(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]
Recursive Merge Sort
def merge_sortr(A):
if len(A) <= 1:
return A
mid = len(A) // 2
left = merge_sortr(A[:mid])
right = merge_sortr(A[mid:])
return merge(left, right)
def merge(left, right):
merged_list = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
merged_list.append(left[i])
i += 1
else:
merged_list.append(right[j])
j += 1
merged_list += left[i:]
merged_list += right[j:]
return merged_list
# main
data = [4, 7, 1, 5, 2, 8, 3, 6]
print(merge_sortr(data))
---------------------------------------
[1, 2, 3, 4, 5, 6, 7, 8]