What is Sorting?
Sorting refers to the process of arranging data in a specific order, typically in ascending or descending order, based on a linear relationship among the data items.
Why Do We Need Sorting?
Sorting is crucial when working with structured data because it allows for efficient data retrieval, simplifies data analysis, and enhances overall data management.
Sorting Algorithms
This post covers the following sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quick Sort.
Bubble Sort
Bubble Sort repeatedly steps through the array, comparing adjacent elements and swapping them if they are in the wrong order. This process continues until the array is sorted, with larger elements "bubbling" to the end.
Algorithm
Step 1: Begin
Step 2: i = 0
Step 3: if i < length(array) - 1, goto Step 4; else goto Step 10
Step 4: j = 0
Step 5: if j < length(array) - i - 1, goto Step 6; else goto Step 3
Step 6: if array[j] > array[j + 1], goto Step 7; else goto Step 8
Step 7: Swap array[j] and array[j + 1]
Step 8: increment j; goto Step 5
Step 9: increment i; goto Step 3
Step 10: End
Code
def bubble_sort(arr):
print("Array Before Sorting: ", end='')
print(arr)
for i in range(len(arr)):
for j in range(len(arr)-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
print("Array After Sorting: ", end='')
print(arr)
# Main
bubble_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
Time Complexity
Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)
Selection Sort
Selection Sort finds the smallest value in the unsorted portion of the array and places it at the beginning of that portion.
Algorithm
Step 1 : Begin
Step 2 : i = 0
Step 3 : if i < length(array) - 1, goto Step 4; else goto Step 10
Step 4 : minimum_value = i; j = i + 1
Step 5 : if j < length(array), goto Step 6; else goto Step 9
Step 6 : if array[minimum_value] > array[j], goto Step 7; else goto Step 8
Step 7 : minimum_value = j
Step 8 : increment j; goto Step 5
Step 9 : swap array[minimum_value] and array[i]
Step 10 : increment i; goto Step 3
Step 11 : End
Code
def selection_sort(arr):
print("Array Before Sorting: ", end='')
print(arr)
for i in range(len(arr) - 1):
min_val = i
for j in range(i + 1, len(arr)):
if arr[j] < arr[min_val]:
min_val = j
arr[i], arr[min_val] = arr[min_val], arr[i]
print("Array After Sorting: ", end='')
print(arr)
# Main
selection_sort([7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6])
Time Complexity
Best Case : O(n^2)
Average Case : O(n^2)
Worst Case : O(n^2)
Insertion Sort
Insertion Sort builds the sorted array one element at a time by taking each element from the unsorted portion and inserting it into the correct position in the sorted portion.
Algorithm
Step 1: Begin
Step 2: i = 1
Step 3: if i < len(arr), goto Step 4; else goto Step 12
Step 4: key = arr[i]
Step 5: j = i - 1
Step 6: if j >= 0 and arr[j] > key, goto Step 7; else goto Step 10
Step 7: arr[j + 1] = arr[j]
Step 8: decrement j by 1
Step 9: goto Step 6
Step 10: arr[j + 1] = key
Step 11: increment i by 1; goto Step 3
Step 12: End
Code
def insertion_sort(arr):
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
# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
insertion_sort(arr)
print("Array After Sorting:", arr)
Time Complexity
Best Case : O(n)
Average Case : O(n^2)
Worst Case : O(n^2)
Merge Sort
Merge Sort is a divide-and-conquer algorithm that recursively divides the array into smaller sub-arrays, sorts them, and then merges them back together.
Algorithm
Merge Sort Algorithm
Step 1: Begin
Step 2: If length(array) <= 1, Return array; goto Step 9
Step 3: mid_point = length(array) // 2
Step 4: left_half = array[:mid_point]
Step 5: right_half = array[mid_point:]
Step 6: sorted_left = merge_sort(left_half)
Step 7: sorted_right = merge_sort(right_half)
Step 8: return merge(sorted_left, sorted_right)
Step 9: End
Merge Function
Step 1: Begin
Step 2: sorted_merge = []
Step 3: l = 0, r = 0
Step 4: if l < len(left) and r < len(right), goto Step 5; else goto Step 9
Step 5: if left[l] <= right[r], goto Step 6; else goto Step 7
Step 6: add left[l] to sorted_merge; increment l by 1
Step 7: add right[r] to sorted_merge; increment r by 1
Step 8: goto Step 4
Step 9: if l < len(left), goto Step 10; else goto Step 12
Step 10: add left[l] to sorted_merge; increment l by 1
Step 11: goto Step 9
Step 12: if r < len(right), goto Step 13; else goto Step 15
Step 13: add right[r] to sorted_merge; increment r by 1
Step 14: goto Step 12
Step 15: Return sorted_merge
Step 16: End
Code
def merge(left, right):
sorted_merge = []
l = r = 0
while l < len(left) and r < len(right):
if left[l] <= right[r]:
sorted_merge.append(left[l])
l += 1
else:
sorted_merge.append(right[r])
r += 1
while l < len(left):
sorted_merge.append(left[l])
l += 1
while r < len(right):
sorted_merge.append(right[r])
r += 1
return sorted_merge
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid_point = len(arr) // 2
left_half = arr[:mid_point]
right_half = arr[mid_point:]
sorted_left = merge_sort(left_half)
sorted_right = merge_sort(right_half)
return merge(sorted_left, sorted_right)
# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
arr = merge_sort(arr)
print("Array After Sorting:", arr)
Time Complexity
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n log n)
Quick Sort
Quick Sort is an efficient, in-place sorting algorithm that uses a divide-and-conquer approach. It selects a pivot element and partitions the array around the pivot so that elements less than the pivot are on its left and elements greater than the pivot are on its right. This process is then recursively applied to the sub-arrays.
Algorithm
Quick Sort
Step 1: Begin
Step 2: If low < high, goto Step 3; else goto Step 6
Step 3: pivot_index = partition(arr, low, high)
Step 4: quicksort(arr, low, pivot_index - 1)
Step 5: quicksort(arr, pivot_index + 1, high)
Step 6: End
Partition Function
Step 1: Begin
Step 2: pivot = arr[high]
Step 3: left = low, right = high - 1
Step 4: if left <= right goto Step 5, else goto Step 9
Step 5: if arr[left] > pivot and arr[right] < pivot, swap arr[left] and arr[right]
Step 6: if arr[left] <= pivot, increment left
Step 7: if arr[right] >= pivot, decrement right
Step 8: goto Step 4
Step 9: swap arr[left] and arr[high]
Step 10: return left
Step 11: End
Code
def partition(arr, low, high):
pivot = arr[high]
left = low
right = high - 1
while left <= right:
if arr[left] > pivot and arr[right] < pivot:
arr[left], arr[right] = arr[right], arr[left]
if arr[left] <= pivot:
left += 1
if arr[right] >= pivot:
right -= 1
arr[left], arr[high] = arr[high], arr[left]
return left
def quicksort(arr, low, high):
if low < high:
pivot_index = partition(arr, low, high)
quicksort(arr, low, pivot_index - 1)
quicksort(arr, pivot_index + 1, high)
# Main
arr = [7, 4, 1, 3, 4, 7, 87, 9, 6, 4, 2, 2, 3, 5, 6]
print("Array Before Sorting:", arr)
quicksort(arr, 0, len(arr) - 1)
print("Array After Sorting:", arr)
Time Complexity
Best Case : O(n log n)
Average Case : O(n log n)
Worst Case : O(n^2)
Top comments (0)