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)