Implement algorithms for sorting

1. selection sort 2. insertion sort 3. shell sort 4. heap sort 5. merge sort 6. quick sort

Plot your running times for sorting 10^i objects where i= 1, 2, 3, 4, 5, 6.

What about plotting for i = 7, 8, 9?

Plot also python's sorted() function to see how well you do.

# 1. selection sort # 2. insertion sort # 3. shell sort # 4. heap sort # 5. merge sort # 6. quick sort import time import random #import matplotlib.pyplot as plt class Sorting(object): """Sorting class """ def __init__(self): self.id = [] def sort_init(self, N): """initialize the data structure """ try: self.id = random.sample(range(1, N ** 3), N) except ValueError: print('Sample size exceeded population size.') #self.id = [random.randint(0, N - 1) for i in range(N)] def get_id(self): """initialize the data structure """ return self.id def selection_sort(self): """Selection sort algorithm is an in-place comparison sort. It has O(n^2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort """ for i_idx, i_item in enumerate(self.id): min = i_idx for j_idx in range(i_idx+1, len(self.id)): if (self.id[j_idx] < self.id[min]): min = j_idx # swap temp = self.id[i_idx] self.id[i_idx] = self.id[min] self.id[min] = temp return self.id def insertion_sort(self): """Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. More efficient in practice than most other simple quadratic (i.e., O(n^2)) algorithms such as selection sort or bubble sort specifically an """ return 1 def shell_sort(self): """Shell sort also known as or Shell's method, is an in-place comparison sort. It can be seen as either a generalization of sorting by exchange (bubble sort) or sorting by insertion (insertion sort). """ return 1 def heap_sort(self): """Heapsort is an improved selection sort: it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. """ return 1 def merge_sort(self): """Merge sort is a divide and conquer algorithm that was invented by John von Neumann in 1945. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. """ return 1 def quick_sort(self): """Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm. Developed by Tony Hoare in 1959. It is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort. """ return 1 # this plots things in log scale (pls google it), you need to add matplotlib # to your virtualenv first! # plot also python's sorted() function to see how well you do. # plt.plot(set_szs, timing) # plt.xscale('log') # plt.yscale('log') # plt.title('log') # plt.ylabel('some numbers') # plt.show()

Python