import numpy as np

import matplotlib.pyplot as plt
%matplotlib inline

# My personal Python routines

from lib.compsci.algorithms import sorting

Empirically comparing the time complexities of Selection Sort and Quicksort

# The instrumented array structure the the sorting algorithms will be sorting on.
class InstrumentedArray:
    def __init__(self, arr):
        self.arr = arr
        self.num_comparisons = 0
        self.num_swaps = 0

    # BEGIN interface for sorting
    
    def len(self):
        return len(self.arr)

    def less(self, i, j):
        self.num_comparisons += 1
        return self.arr[i] < self.arr[j]

    def swap(self, i, j):
        self.num_swaps += 1
        self.arr[i], self.arr[j] = self.arr[j], self.arr[i]
        
    # END interface for sorting

    def stats(self):
        return {
            'comparisons': self.num_comparisons,
            'swaps': self.num_swaps,
        }

def empty_stats():
    return {
        'comparisons': [],
        'swaps': [],
    }

selection_sort_stats = empty_stats()
quicksort_stats = empty_stats()

Test the sorting algorithms on randomly generated lists of integers of different sizes

def _append_stats(acc, x):
    for key, x in x.items():
        acc[key].append(x)

N = range(10, 1000, 10)

for size in N:
    arr = np.random.randint(0, 100, size=size)
    
    a = InstrumentedArray(arr.copy())
    sorting.selection_sort(a)
    assert sorting.is_sorted(a.arr)
    _append_stats(selection_sort_stats, a.stats())
    
    a = InstrumentedArray(arr.copy())
    sorting.quicksort(a)
    assert sorting.is_sorted(a.arr)
    _append_stats(quicksort_stats, a.stats())

Result

The number of ops between comparison and swap

fig = plt.figure()
ax1 = fig.add_subplot(211)

ax1.set_title('Selection Sort')
ax1.plot(N, selection_sort_stats['comparisons'], label='comparisons')
ax1.plot(N, selection_sort_stats['swaps'], label='swaps')
ax1.legend()

ax2 = fig.add_subplot(212)
ax2.set_title('Quicksort')
ax2.plot(N, quicksort_stats['comparisons'], label='comparisons')
ax2.plot(N, quicksort_stats['swaps'], label='swaps')
ax2.legend()

plt.tight_layout()

• Selection sort - The comparisons dominate the number of ops and can be seen increasing quadratically. For selection sort, The number of ops is a function of N.
• Quicksort - The comparison and swap ops are comparable. The time complexity is close to linear.

Comparing comparison ops

plt.title('Number of comparison ops')
plt.plot(selection_sort_stats['comparisons'], label='selection sort')
plt.plot(quicksort_stats['comparisons'], label='quicksort')
plt.legend()
plt.show()

Comparing swap ops

plt.title('Number of swap ops')
plt.plot(selection_sort_stats['swaps'], label='selection sort')
plt.plot(quicksort_stats['swaps'], label='quicksort')
plt.legend()
plt.show()

Quicksort performs more swap operations than selection sort.