Sorting N numbers

In this article will be adding different ways to sort an array of n numbers and code snippets for each one of them. Idea with this post is to keep all the sorting methods with code snippets in one place, for comparison purpose.

Leetcode problem:

Sort an array

Decease & Conqure Strategies:#

Bubble Sort#

Time Complexity: O(N^2)
In Place
Stable

def sortArray(nums: List[int]) -> List[int]:
    # Bubble sort: Top down strategy, first do work then delegate.
    # Decease & Conqure: Bubble up the largest element in the N elements to N - 1 position, and then repeat the same process for N - 1 elements and N - 2 position.
    # BubbleSort(N) :=>  BubbleSort(N - 1) + [bubblemax(N)]
    n = len(nums)
    for i in range(1, n):
        for j in range(n - i):
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums

Selection Sort#

Time Complexity: O(N^2)
In Place
Not Stable: As swap of min element with left index can change the order of equal elements. Ex [3, 3, 3, 1]

def sortArray(nums: List[int]) -> List[int]:
        # Selection sort: Top down strategy, first do work then delegate.
        # Decease & Conqure: Select the min element out of N - i  elements for ith position, then do the same for i + 1 positon with N - i - 1 elements.
        # SeletionSort(N) :=> [min(N)] + SelectionSort(N - 1)
        n = len(nums)
        for i in range(n):
            lo = i
            for j in range(i, n):
                if nums[j] < nums[lo]:
                    lo = j
            nums[i], nums[lo] = nums[lo], nums[i]
        return nums

Insertion Sort#

Time Complexity: Worst & Average case: O(N^2), Best Case: Theta(N) (Array is already sorted.)
In place
Stable

def sortArray(nums: List[int]) -> List[int]:
    # Insertion sort: Bottom Up strategy, first delegate then do work.
    # Decease & Conqure: Assume first N - 1 elements are sorted already then insert the Nth element at the right place.
    # InsertionSort(N) :=> InsertionSort(N - 1) + Insert(N)
    n = len(nums)
    for i in range(n):
        # Move all greater elements to right and find the right position to insert ith element.
        j, tmp = i, nums[i]
        while j >= 1 and nums[j - 1] > tmp:
            nums[j] = nums[j - 1]
            j -= 1
        nums[j] = tmp
        # Using swap similar to bubble sort
        #for j in reversed(range(0, i)):
        #    if nums[j] > nums[j + 1]:
        #        nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

Divide & Conqure Strategies:#

Merge Sort#

Time Complexity O(N logN)
Uses O(N) auxilary space.
Stable

def sortArray(nums: List[int]) -> List[int]:
    # Merge Sort
    # Divide & Conqure: Divide the array in two equal parts, recursively sort them and merge the two parts to form sorted array.
    # MergeSort(N) = 2 * MergeSort(N/2) + Merge(N)
    def helper(lo, hi: int):
        if lo == hi:
            return
        mid = (lo + hi)//2
        helper(lo, mid)
        helper(mid + 1, hi)
        merge(lo, mid+1, hi)
    
    # Merge two sorted sections in an arry.
    # Sections from [start1..start2-1] & [start2..end2] index included.
    def merge(start1, start2, end2: int):
        # Copy one of the sub array in temporary store.
        tmp = nums[start1:start2]
        i, j, k = 0, start2, start1
        while i < len(tmp) and j <= end2:
            if tmp[i] <= nums[j]:
                nums[k] = tmp[i]
                i += 1
            else:
                nums[k] = nums[j]
                j += 1
            k += 1
        while i < len(tmp):
            nums[k] = tmp[i]
            i += 1
            k += 1
        while j <= end2:
            nums[k] = nums[j]
            j += 1
            k += 1
    
    helper(0, len(nums) - 1)
    return nums

TimSort#

Time Complexity O(N logN)
Uses O(N) auxilary space.
Stable

Combination of mergeSort and insertionSort where, if the number of elements are small in subarray do insertion sort otherwise do merge sort on the array. Used in python sort() implementation. Includes clever ways to divide the array into smaller sorted subarrays.

QuickSort#

Time Complexity Best & Average O(N logN), Worst case O(N^2)
In place; Extra stack space O(N) worst case.
Not Stable; Partitioning breaks the stability

def sortArray(nums: List[int]) -> List[int]:
    # quickSort
    def helper(lo, hi: int):
        if lo >= hi:
            return
        pivot = partition(lo, hi)
        # Pivot should not be part of the remaining recursive call.
        helper(lo, pivot - 1)
        helper(pivot + 1, hi)
    
    # Partition is based on Lomuto algorithm, listed in the other article I posted for array partitions.
    # Important differnce is pivot should be placed back at the right position after the partition.
    def partition(lo, hi: int):
        pi, pivot = lo, random.randint(lo, hi) # Randomly select pivot index.
        nums[hi], nums[pivot] = nums[pivot], nums[hi] # move the pivot out of the elements to partition either to start or end.
        for i in range(lo, hi):
            if nums[i] <= nums[hi]: # If less than and equal to pivot, move to the left of the partition.
                nums[i], nums[pi] = nums[pi], nums[i]
                pi += 1
        nums[hi], nums[pi] = nums[pi], nums[hi] # move the pivot back to where the partition is done.
        return pi # Return the index of the pivot.
    
    helper(0, len(nums) - 1)
    return nums

Transform & Conqure Strategies:#

Heap Sort#

Time Complexity: O(N logN)
In place; Can be made in-place, by using a max heap and appending the extracted max at the end of the array.
Not Stable; heapify breaks the order of the equal ordered elements.

def sortArray(nums: List[int]) -> List[int]:
    # heapSort
    heapq.heapify(nums) # O(N) operation
    sol = []
    for i in range(len(nums)):
        sol.append(heapq.heappop(nums)) # Each extract min operation over heap is : O(logN)
    return sol