|
|
Home | Switchboard | Unix Administration | Red Hat | TCP/IP Networks | Neoliberalism | Toxic Managers |
| (slightly skeptical) Educational society promoting "Back to basics" movement against IT overcomplexity and bastardization of classic Unix | |||||||
| Sorting algorithms | Recommended Books | Recommended Links | Shaker sort | Insertion sort | |
| Animations | Testing Sorting Algorithms | Donald Knuth | The Art of Computer Programming | Humor | Etc |
|
|
This horrible bubblesort algorithm tortured generations of students who take programming classes ;-).
In reality, bubblesort is an extremely simple algorithm the most distinctive feature of which is that this is most often incorrectly implemented sorting algorithms in existence. Looks like few writes of bubblesort even open Knuth.
It is not only incorrectly implemented in popular web pages, it is also often implemented incorrectly in textbooks and animations :-). Again, bubblesort is probably the champion of incorrect implementations among simple sorting algorithms
| Bubblesort is probably the champion of incorrect implementations among simple sorting algorithms |
|
|
The idea is to swap adjacent elements, if the elements are out of order, moving up or down the data set. Usually multiple passes are necessary. Each subsequent pass is shorter as elements after the last swap are already sorted (it is this element that is often missed in "naive" implementations that dominate the web). It terminated as soon as no swaps were performed during the pass. See animation to get better idea of the details
On any set of data it is less efficient then Insertion sort so it has purely theoretical value as it has some interesting properties. Like insertion sort it is a stable sorting algorithm.
See Reversed Initial Order - Sorting Algorithm Animations for nice animation
An interesting and often overlooked feature of the algorithm is that the last swap signify the boundary of the already sorted part of the array. In this sense bubblesort is similar to selection sort as on each pass the maximum or minimum element in the unsorted part is found and subsequent sort can be done on a subset that is smaller then initial by one or more elements (the place of last swap is the boundary).
Speed with which largest element "sinks" is high -- he occupies its proper place in one pass, but the speed with which small element "floats up" is slow: only one exchange is done on each path. That's why sometimes largest elements in bubble sort are called "rabbits" and smallest "tortoises".
But it's details of the implementation that are presented are often incorrect. For example Robert Sedgewick's implementation Algorithms in Java, Third Edition, Parts 1-4: Fundamentals, Data Structures, Sorting, Searching is definitely wrong (too primitive to be exact) and does not corresponds to Donald Knuth's version:
static void bubble(ITEM[] a, int l, int r)
{ for (int i = l; i < r; i++)
for (int j = r; j > i; j--)
compExch(a, j-1, j);
}
As most implementations of bubblesort presented on the web and some implementations in the textbooks are incorrect it is important to understand two properties of the correct implementation of bubblesort:
Two properties of the correct implementation of bubblesort:
|
Here is the reimplementation of the algorithm as it was discussed by Knuth:
void bubbleSort(int a[], int n)
/* Sorts in increasing order the array A of the size N */
{
int k;
int bound = n-1;
int t;
int last_swap;
while (bound) {
last_swap = 0;
for ( k=0; k<bound; k++ )
t = a[k]; /* t is a maximum of A[0]..A[k] */
if ( t > a[k+1] ) {
a[k] = a[k+1]; a[k+1] = t; /*swap*/
last_swap = k; /* mark the last swap position */
}//if
}//for
bound=last_swap; /*elements after bound are already sorted */
}//while
} // bubbleSort
There the valuable bound determines when the sorting is finished and it is assigned the position of the last swap. The part of the code that "drags" maximum element to the bottom is sometimes called "bubblemax" and can be coded as subroutines but that does not make much sense. You can also double this part of algorithm adding "bubblemin" pass on the opposite direction to compensate for the slowness with which minimum elements are "bubbling up" while max element is "sinking" in a single pass. This enhancement to bidirectional bubblesort is known also as shaker sort. But the question is whether this enhancement worth the additional complexity as there are more efficient algorithms of comparable complexity which achieve the same goals (first of all Mergesort).
If you were to watch a graphical representation of the sorting occurring, you would see that each path the smallest element gets "bubbled" up to the top, while the largest element is sinking to the bottom.
One of the few advantages of Bubblesort is that like insertion sort it is a natural algorithm to be used on lists. It is also works very well on already sorted lists, or lists with just few permutations. If there is just one permutation the algorithm requires just one pass to sort.
It is possible to increase the speed of Bubblesort, but only at the cost of increased complexity of the code. One trivial enhancement is to make it symmetrical alternating passes in each direction. This variant is often called cocktail sort (implementations at Wikipedia are incorrect) or shaker short. It works much better is only works much better when some small and large items are swapped in the data set and concentrated on the "wrong end".
The other possibility is shorten the size of the pass based on observation that the element before the first swap can be used for the beginning of next pass: previous elements cannot change their places as they are in partial order. This adds to total number of comparison as check for the first swaps will be performed for each swap. See C++ Notes Algorithms More Bubble Sorts for the implementation of this idea.
|
|
Switchboard | ||||
| Latest | |||||
| Past week | |||||
| Past month | |||||
 |
 |
 |
Dec 27, 2018 | en.wikipedia.org
Comb sort is a relatively simple sorting algorithm originally designed by Włodzimierz Dobosiewicz in 1980. [1] [2] Later it was rediscovered by Stephen Lacey and Richard Box in 1991. [3] Comb sort improves on bubble sort . Contents
Algorithm [ edit ]The basic idea is to eliminate turtles , or small values near the end of the list, since in a bubble sort these slow the sorting down tremendously. Rabbits , large values around the beginning of the list, do not pose a problem in bubble sort.
In bubble sort , when any two elements are compared, they always have a gap (distance from each other) of 1. The basic idea of comb sort is that the gap can be much more than 1. The inner loop of bubble sort, which does the actual swap , is modified such that gap between swapped elements goes down (for each iteration of outer loop) in steps of a "shrink factor" k : [ n / k , n / k 2 , n / k 3 , ..., 1 ].
The gap starts out as the length of the list n being sorted divided by the shrink factor k (generally 1.3; see below) and one pass of the aforementioned modified bubble sort is applied with that gap. Then the gap is divided by the shrink factor again, the list is sorted with this new gap, and the process repeats until the gap is 1. At this point, comb sort continues using a gap of 1 until the list is fully sorted. The final stage of the sort is thus equivalent to a bubble sort, but by this time most turtles have been dealt with, so a bubble sort will be efficient.
The shrink factor has a great effect on the efficiency of comb sort. k = 1.3 has been suggested as an ideal shrink factor by the authors of the original article after empirical testing on over 200,000 random lists. A value too small slows the algorithm down by making unnecessarily many comparisons, whereas a value too large fails to effectively deal with turtles, making it require many passes with 1 gap size.
The pattern of repeated sorting passes with decreasing gaps is similar to Shellsort , but in Shellsort the array is sorted completely each pass before going on to the next-smallest gap. Comb sort's passes do not completely sort the elements. This is the reason that Shellsort gap sequences have a larger optimal shrink factor of about 2.2.
Pseudocode
function combsort(array input) gap := input.size // Initialize gap size shrink := 1.3 // Set the gap shrink factor sorted := false loop while sorted = false // Update the gap value for a next comb gap := floor(gap / shrink) if gap ≤ 1 gap := 1 sorted := true // If there are no swaps this pass, we are done end if // A single "comb" over the input list i := 0 loop while i + gap < input.size // See Shell sort for a similar idea if input[i] > input[i+gap] swap(input[i], input[i+gap]) sorted := false // If this assignment never happens within the loop, // then there have been no swaps and the list is sorted. end if i := i + 1 end loop end loop end function
|
|
|
|
|
|
|
|
|
- Bubble sort is the best first sorting algorithm to teach No, it isn't. I have written an entire page about why bubble sort is a horrible sorting algorithm to teach as some kind of first basic sorting.
- Bubble sort is the easiest sorting algorithm to understand No, it isn't. Compared to both insertion sort (the best O(n2) sorting algorithm) and selection sort, bubble sort is quite complicated for a beginner programmer to understand. (More precisely, it's surprisingly difficult to understand why it works.) Both insertion sort and selection sort are much closer to how people intuitively would sort a collection of things, which makes them much easier to understand. Bubble sort is very exotic and has nothing to do with how people would intuitively sort things.
- Bubble sort is the easiest to implement No, it isn't. Both insertion sort and selection sort are at least as easy to implement, and require approximately the same amount of code.
- Bubble sort is efficient with small amounts of data. No, it isn't. Not compared with other O(n2) sorting algorithms, one of the best of them being insertion sort. There exist no cases where bubble sort would be faster than insertion sort. Insertion sort always beats bubble sort (this is actually rather easy to prove mathematically). Since insertion sort is easier to understand and equally easy to implement, there just is no disadvantage in using it rather than bubble sort.
|
|
|
Tinsology
It is not too often in the real world that you have to implement your own sort. Generally, whatever language you are using has a library with this functionality built in. If the occasion does arise, however, it is important to understand which algorithms are applicable in which situations. As with most choices, there is no absolute correct answer; there are many trade offs to consider. When choosing an algorithm there are three things you should consider: performance, overhead, and ease of implementation.You should give equal consideration to each of these factors, disregarding any one of them can lead to poor choices. It is common, for instance, for people to ignore the ease of implementation and focus on the performance of the algorithm. The problem with this is that not every operation is critical. No one is going to die if they songs on their play list do not get sorted quickly enough. Programmer time is more expensive than run time as a professor of mine often said. In addition to this, some high performance algorithms can slower than simpler algorithms due to overhead. If you are sorting 100 items, you can probably insertion sort them just as fast or faster than you can heap sort them. The same would not be true with one million items; heap sort would be faster.
Once we consider all of the factors, you should find that no one algorithm is ideal in every case. There are some algorithms, however, that are not ideal in any case. Unfortunately one of these algorithms is among the most popular: bubble sort. Bubble sort is a very simple algorithm to implement and it has little overhead. The problem lies in its performance. You might think that this conflicts with my earlier point that even simple, low performance algorithms can be faster than others in the right situation. You also might think that bubble sort, being easy to implement, makes up for its performance short comings. This would be true, if it were not the case that there are algorithms that are equally simple to implement, require just as little overhead, and perform better in practice.
Insertion sort is one such algorithm. Like bubble sort it is an in place sort, and is just as easy to implement. Both algorithms have the same time complexity (O notation), but in practice insertion sort performs better in most cases. This being the case you may wonder why bubble sort is even around. Certainly if it is obsolete pages regarding its implementation should be torn out of books and mentioning it should be punishable by a swift slap with a keyboard. Maybe not. When I learned bubble sort it was as an example of how not to sort. In my non-expert opinion, it is equally important to understand how NOT to do things as it is important to understand how TO do them. My point? Learn bubble sort, but never use it.
|
|
|
Here are some additional variations on bubble sort.Bubble Sort -- stop when no exchanges
This version of bubble sort continues making passes over the array as long as there were any exchanges. If the array is already sorted, this sort will stop after only one pass.void bubbleSort2(int x[], int n) { bool exchanges; do { exchanges = false; // assume no exchanges for (int i=0; i<n-1; i++) { if (x[i] > x[i+1]) { int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp; exchanges = true; // after exchange, must look again } } } while (exchanges); }Disadvantage: This algorithm doesn't shorten the range each time by 1 as it could. See below.Bubble Sort -- stop when no exchanges, shorter range each time
This version of bubble sort combines ideas from the previous versions. It stops when there are no more exchanges, and it also sorts a smaller range each time.void bubbleSort3(int x[], int n) { bool exchanges; do { n--; // make loop smaller each time. exchanges = false; // assume this is last pass over array for (int i=0; i<n; i++) { if (x[i] > x[i+1]) { int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp; exchanges = true; // after an exchange, must look again } } } while (exchanges); }Disadvantage: After the first pass it may not be necessary to examine the entire range of the array -- only from where the lowest exchange occurred to where the highest exchange occurred. The parts above and below must already be sorted. See below.Bubble Sort -- Sort only necessary range
Here's a version of bubble sort that, on each pass, looks only at the region of array where more exchanges might be necessary.Disadvantage: Notice that the largest unsorted element will always be moved all the way to its correct position in the array, but small elements are shifted down by only one place on each pass.
//========================================================= bubbleSortRange // After a pass in bubble sort, it's only necessary to sort from just // below the first exchange (small values may move lower) // to just before the last exchange (largest values won't move higher). // Everything that wasn't exchanged must be in the correct order. // After each pass, the upper and lower bounds for the next pass are // set from the positions of the first and last exchanges on prev pass. void bubbleSortRange(int x[], int n) { int lowerBound = 0; // First position to compare. int upperBound = n; // First position NOT to compare. //--- Continue making passes while there is a potential exchange. while (lowerBound <= upperBound) { int firstExchange = n; // assume impossibly high index for low end. int lastExchange = -1; // assume impossibly low index for high end. //--- Make a pass over the appropriate range. for (int i=lowerBound; i<upperBound; i++) { if (x[i] > x[i+1]) { //--- exchange elements int temp = x[i]; x[i] = x[i+1]; x[i+1] = temp; //--- Remember first and last exchange indexes. if (i<firstExchange) { // true only for first exchange. firstExchange = i; } lastExchange = i; } } //--- Prepare limits for next pass. lowerBound = firstExchange-1; if (lowerBound < 0) { lowerBound = 0; } upperBound = lastExchange; } }//end bubbleSortRangeThe text from the above example can be selected, copied, and pasted into an editor.Other bubble sorts
Note that in all these sorts the part that is sorted grows at only one end of the array. The ability to quit early is not symmetrical. The extreme values move all the way to the end in one direction, but only one place in the other direction. The algorithm can be improved by alternately "bubbling" in opposite directions.
|
|
|
InformIT
LISTING 3.1 The bubbleSort.java Program
// bubbleSort.java // demonstrates bubble sort // to run this program: C>java BubbleSortApp //////////////////////////////////////////////////////////////// class ArrayBub { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayBub(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j=0; j<nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort() //-------------------------------------------------------------- private void swap(int one, int two) { long temp = a[one]; a[one] = a[two]; a[two] = temp; } //-------------------------------------------------------------- } // end class ArrayBub //////////////////////////////////////////////////////////////// class BubbleSortApp { public static void main(String[] args) { int maxSize = 100; // array size ArrayBub arr; // reference to array arr = new ArrayBub(maxSize); // create the array arr.insert(77); // insert 10 items arr.insert(99); arr.insert(44); arr.insert(55); arr.insert(22); arr.insert(88); arr.insert(11); arr.insert(00); arr.insert(66); arr.insert(33); arr.display(); // display items arr.bubbleSort(); // bubble sort them arr.display(); // display them again } // end main() } // end class BubbleSortApp ////////////////////////////////////////////////////////////////The constructor and the insert() and display() methods of this class are similar to those we've seen before. However, there's a new method: bubbleSort(). When this method is invoked from main(), the contents of the array are rearranged into sorted order.
The main() routine inserts 10 items into the array in random order, displays the array, calls bubbleSort() to sort it, and then displays it again. Here's the output:
77 99 44 55 22 88 11 0 66 33 0 11 22 33 44 55 66 77 88 99The bubbleSort() method is only four lines long. Here it is, extracted from the listing:
public void bubbleSort() { int out, in; for(out=nElems-1; out>1; out--) // outer loop (backward) for(in=0; in<out; in++) // inner loop (forward) if( a[in] > a[in+1] ) // out of order? swap(in, in+1); // swap them } // end bubbleSort()
|
|
|
Visualizers
Google matched content |
Bubble sort (double direction)
Definition: A variant of bubble sort which compares each adjacent pairs of items in a list in turn, swapping them if necessary, and alternately passes through the list from the beginning to the end then from the end to the beginning until no swaps are done.
Also known as cocktail shaker sort, shaker sort, double-direction bubble sort.
See also sort.
Note: Complexity is O(n2) for arbitrary data, but approaches O(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better than bubble sort since at least one item is moved forward or backward to its place in the list with each pass. Bubble sort moves items forward into place, but can only move items backward one location each pass.
Bidirectional Bubble Sort Algorithm Demo
Society
Groupthink : Two Party System as Polyarchy : Corruption of Regulators : Bureaucracies : Understanding Micromanagers and Control Freaks : Toxic Managers : Harvard Mafia : Diplomatic Communication : Surviving a Bad Performance Review : Insufficient Retirement Funds as Immanent Problem of Neoliberal Regime : PseudoScience : Who Rules America : Neoliberalism : The Iron Law of Oligarchy : Libertarian Philosophy
Quotes
War and Peace : Skeptical Finance : John Kenneth Galbraith :Talleyrand : Oscar Wilde : Otto Von Bismarck : Keynes : George Carlin : Skeptics : Propaganda : SE quotes : Language Design and Programming Quotes : Random IT-related quotes : Somerset Maugham : Marcus Aurelius : Kurt Vonnegut : Eric Hoffer : Winston Churchill : Napoleon Bonaparte : Ambrose Bierce : Bernard Shaw : Mark Twain Quotes
Bulletin:
Vol 25, No.12 (December, 2013) Rational Fools vs. Efficient Crooks The efficient markets hypothesis : Political Skeptic Bulletin, 2013 : Unemployment Bulletin, 2010 : Vol 23, No.10 (October, 2011) An observation about corporate security departments : Slightly Skeptical Euromaydan Chronicles, June 2014 : Greenspan legacy bulletin, 2008 : Vol 25, No.10 (October, 2013) Cryptolocker Trojan (Win32/Crilock.A) : Vol 25, No.08 (August, 2013) Cloud providers as intelligence collection hubs : Financial Humor Bulletin, 2010 : Inequality Bulletin, 2009 : Financial Humor Bulletin, 2008 : Copyleft Problems Bulletin, 2004 : Financial Humor Bulletin, 2011 : Energy Bulletin, 2010 : Malware Protection Bulletin, 2010 : Vol 26, No.1 (January, 2013) Object-Oriented Cult : Political Skeptic Bulletin, 2011 : Vol 23, No.11 (November, 2011) Softpanorama classification of sysadmin horror stories : Vol 25, No.05 (May, 2013) Corporate bullshit as a communication method : Vol 25, No.06 (June, 2013) A Note on the Relationship of Brooks Law and Conway Law
History:
Fifty glorious years (1950-2000): the triumph of the US computer engineering : Donald Knuth : TAoCP and its Influence of Computer Science : Richard Stallman : Linus Torvalds : Larry Wall : John K. Ousterhout : CTSS : Multix OS Unix History : Unix shell history : VI editor : History of pipes concept : Solaris : MS DOS : Programming Languages History : PL/1 : Simula 67 : C : History of GCC development : Scripting Languages : Perl history : OS History : Mail : DNS : SSH : CPU Instruction Sets : SPARC systems 1987-2006 : Norton Commander : Norton Utilities : Norton Ghost : Frontpage history : Malware Defense History : GNU Screen : OSS early history
Classic books:
The Peter Principle : Parkinson Law : 1984 : The Mythical Man-Month : How to Solve It by George Polya : The Art of Computer Programming : The Elements of Programming Style : The Unix Hater’s Handbook : The Jargon file : The True Believer : Programming Pearls : The Good Soldier Svejk : The Power Elite
Most popular humor pages:
Manifest of the Softpanorama IT Slacker Society : Ten Commandments of the IT Slackers Society : Computer Humor Collection : BSD Logo Story : The Cuckoo's Egg : IT Slang : C++ Humor : ARE YOU A BBS ADDICT? : The Perl Purity Test : Object oriented programmers of all nations : Financial Humor : Financial Humor Bulletin, 2008 : Financial Humor Bulletin, 2010 : The Most Comprehensive Collection of Editor-related Humor : Programming Language Humor : Goldman Sachs related humor : Greenspan humor : C Humor : Scripting Humor : Real Programmers Humor : Web Humor : GPL-related Humor : OFM Humor : Politically Incorrect Humor : IDS Humor : "Linux Sucks" Humor : Russian Musical Humor : Best Russian Programmer Humor : Microsoft plans to buy Catholic Church : Richard Stallman Related Humor : Admin Humor : Perl-related Humor : Linus Torvalds Related humor : PseudoScience Related Humor : Networking Humor : Shell Humor : Financial Humor Bulletin, 2011 : Financial Humor Bulletin, 2012 : Financial Humor Bulletin, 2013 : Java Humor : Software Engineering Humor : Sun Solaris Related Humor : Education Humor : IBM Humor : Assembler-related Humor : VIM Humor : Computer Viruses Humor : Bright tomorrow is rescheduled to a day after tomorrow : Classic Computer Humor
The Last but not Least Technology is dominated by two types of people: those who understand what they do not manage and those who manage what they do not understand ~Archibald Putt. Ph.D
Copyright © 1996-2021 by Softpanorama Society. www.softpanorama.org was initially created as a service to the (now defunct) UN Sustainable Development Networking Programme (SDNP) without any remuneration. This document is an industrial compilation designed and created exclusively for educational use and is distributed under the Softpanorama Content License. Original materials copyright belong to respective owners. Quotes are made for educational purposes only in compliance with the fair use doctrine.
FAIR USE NOTICE This site contains copyrighted material the use of which has not always been specifically authorized by the copyright owner. We are making such material available to advance understanding of computer science, IT technology, economic, scientific, and social issues. We believe this constitutes a 'fair use' of any such copyrighted material as provided by section 107 of the US Copyright Law according to which such material can be distributed without profit exclusively for research and educational purposes.
This is a Spartan WHYFF (We Help You For Free) site written by people for whom English is not a native language. Grammar and spelling errors should be expected. The site contain some broken links as it develops like a living tree...
|
|
You can use PayPal to to buy a cup of coffee for authors of this site |
Disclaimer:
The statements, views and opinions presented on this web page are those of the author (or referenced source) and are not endorsed by, nor do they necessarily reflect, the opinions of the Softpanorama society. We do not warrant the correctness of the information provided or its fitness for any purpose. The site uses AdSense so you need to be aware of Google privacy policy. You you do not want to be tracked by Google please disable Javascript for this site. This site is perfectly usable without Javascript.
Last modified: December 29, 2018
