Review Common Sorting Algorithms

• Bubble Sort: Time $O(n^2)$; Space $O(1)$
• Selection Sort: Time $O(n^2)$; Space $O(1)$
• Insert Sort: Time $O(n^2)$; Space $O(1)$
• Merge Sort: Time $O(n\log n)$; Space $O(n)$
• Quick Sort Time $O(n\log n)$; Space $O(\log n)$

arr0 = [12, 11, 6, 100, 21, 1, 1, -1, 0, 100]
print(f"Sorted array: {sorted(arr0)}")
print(f"Unsorted array: {arr0}")

Sorted array: [-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]
Unsorted array: [12, 11, 6, 100, 21, 1, 1, -1, 0, 100]

Bubble Sort

• Idea: Repeatedly swap adjacent elements if they are in the wrong order.
• Time Complexity: $O(n^2)$
• Space: $O(1)$
• Notes: Rarely used in practice; mainly for learning purposes.

def bubble_sort(arr):
    n = len(arr)    
    # travel through all elements
    for i in range(n):
        for j in range(n-i-1):
            # move the larger one to the right
            # at the end, the last element is the largest among arr[:(n-i)]
            if arr[j] > arr[j+1]:
                arr[j+1], arr[j] = arr[j], arr[j+1]
    print(arr)

arr = arr0.copy()
bubble_sort(arr)

[-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]

Selection Sort

• Idea: Repeatedly find the minimum element and place it at the beginning.
• Time Complexity:$O(n^2)$
• Space Complexity: $O(1)$
• Notes: Simple, but inefficient for large datasets.

def selection_sort(arr):
    n = len(arr)
    # travel through all elements
    for i in range(n):
        for j in range(i+1, n):
            # find the smallest element
            # at the end, the left element is the smallest among arr[(i+1):]
            if arr[i] > arr[j]:
                arr[i], arr[j] = arr[j], arr[i]
    print(arr)

arr = arr0.copy()
selection_sort(arr)

[-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]

Insertion Sort

• Idea: Build the sorted array one element at a time by placing elements in their correct position.
• Time Complexity: $O(n^2)$
• Space Complexity: $O(1)$
• Notes: Efficient for small or nearly sorted datasets.

def insertion_sort(arr):
    n = len(arr)
    # travel through all elements
    for i in range(n):
        ele = arr[i]
        j = i - 1
        # From right to left, move elements of arr[:(i-1)] that are greater than ele
        # to one position ahead of their current position
        # e.g., arr[i] = arr[i-1] if arr[i-1] > ele
        while j >= 0 and arr[j] > ele:
            arr[j+1] = arr[j]
            j -= 1
        # Once we found arr[j] <= ele, we assign ele to its right
        # Edge condition: j = -1, we assgin arr[0] = ele
        arr[j+1] = ele
    print(arr)

arr = arr0.copy()
insertion_sort(arr)

[-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]

Merge Sort

• Idea: Divide the array into halves, sort each half, and merge them.
• Time Complexity: $O(n\log n)$
• Space Complexity:$O(n)$
• Notes: Excellent for linked lists and large datasets.

def _merge(arr, left, mid, right):
    n1 = mid - left + 1
    n2 = right - mid
    
    # Copy two sorted subarrays L[] and R[]
    L = arr[left: (mid+1)]
    R = arr[(mid+1): (right+1)]

    # Merge L and R into a single array from index k = left to k = right
    # At each k, compare the left element of L and R that are not used yet
    # If say L[i] < R[j], we know L[i] < R[l] for all l > j because R is sorted
    # Hence, we can safely take L[i] and only need to compare L[i+1] with R[j]
    i, j, k = 0, 0, left
    while i < n1 and j < n2:
        if L[i] < R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1        

    # Copy the remaining elements of L if there are any.
    # e.g., if R[n2] <= L[i], then L[(i+1):] is appended at the end of the merged arr 
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R if there are any
    # e.g., if L[n1] < R[j], then R[(j+1):] is appended at the end of the merged arr 
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
        
def _merge_sort(arr, left, right):
    if left < right:
        mid = (left + right) // 2

        _merge_sort(arr, left, mid) # sort the left-side
        _merge_sort(arr, mid+1, right) # sort the right
        _merge(arr, left, mid, right) # merge the subarrays

def merge_sort(arr):
    _merge_sort(arr, 0, len(arr)-1)
    print(arr)

arr = arr0.copy()
merge_sort(arr)

[-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]

Quick Sort

• Idea: Choose a pivot, partition the array, and sort partitions recursively.
• Time Complexity: Worst $O(n^2)$; Best/Average: $O(n\log n)$
• Space: $O(\log n)$
• Notes: Often the default sorting algorithm due to its speed.

def _partition(arr, low, high):
    # Choose the pivot
    pivot = arr[high]    
    # Index of smaller element and indicates the right position of pivot found so far
    i = low - 1    
    # Traverse arr[low:high] and move all smaller elements to the left side. 
    # Elements from low to i are smaller after every iteration
    for j in range(low, high):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    # Move pivot after smaller elements and return its position
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

def _quickSort(arr, low, high):
    if low < high:
        # pi is the partition return index of pivot
        pi = _partition(arr, low, high)
        # Recursion calls for smaller elements
        _quickSort(arr, low, pi - 1)
        # Recursion calls for greater or equals elements
        _quickSort(arr, pi + 1, high)

def quick_sort(arr):
    _quickSort(arr, 0, len(arr)-1)
    print(arr)
    
arr = arr0.copy()
quick_sort(arr)

[-1, 0, 1, 1, 6, 11, 12, 21, 100, 100]