Simple Sorting AlgorithmsBubble sortExample of bubble sortCode for bubble sortAnalysis of bubble sortLoop invariantsSelection sortExample and analysis of selection sortCode for selection sortInvariants for selection sortInsertion sortOne step of insertion sortAnalysis of insertion sortSummaryThe EndSimple Sorting Algorithms2Bubble sortCompare each element (except the last one) with its neighbor to the rightIf they are out of order, swap themThis puts the largest element at the very endThe last element is now in the correct and final placeCompare each element (except the last two) with its neighbor to the rightIf they are out of order, swap themThis puts the second largest element next to lastThe last two elements are now in their correct and final placesCompare each element (except the last three) with its neighbor to the rightContinue as above until you have no unsorted elements on the left3Example of bubble sort72 8 5 427 8 5 427 8 5 427 5 8 427 5 4 827 5 4 825 7 4 825 4 7 827 5 4 825 4 7 824 5 7 825 4 7 824 5 7 824 5 7 8(done)4Code for bubble sortpublic static void bubbleSort(int[] a) { int outer, inner; for (outer = a.length - 1; outer > 0; outer--) { // counting down for (inner = 0; inner < outer; inner++) { // bubbling up if (a[inner] > a[inner + 1]) { // if out of order... int temp = a[inner]; // ...then swap a[inner] = a[inner + 1]; a[inner + 1] = temp; } } }}5Analysis of bubble sortfor (outer = a.length - 1; outer > 0; outer--) { for (inner = 0; inner < outer; inner++) { if (a[inner] > a[inner + 1]) { // code for swap omitted} } }Let n = a.length = size of the arrayThe outer loop is executed n-1 times (call it n, that’s close enough)Each time the outer loop is executed, the inner loop is executedInner loop executes n-1 times at first, linearly dropping to just onceOn average, inner loop executes about n/2 times for each execution of the outer loopIn the inner loop, the comparison is always done (constant time), the swap might be done (also constant time)Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)6Loop invariantsYou run a loop in order to change thingsOddly enough, what is usually most important in understanding a loop is finding an invariant: that is, a condition that doesn’t changeIn bubble sort, we put the largest elements at the end, and once we put them there, we don’t move them againThe variable outer starts at the last index in the array and decreases to 0Our invariant is: Every element to the right of outer is in the correct placeThat is, for all j > outer, if i < j, then a[i] <= a[j]When this is combined with the loop exit test, outer == 0, we know that all elements of the array are in the correct place7Selection sortGiven an array of length n,Search elements 0 through n-1 and select the smallestSwap it with the element in location 0Search elements 1 through n-1 and select the smallestSwap it with the element in location 1Search elements 2 through n-1 and select the smallestSwap it with the element in location 2Search elements 3 through n-1 and select the smallestSwap it with the element in location 3Continue in this fashion until there’s nothing left to search8Example and analysis of selection sortThe selection sort might swap an array element with itself--this is harmless, and not worth checking forAnalysis:The outer loop executes n-1 timesThe inner loop executes about n/2 times on average (from n to 2 times)Work done in the inner loop is constant (swap two array elements)Time required is roughly (n-1)*(n/2)You should recognize this as O(n2)72 8 5 427 8 5 424 8 5 724 5 8 724 5 7 89Code for selection sortpublic static void selectionSort(int[] a) { int outer, inner, min; for (outer = 0; outer < a.length - 1; outer++) { min = outer; for (inner = outer + 1; inner < a.length; inner++) { if (a[inner] < a[min]) { min = inner; } // Invariant: for all i, if outer <= i <= inner, then a[min] <= a[i] } // a[min] is least among a[outer]..a[a.length - 1] int temp = a[outer]; a[outer] = a[min]; a[min] = temp; // Invariant: for all i <= outer, if i < j then a[i] <= a[j] }}10Invariants for selection sortFor the inner loop:This loop searches through the array, incrementing inner from its initial value of outer+1 up to a.length-1As the loop proceeds, min is set to the index of the smallest number found so farOur invariant is:for all i such that outer <= i <= inner, a[min] <= a[i]For the outer (enclosing) loop:The loop counts up from outer = 0Each time through the loop, the minimum remaining value is put in a[outer]Our invariant is:for all i <= outer, if i < j then a[i] <= a[j]11Insertion sortThe outer loop of insertion sort is: for (outer = 1; outer < a.length; outer++) {...}The invariant is that all the elements to the left of outer are sorted with respect to one anotherFor all i < outer, j < outer, if i < j then a[i] <= a[j]This does not mean they are all in their final correct place; the remaining array elements may need to be insertedWhen we increase outer, a[outer-1] becomes to its left; we must keep the invariant true by inserting a[outer-1] into its proper placeThis means: Finding the element’s proper placeMaking room for the inserted element (by shifting over other elements)Inserting the element12One step of insertion sort34 7 121414202133381055 9232816sorted next to be inserted34 755 923281610temp3833212014141210sortedless than 1013Analysis of insertion sortWe run once through the outer loop, inserting each of n elements; this is a factor of nOn average, there are n/2 elements already sortedThe inner loop looks at (and moves) half of theseThis gives a second factor of n/4Hence, the time required for an insertion sort of an array of n elements is proportional to n2/4Discarding constants, we find that insertion sort is O(n2)14SummaryBubble sort, selection sort, and insertion sort are all O(n2)As we will see later, we can do much better than this with somewhat more complicated sorting algorithmsWithin O(n2), Bubble sort is very slow, and should probably never be used for anythingSelection sort is intermediate in speedInsertion sort is usually the fastest of the three--in fact, for small arrays (say, 10 or 15 elements), insertion sort is faster than more complicated
View Full Document