# Sorting: why? We do it A LOT! Makes

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))

## Recently Viewed Presentations

• Editor and Publishing Environment. Web map product. QA/QC. Internal and from other government agencies. ... SPC- Geoscience Division. We would just like to acknowledge all the custodians whose data enabled this product to come together. Thank you. Author:
• Implementasi Fungsi Logika. (Continued) B A D C Chapter 2 - Part 1 * Gerbang Logika(Logic Gates) Pada awal komputer, switches terbuka dan tertutup menggunakan medan magnit yang dihasilkan oleh energi dari koil pada relays. Switches secara bergantian membuka dan...
• Biodiversity & Ecology: Ecology. The relationship and interaction between organisms and their environment. The distribution and quantity of organisms in certain environments. Factors limiting and supporting the populations. Climate. Climate is the most important factor determining where and how many...
• (Note that the products H2O and CO2 are in their gaseous form.) Further, by employing Charles' Law for perfect gases, the volume of the products of explosion may also be calculated for any given temperature. This law states that at...
• Numerical facts such as averages, medians, percents, and index numbers. Art and science of collecting, analyzing, presenting, and interpreting data. Data and Data Sets. Data are the facts and figures collected, analyzed, and summarized for presentation and interpretation.
• In college TESL cert. ES/FL Yrs using rubrics 7 5 2 "on and off" 2 Used criteria sheets 20 5 * * I am a sessional teacher in the full time ESL program at George Brown College I did my...
• The U.S. and the Fall of the Soviet Union (We won! #merica) Mikhail Gorbachev (1988-1991) Young (56) Reformer First leader to be born after the Revolution (Significance?)
• Image texturing. Usually, texturing is image texturing: Gluing a 2D image onto a polygon. Recall that textures have certain limitations. Usually 2m x 2ntexels. Some old cards require square textures. Most new cards don't have to do powers of 2....