Sorting: why? We do it A LOT! Makes finding the largest and smallest value easier Makes finding how many of a certain value are in a list easier Using binary search, makes finding anything much quicker Plus its a nice way to show differences in efficiency in algorithms First: SelectionSort 1. Idea: Go through and find the smallest value in a list.

2. Switch it with the first value on the list Or remove it and append it to a new list. Repeat steps 1 and 2 until the entire list is sorted This algorithm is very easy to conceive of and to implement, but it isnt terribly efficient. For every value we put in place, we have to go through the whole (rest of the) list and find the smallest value. We have to do this for every value.

Thus analysis of running time is estimated to be n2 (assuming there are n values in the list) def SelectionSort(ls): for i in range(len(ls)): s=ls[i] si = i for j in range(i, len(ls)): if (ls[j]~~", SelectionSort(a)) Analysis? a = [1,2,3,4,5] a = [5,4,3,2,1] Next: BubbleSort 1. Idea: compare the first and second number in the list. If the first is greater than ~~

the second, switch them (this is known as bubbling up). 2. Compare the (possibly new) second and third number in the list. If the second is greater than the third, switch them. 3. Compare the third and fourth numbers in the list. If the third is greater than the fourth, switch them. 4. Continue like this to the end of the list. Repeat steps 1-4 again and again, until there are no more switches (bubbles). Analysis: Worst case: n2 (with n being the length of the list) Best case: when the list is already sorted

Then you only do steps 1-4 1 time, so analysis is only n This algorithm is a bit more efficient than selection sort, but also just a bit more difficult to write in code (not much!) def bubblesort(list2): i = 0; swap_test = False while ((i < len(list2)-1) and (swap_test == False)): swap_test = True for j in range(0, len(list2) - i - 1): if list2[j] > list2[j + 1]: list2[j], list2[j + 1] = list2[j + 1], list2[j] swap_test = False i += 1 return(list2) ls = [3,2,4,7,1] print(bubblesort(ls)) Next: InsertionSort Idea: Always inserting into an already sorted portion of the list 1.

Take the second card in a list and compare it to the first card. Make sure the first two cards are in order by possibly switching the first and second card. 2. Take the third card and compare it to the second card and possibly the first card, placing it into the correct order so the first, second, and third card are sorted. Repeat steps 1-3 with each card in the list until the entire list is sorted. Analysis: Worst case: n2 (with n being the length of the list) Best case: when the list is already sorted Then you do one comparison for each number in the list, so analysis is only n In terms of efficiency, about the same as bubblesort def insertionsort(ls):

for i in range(0,len(ls)): x = ls[i] j = i-1 while (j >= 0) and (ls[j] > x): ls[j+1] = ls[j] j = j-1 ls[j+1] = x return(ls) ls=[3,1,2,6,4,7] insertionsort(ls) print(ls) Analysis? a = [1,2,3,4,5] a = [5,4,3,2,1] QuickSort Idea: select a pivot value in the list All values less than the pivot go in the list below the pivot.

All values greater than the pivot go in the list above the pivot Pivot is now in place. Repeat (recursively) with the lesser list and the greater list. Analysis: Average case: nlog2n (with n being the length of the list) Each time were dividing the list in half (hopefully) So we compare the full list, then half the list, then the list, then 1/8 the list, etc. def main( aList ): quicksort( aList, 0, len( aList ) - 1 ) QuickSort

def quicksort( aList, first, last ): if first < last: pivot = partition( aList, first, last ) quicksort( aList, first, pivot - 1 ) quicksort( aList, pivot + 1, last ) def partition( aList, first, last ) : pivot = first + random.randrange( last - first + 1 ) swap( aList, pivot, last ) for i in range( first, last ): if aList[i] <= aList[last]: swap( aList, i, first ) first += 1 swap( aList, first, last ) return first def swap( A, x, y ): tmp = A[x] A[x] = A[y] A[y] = tmp #could have just said, A[x],A[y] = A[y],A[x] ls = [32,41,33,12,8,3,24,15,97,54,36,26,71,51,32,0,6,2] main(ls) print(ls)

Next: MergeSort Idea: pretend each number in the list is its own list. 1. Merge each neighboring list into a list of two sorted elements. 2. Merge each sorted list of two elements into sorted lists of 4 elements. 3. Merge each sorted list of 4 elements into sorted lists of 8 elements. 4. Continue to merge neighboring lists until theres only one list left. Analysis: Worst case: nlog2n (with n being the length of the list) Each time were merging half the list. So were doing log 2n merges.

We may need to compare each number when we merge, so thats the n This is the most efficient of the sorting algorithms weve seen! MergeSort in Python: def mergesort(lista): def merge(left, right): if len(lista) <=1: result = [] return lista else: i ,j = 0, 0 middle = len(lista) / 2 while i < len(left) and j < len(right): #keep dividing left side into 2 if left[i] <= right[j]: #lists half the size of the original result.append(left[i]) left = mergesort(lista[:middle]) i += 1 #keep dividing right side into 2

else: #lists half the size of the original result.append(right[j]) right = mergesort(lista[middle:]) j += 1 result += left[i:] #now we have a bunch of small lists #that we need to keep merging result += right[j:] #back into larger, sorted lists return result return merge(left, right) listb = [8,2,3,1,9,5,7,0,4,6] print(mergesort(listb))