Sorting Algorithms Part 2: Code Examples (3 Part Series)

In part 1 of this series we took a look at some types of sorting algorithms. In this part let’s take each one of those and look at code examples in python on how to implement them.

---

Bubble Sort

def bubbleSort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Selection Sort

def selectionSort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Insertion Sort

def insertionSort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i-1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Merge Sort

def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]
        
        mergeSort(L)
        mergeSort(R)
        
        i = j = k = 0
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1
        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

Quick Sort

def quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi-1)
        quickSort(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]
    i = (low-1)
    for j in range(low, high):
        if arr[j] <= pivot:
            i = i+1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return (i+1)

Heap Sort

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[i] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

Radix Sort

def countingSort(arr, exp1):
    n = len(arr)
    output = [0] * (n)
    count = [0] * (10)
    for i in range(0, n):
        index = (arr[i] / exp1)
        count[int(index % 10)] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    i = n - 1
    while i >= 0:
        index = (arr[i] / exp1)
        output[count[int(index % 10)] - 1] = arr[i]
        count[int(index % 10)] -= 1
        i -= 1
    for i in range(0, len(arr)):
        arr[i] = output[i]

def radixSort(arr):
    max1 = max(arr)
    exp = 1
    while max1 / exp > 0:
        countingSort(arr, exp)
        exp *= 10

---

Sample Data and Testing

1. Random Data:
   • arr_random = [64, 34, 25, 12, 22, 11, 90]
2. Sorted Data (to test best-case scenarios for some algorithms):
   • arr_sorted = [11, 22, 25, 34, 64, 90]
3. Reverse Sorted Data (to test worst-case scenarios for some algorithms):
   • arr_reverse_sorted = [90, 64, 34, 25, 22, 11]
4. Data with Duplicate Values:
   • arr_duplicates = [64, 34, 25, 12, 22, 12, 90, 64]
5. Single Element Data:
   • arr_single = [64]
6. Empty Data:
   • arr_empty = []

Here’s an example of how you can test the bubbleSort function using the arr_random sample data:

arr_random = [64, 34, 25, 12, 22, 11, 90]
bubbleSort(arr_random)
print("Sorted array:", arr_random)

You can similarly test the rest of the sorting functions with the provided sample data. Some sorting functions might require additional parameters, such as low and high for quickSort, so ensure you’re providing the correct arguments when testing.

---

While these code examples provide a basic introduction, further optimizations and refinements can be applied to each algorithm to cater to specific use cases or to enhance performance.

In tomorrow’s post (Part 3) we will wrap up this series with a discussion on determining the efficiency of each algorithm.