CompSci 100E29.1Sorting: From Theory to Practiceÿ Why do we study sorting?þ Because we have toþ Because sorting is beautifulþ Example of algorithm analysis in a simple, useful settingÿ There are n sorting algorithms, how many should we study?þ O(n), O(log n), …þ Why do we study more than one algorithm?o Some are good, some are bad, some are very, very sado Paradigms of trade-offs and algorithmic designþ Which sorting algorithm is best?þ Which sort should you call from code you write?CompSci 100E29.2Sorting out sortsÿ Simple, O(n2) sorts --- for sorting n elementsþ Selection sort --- n2comparisons, n swaps, easy to codeþ Insertion sort --- n2comparisons, n2moves, stable, fast on nearlysorted vectors: O(n)þ Bubble sort --- n2everything, slowerÿ Divide and conquer faster sorts: O(n log n) for n elementsþ Quick sort: fast in practice, O(n2) worst caseþ Merge sort: good worst case, great for linked lists, stable, usesextra storage for vectors/arraysÿ Other sorts:þ Heap sort, basically priority queue sortingþ Radix sort: doesn’t compare keys, uses digits/charactersþ Shell sort: quasi-insertion, fast in practice, non-recursiveCompSci 100E29.3Selection sort: summaryÿ Simple to code n2sort: n2comparisons, n swapsvoid selectSort(String[] a){for(int k=0; k < a.length; k++){int minIndex = findMin(a,k);swap(a,k,minIndex);}}ÿ # comparisons:þ Swaps?þ Invariant:ΣΣΣΣk=1nk=1+2+…+n=n(n+1)/2=O(n2)Sorted, won’t movefinal position?????CompSci 100E29.4Insertion Sort: summaryÿ Stable sort, O(n2) -- ( O(n) on nearly sorted vectors!)þ Stable sorts maintain order of equal keysþ Good for sorting on two criteria: name, then agevoid insertSort(String[] a){int k, loc; string elt;for(k=1; k < a.length; k++) {elt = a[k];loc = k;// shift until spot for elt is foundwhile (0 < loc && elt.compareTo(a[loc-1]) < 0) {a[loc] = a[loc-1]; // shift rightloc=loc-1;}a[loc] = elt;}}Sorted relative toeach other?????CompSci 100E29.5Bubble sort: summary of a dogÿ For completeness you should know about this sortþ Few, if any, redeeming features. Really slow, reallyþ Can code to recognize already sorted vector (see insertion)o Not worth it for bubble sort, much slower than insertionvoid bubbleSort(String[] a) {for(int j=a.length-1; j >= 0; j--) {for(int k=0; k < j; k++) {if (a[k] > a[k+1])swap(a,k,k+1);}}}ÿ “bubble” elements down the vector/arraySorted, in finalposition?????CompSci 100E29.6Summary of simple sortsÿ Selection sort has n swaps, good for “heavy” dataþ moving objects with lots of state, e.g., …o In C or C++ this is an issueo In Java everything is a pointer/reference, so swapping is fastsince it's pointer assignmentÿ Insertion sort is good on nearly sorted data, it’s stable, it’s fastþ Also foundation for Shell sort, very fast non-recursiveþ More complicated to code, but relatively simple, and fastÿ Bubble sort is a travesty? But it's fast to code if you know it!þ Can be parallelized, but on one machine don’t go near it (seequotes at end of slides)CompSci 100E29.7Quicksort: fast in practiceÿ Invented in 1962 by C.A.R. Hoare, didn’t understand recursionþ Worst case is O(n2), but avoidable in nearly all casesþ In 1997 Introsort published (Musser, introspective sort)o Like quicksort in practice, but recognizes when it will be badand changes to heapsortvoid quick(String[], int left, int right) {if (left < right) {int pivot = partition(a, left, right);quick(a, left, pivot-1);quick(a, pivot+1, right);}}ÿ Recurrence?<= X>XXpivot indexCompSci 100E29.8Partition codefor quicksortleftÿEasy to develop partitionint partition(String[] a,int left, int right){string pivot = a[left];int k, pIndex = left;for(k=left+1, k <= right; k++){if (a[k].compareTo(pivot) <= 0){pIndex++;swap(a,k,pIndex);}}swap(a,left,pIndex);}ÿ Loop invariant:þ statement true each time loop test isevaluated, used to verify correctness ofloopÿ Can swap into a[left] before loopþ Nearly sorted data still ok??????????????<=>???<= pivot > pivotpIndexleftrightrightleft rightwhat we wantwhat we start withinvariantpIndexkCompSci 100E29.9Analysis of Quicksortÿ Average case and worst case analysisþ Recurrence for worst case: T(n) =þ What about average?ÿ Reason informally:þ Two calls vector size n/2þ Four calls vector size n/4þ … How many calls? Work done on each call?ÿ Partition: typically find middle of left, middle, right, swap, goþ Avoid bad performance on nearly sorted dataÿ In practice: remove some (all?) recursion, avoid lots of “clones”T(n-1) + T(1) + O(n)T(n) = 2T(n/2) + O(n)CompSci 100E29.10Tail recursion eliminationÿ If the last statement is a recursive call, recursion can be replacedwith iterationþ Call cannot be part of an expressionþ Some compilers do this automaticallyvoid foo(int n) void foo2(int n){{if(0<n){ while(0<n){System.out.println(n); System.out.println(n);foo(n-1); n = n-1;}}}}ÿ What if print and recursive call switched?ÿ What about recursive factorial? return n*factorial(n-1);CompSci 100E29.11Merge sort: worst case O(n log n)ÿ Divide and conquer --- recursive sortþ Divide list/vector into two halveso Sort each halfo Merge sorted halves togetherþ What is complexity of merging two sorted lists?þ What is recurrence relation for merge sort as described?T(n) =ÿ What is advantage of array over linked-list formerge sort?þ What about merging, advantage of linked list?þ Array requires auxiliary storage (or very fancy coding)T(n) = 2T(n/2) + O(n)CompSci 100E29.12Merge sort: lists or vectorsÿ Mergesort for vectorsvoid mergesort(String[] a, int left, int right) {if (left < right) {int mid = (right+left)/2;mergesort(a, left, mid);mergesort(a, mid+1, right);merge(a,left,mid,right);}}ÿ What’s different when linked lists used?þ Do differences affect complexity? Why?ÿ How does merge work?CompSci 100E29.13Mergesort continuedÿ Array code for merge isn’t pretty, but it’s not hardþ Mergesort itself is elegantvoid merge(String[] a,int left, int middle, int right)// pre: left <= middle <= right,// a[left] <= … <= a[middle],// a[middle+1] <= … <= a[right]// post: a[left] <= … <= a[right]ÿ Why is this prototype potentially simpler for linkedlists?þ What will prototype be? What is complexity?CompSci 100E29.14Mergesort continuedvoid merge(String[] a, int left, int middle, int right) {String[] b = new String[right - left + 1];int k = 0, kl = left, kr = middle + 1;for (; kl <= middle && kr <= right; k++){if (a[kl].compareTo(a[kr]) <= 0)b[k] =
View Full Document
Unlocking...