1Week4:SortingAlgorithmsBubble sort Compare each element (except the last one) with itsneighbor to the right If they are out of order, swap them This puts the largest element at the very end The last element is now in the correct and final place Compare each element (except the last two) with itsneighbor to the right If … Continue reading “Sorting Algorithms Bubble sort | My Assignment Tutor”
1Week4:SortingAlgorithmsBubble sort Compare each element (except the last one) with itsneighbor to the right If they are out of order, swap them This puts the largest element at the very end The last element is now in the correct and final place Compare each element (except the last two) with itsneighbor to the right If they are out of order, swap them This puts the second largest element next to last The last two elements are now in their correct and finalplaces Compare each element (except the last three) with itsneighbor to the right Continue as above until you have no unsorted elements onthe left22Example of bubble sort 37 2 8 5 42 7 8 5 42 7 8 5 42 7 5 8 42 7 5 4 82 7 5 4 82 5 7 4 82 5 4 7 82 7 5 4 82 5 4 7 82 4 5 7 82 5 4 7 82 4 5 7 82 4 5 7 8(done)Code for bubble sort public static void bubbleSort(int[] a) {int outer, inner;for (outer = a.length – 1; outer > 0; outer–) { // counting down for (inner = 0; inner a[inner + 1]) { // if out of order…int temp = a[inner];// …then swap a[inner] = a[inner + 1];a[inner + 1] = temp;}}}}43Analysis of bubble sort for (outer = a.length – 1; outer > 0; outer–) {for (inner = 0; inner a[inner + 1]) {// code for swap omitted} } } Let n = a.length = size of the array The outer loop is executed n-1 times (call it n, that’s closeenough) Each time the outer loop is executed, the inner loop isexecuted Inner loop executes n-1 times at first, linearly dropping tojust once On average, inner loop executes about n/2 times for eachexecution of the outer loop In the inner loop, the comparison is always done (constanttime), the swap might be done (also constant time) Result is n * n/2 * k, that is, O(n2/2 + k) = O(n2)5Loop invariants You run a loop in order to change things Oddly enough, what is usually most important inunderstanding a loop is finding an invariant: that is,a condition that doesn’t change In bubble sort, we put the largest elements at theend, and once we put them there, we don’t movethem again The variable outer starts at the last index in the array anddecreases to 0 Our invariant is: Every element to the right of outer is in thecorrect place That is, for all j > outer, if i
