What bubble sort Algorithm

how bubble sort works with example, what is bubble sort with example its time complexity,how to write bubble sort algorithm, how to make bubble sort efficient pdf free download
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Bubble sort Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Bubble sort 2 Outline 2 The second sorting algorithm is the O(n ) bubble sort algorithm – Uses an opposite strategy from insertion sort We will examine: – The algorithm and an example – Run times • best case • worst case • average case (introducing inversions) – Summary and discussionBubble sort 3 8.3 Description Suppose we have an array of data which is unsorted: – Starting at the front, traverse the array, find the largest item, and move (or bubble) it to the top – With each subsequent iteration, find the next largest item and bubble it up towards the top of the arrayBubble sort 4 8.3 Description As well as looking at good algorithms, it is often useful too look at sub-optimal algorithms – Bubble sort is a simple algorithm with: • a memorable name, and • a simple idea – It is also significantly worse than insertion sortBubble sort 5 8.3 Observations Some thoughts about bubble sort: – the Jargon file states that bubble sort is “the generic bad algorithm” – Donald Knuth comments that “the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems”Bubble sort 6 8.3 Obama on bubble sort When asked the most efficient way to sort a million 32-bit integers, Senator Obama had an answer: http://www.youtube.com/watch?v=k4RRi_ntQc8Bubble sort 7 8.3.1 Implementation Starting with the first item, assume that it is the largest Compare it with the second item: – If the first is larger, swap the two, – Otherwise, assume that the second item is the largest Continue up the array, either swapping or redefining the largest itemBubble sort 8 8.3.1 Implementation After one pass, the largest item must be the last in the list Start at the front again: – the second pass will bring the second largest element into the second last position Repeat n– 1 times, after which, all entries will be in placeBubble sort 9 8.3.1 Implementation The default algorithm: template typename Type void bubble( Type const array, int const n ) for ( int i = n - 1; i 0; i ) for ( int j = 0; j i; ++j ) if ( arrayj arrayj + 1 ) std::swap( arrayj, arrayj + 1 ); Bubble sort 10 8.3.1 The Basic Algorithm Here we have two nested loops, and therefore calculating the run time is straight-forward: n1 n n 11 n n  2 n k n n1(n )   22 k1Bubble sort 11 8.3.1 Example Consider the unsorted array to the right We start with the element in the first location, and move forward: – if the current and next items are in order, continue with the next item, otherwise – swap the two entriesBubble sort 12 8.3.1 Example After one loop, the largest element is in the last location – Repeat the procedureBubble sort 13 8.3.1 Example Now the two largest elements are at the end – Repeat againBubble sort 14 8.3.1 Example With this loop, 5 and 7 are swappedBubble sort 15 8.3.1 Example Finally, we swap the last two entries to order them – At this point, we have a sorted arrayBubble sort 16 8.3.2 Implementations and Improvements The next few slides show some implementations of bubble sort together with a few improvements: – reduce the number of swaps, – halting if the list is sorted, – limiting the range on which we must bubble, and – alternating between bubbling up and sinking downBubble sort 17 8.3.2.1 First Improvement We could avoid so many swaps... template typename Type void bubble( Type const array, int const n ) for ( int i = n - 1; i 0; i ) Type max = array0; // assume a0 is the max for ( int j = 1; j = i; ++j ) if ( arrayj max ) arrayj - 1 = arrayj; // move else arrayj – 1 = max; // store the old max max = arrayj; // get the new max arrayi = max; // store the max Bubble sort 18 8.3.2.2 Flagged Bubble Sort One useful modification would be to check if no swaps occur: – If no swaps occur, the list is sorted – In this example, no swaps occurred th during the 5 pass Use a Boolean flag to check if no swaps occurredBubble sort 19 8.3.2.2 Flagged Bubble Sort Check if the list is sorted (no swaps) template typename Type void bubble( Type const array, int const n ) for ( int i = n - 1; i 0; i ) Type max = array0; bool sorted = true; for ( int j = 1; j i; ++j ) if ( arrayj max ) arrayj - 1 = arrayj; sorted = false; else arrayj – 1 = max; max = arrayj; arrayi = max; if ( sorted ) break; Bubble sort 20 8.3.2.3 Range-limiting Bubble Sort Intuitively, one may believe that limiting the loops based on the location of the last swap may significantly speed up the algorithm – For example, after the second pass, we are certain all entries after 4 are sorted The implementation is easier than that for using a Boolean flag

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.