‘A Basket of Sorting Algorithms’ Using Python

Photo by Soraya Irving on Unsplash

"Sorting" essentially refers to "sorting in ascending order", unless specified otherwise.

Sorting algorithms are capable of doing multiple and extraordinary things, imagine how much time it would take for a human to sort a list of thousands of names to make a phonebook, or a list of thousands of recipes, archives, animals, etc.

Let’s create a list of numbers to be sorted as an example !

nums: A list of numbers e.g. [4, 2, 6, 3, 4, 6, 2, 1]

1. Bubble Sort

It is called by this name because herein smaller elements to bubble to the top and larger to sink to the bottom.

The core operations in bubble sort are “compare” and “swap”.

def bubble_sort(nums):
    # Create a copy of the list, to avoid changing it
    nums = list(nums)
    
    # 4. Repeat the process n-1 times
    for _ in range(len(nums) - 1):
        
        # 1. Iterate over the array (except last element)
        for i in range(len(nums) - 1):
            
            # 2. Compare the number with  
            if nums[i] > nums[i+1]:
                
                # 3. Swap the two elements
                nums[i], nums[i+1] = nums[i+1], nums[i]
    
    # Return the sorted list
    return nums

2. Insertion Sort

Here we keep the initial portion of the array sorted and insert the remaining elements one by one at the right position.

def insertion_sort(nums):
    nums = list(nums)
    for i in range(len(nums)):
        cur = nums.pop(i)
        j = i-1
        while j >=0 and nums[j] > cur:
            j -= 1
        nums.insert(j+1, cur)
    return nums

For performing sorting more efficiently, a strategy called Divide and Conquer is applied, which has the following general steps:

1. Divide the inputs into two roughly equal parts.
2. Recursively solve the problem individually for each of the two parts.
3. Combine the results to solve the problem for the original inputs.
4. Include terminating conditions for small or indivisible inputs.

Visual representation of above strategy

3. Merge Sort

def merge_sort(nums):
    # Terminating condition (list of 0 or 1 elements)
    if len(nums) <= 1:
        return nums
    
    # Get the midpoint
    mid = len(nums) // 2
    
    # Split the list into two halves
    left = nums[:mid]
    right = nums[mid:]
    
    # Solve the problem for each half recursively
    left_sorted, right_sorted = merge_sort(left), merge_sort(right)
    
    # Combine the results of the two halves
    sorted_nums =  merge(left_sorted, right_sorted)
    
    return sorted_nums

Now, how to merge the two sorted arrays?

For this, we can repeatedly compare the two least elements of each array, and copy over the smaller one into a new array.

def merge(nums1, nums2):    
    # List to store the results 
    merged = []
    
    # Indices for iteration
    i, j = 0, 0
    
    # Loop over the two lists
    while i < len(nums1) and j < len(nums2):        
        
        # Include the smaller element in the result and move to next element
        if nums1[i] <= nums2[j]:
            merged.append(nums1[i])
            i += 1 
        else:
            merged.append(nums2[j])
            j += 1
    
    # Get the remaining parts
    nums1_tail = nums1[i:]
    nums2_tail = nums2[j:]
    
    # Return the final merged array
    return merged + nums1_tail + nums2_tail

4. Quick Sort

It is another divide-and-conquer based sorting algorithm, which works as follows:

1. If the list is empty or has just one element, return it. It’s already sorted.
2. Pick a random element from the list. This element is called a pivot.
3. Reorder the list so that all elements with values less than or equal to the pivot come before the pivot, while all elements with values greater than the pivot come after it. This operation is called partitioning.
4. The pivot element divides the array into two parts which can be sorted independently by making a recursive call to quicksort.

def quicksort(nums, start=0, end=None):
    # print('quicksort', nums, start, end)
    if end is None:
        nums = list(nums)
        end = len(nums) - 1
    
    if start < end:
        pivot = partition(nums, start, end)
        quicksort(nums, start, pivot-1)
        quicksort(nums, pivot+1, end)

    return nums

Here’s an implementation of partition, which uses the last element of the list as a pivot:

def partition(nums, start=0, end=None):
    # print('partition', nums, start, end)
    if end is None:
        end = len(nums) - 1
    
    # Initialize right and left pointers
    l, r = start, end-1
    
    # Iterate while they're apart
    while r > l:
        # print('  ', nums, l, r)
        # Increment left pointer if number is less or equal to pivot
        if nums[l] <= nums[end]:
            l += 1
        
        # Decrement right pointer if number is greater than pivot
        elif nums[r] > nums[end]:
            r -= 1
        
        # Two out-of-place elements found, swap them
        else:
            nums[l], nums[r] = nums[r], nums[l]
    # print('  ', nums, l, r)
    # Place the pivot between the two parts
    if nums[l] > nums[end]:
        nums[l], nums[end] = nums[end], nums[l]
        return l
    else:
        return end

The key observation here is that after the partition, the pivot element is at its right place in the sorted array, and the two parts of the array can be sorted independently in-place.

The efficiency of above algorithms summarized →

Thus, sorting algorithms are chosen based on the application and efficiency required for that application.