| Bubble Sort |
Article Index for Bubble |
Website Links For Bubble |
Information AboutBubble Sort |
| CATEGORIES ABOUT BUBBLE SORT | |
| articles with example pseudocode | |
| sorting algorithms | |
| comparison sorts | |
| stable sorts | |
|
In more detail, the bubble sort algorithm works as follows: #Compare adjacent elements. If the first is greater than the second, swap them. #Do this for each pair of adjacent elements, starting with the first two and ending with the last two. At this point the last element should be the greatest. #Repeat the steps for all elements except the last one. #Keep repeating for one fewer element each time, until you have no more pairs to compare. (Alternatively, keep repeating until no swaps are needed.) function bubblesort (A : ''list'' {Link without Title} ) { var ''int'' i, j; for i '''from''' n '''downto''' 1 { for j '''from''' 1 '''to''' i-1 { if (A > A[j+1 ) swap(A A[j+1 ) } } } IMPLEMENTATION For implementations in other real programming languages, see . C (add a flag) void bubbleSort_flag('''int''' a {Link without Title} , '''int''' n) { int i, j, temp, flag; for(i=n-1; i>0; i--) { flag = 1; for(j=0; i>j; j++) { if(a {Link without Title} >a {Link without Title} ) { flag = 0; temp = a {Link without Title} ; a = a[j+1 ; a {Link without Title} = temp; } } //out this block when flag is true //i.e. inner loop performed no swaps, so the list is already sorted if(flag) break; } } or, a bit modified from pseudo code, but still very efficient :
{ int tmp; int again; int i; for (again = 1; again;) for (again = 0, i = 0; i < (len - 1); i++) { if (tab > tab[i + 1 ) { tmp = tab {Link without Title} ; tab = tab[i + 1 ; tab + 1 = tmp; again = 1; } } } PERFORMANCE Bubble sort needs comparisons to sort n items and can sort in-place. Although the algorithm is one of the simplest sorting algorithms to understand and implement, it is too inefficient for use on lists having more than a few elements. Even among simple sorting algorithms, algorithms like insertion sort are considerably more efficient. Due to its simplicity, the bubble sort is often used to introduce the concept of an algorithm to introductory programming students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught. {Link without Title} The Jargon file, which famously calls '', concluded 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", some of which he discusses therein. Bubble sort is Asymptotically equivalent in running time to Insertion Sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Insertion sort needs only operations if the list is already sorted, whereas naïve implementations of bubble sort (like the pseudocode above) require operations. (This can be reduced to if code is added to stop the outer loop when the inner loop performs no swaps.) Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort. Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more Branch Mispredictions (O(''n''log ''n'') rather than insertion sort's O(''n'')). Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than Selection Sort . Reversing the order in which the list is traversed for each pass improves the efficiency somewhat. This is sometimes called Shuttle Sort since the algorithm shuttles from one end of the list to the other. REFERENCES
EXTERNAL LINKS
|
|
|