""" CS101 Sorting Examples """ import random import time import matplotlib.pyplot as plt def selection_sort(L): """ Sort list in place using the selection sort algorithm Args: L : List to sort in place """ # In each iteration, find the next smallest element in the list # and swap it into the appropriate place for i in range(len(L)): # Find the index of the smallest value from i onwards min_index = i min_value = L[i] for j in range(i+1, len(L)): if L[j] < min_value: min_index = j min_value = L[j] # Swap i and min_index L[i], L[min_index] = L[min_index], L[i] def insertion_sort(L): """ Sort list in place using the insertion sort algorithm Args: L : List to sort in place """ for i in range(1,len(L)): # Values at 0...i-1 are sorted already # Shift up all values in 0...i-1 greater than L[i] value = L[i] index = i while index > 0 and L[index-1] > value: L[index] = L[index-1] index -= 1 # Now insert value (old L[i]) in its proper place L[index] = value # Now everything from 0...i is sorted def merge_sort(L): """ Sort list using the merge sort algorithm returning a new sorted list. Args: L: List to sort Returns: New sorted list """ if len(L) <= 1: # Base case: List with single value is already sorted return L else: # Recursive case: Split list in half, sort each half then merge # the resulting lists mid_index = len(L) // 2 left = merge_sort(L[:mid_index]) right = merge_sort(L[mid_index:]) #print("Left: ", left) #print("Right: ", right) merged = merge(left, right) #print("Merged: ", merged) return merged def merge(list1, list2): """ Return a sorted list produced from merging two sorted lists Args: list1, list2: Sorted lists to merge Returns: Sorted, merged, list """ result = [] index1 = 0 index2 = 0 # Iterate each of the lists an item at a time while index1 < len(list1) and index2 < len(list2): if list1[index1] < list2[index2]: # If the current item in list1 is smaller, copy # and advance current item in list1 result.append(list1[index1]) index1 += 1 else: # Otherwise, do the same in list2 result.append(list2[index2]) index2 += 1 # Append any remaining elements in list1 or list2. Only one of these lists # should have any remaining elements, the other slicing operation # will produce an empty list result += list1[index1:] result += list2[index2:] return result """ Sample code to run: a = list(range(8)) random.shuffle(a) a selection_sort(a) insertion_sort(a) merge_sort(a) """ def time_sort(size, sort_function): """ Invoke and time sort_function on random data of length size Args: size: Size of random test data to generate sort_function: Sorting function to invoke Returns: Time required to sort """ # get some random data data = list(range(size)) random.shuffle(data) start = time.time() sort_function(data) return time.time()-start def compare_sorting(): """ Generate plot of runtime for selection sort, merge sort and built-in sort """ sel = [] mer = [] blt = [] sizes = range(500, 10000, 500); for size in sizes: sel.append(time_sort(size, selection_sort)) mer.append(time_sort(size, merge_sort)) blt.append(time_sort(size, sorted)) print("N = %4d, select.: %4.2fs, merge: %4.3fs, sorted: %4.3fs" % (size, sel[-1], mer[-1], blt[-1])) plt.plot(sizes, sel, label="Selection") plt.plot(sizes, mer, label="Merge") plt.plot(sizes, blt, label="sorted built-in") plt.xlabel("List size") plt.ylabel("Sorting time in seconds") plt.title("Timing sorting algorithms") plt.legend(loc='upper left') plt.show() """ To run: compare_sorting() """