Verify complexity of selection sort using countop

In [2]:

    

from countop import Integer
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline


    

In [3]:

    

# Create a quick selection sort function
def selection_sort(x):
    n = len(x)
    if n == 0 or n == 1:
        return x
    
    for i in range(n - 1):
        # Find the minimum element in x[i, .. ,n - 1] manually
        imin = i
        for j in range(i + 1, n):
            if x[j] < x[imin]:
                imin = j
        
        # Replace x[i] with x[imin]
        temp = x[i]
        x[i] = x[imin]
        x[imin] = temp
    return x


    

In [4]:

    

# Basic sorting example
n = 10
x = [Integer(j) for j in range(n, 0, -1)]
Integer.reset_counts()
print 'Comparisons before sorting: {}'.format(Integer.comparisons())
selection_sort(x)
print 'Comparisons after sorting: {}'.format(Integer.comparisons())


    

    




Comparisons before sorting: 0
Comparisons after sorting: 45

In [5]:

    

# Basic max operation
Integer.reset_counts()
print 'Comparisons before sorting: {}'.format(Integer.comparisons())
print 'max(x) = {}'.format(max(x))
print 'Comparisons after sorting: {}'.format(Integer.comparisons())


    

    




Comparisons before sorting: 0
max(x) = 10
Comparisons after sorting: 9

In [6]:

    

# Obtain number of comparisons for various input sizes
exp_array = np.arange(0, 12, 1)
n_array = 2**exp_array
comp_array = np.zeros(len(n_array), int)
for i, n in enumerate(n_array):
    Integer.reset_counts()
    selection_sort([Integer(j) for j in range(n, 0, -1)])
    comp_array[i] = Integer.comparisons()


    

In [7]:

    

# Plot number of comparisons against input size
plt.figure(1)
plt.hold(True)
plt.plot(n_array, comp_array, 'o')
plt.plot(n_array, 0.5*n_array*n_array, 'k--')
plt.legend(('# Comparisons', '0.5 * n^2'))
plt.xlabel('Input size (n)')
plt.ylabel('Number of comparisons')
plt.title('Selection sort complexity')
plt.grid(True)