Sorting Algorithms in Python

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)