Wikipedia:Reference desk/Archives/Computing/2017 January 2

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 2

Bubble Sort vs. Insertion Sort

Hi,
Are there any assumptions or any case, in which there is an advantage to bubble sort over insertion sort?
Thanks — Preceding unsigned comment added by 132.66.85.42 (talk) 13:06, 2 January 2017 (UTC)

Bubblesort looks better animated (IMHO). --Stephan Schulz (talk) 13:22, 2 January 2017 (UTC)

Bubble sort is easier for beginner programmers to write and isn't necessarily bad if the sets are small. If I've already taught arrays, I use bubble sort to show how for loops work when I get to that topic. I then use two for loops and do insertion sort. You'd be amazed at how much harder it is for beginners to comprehend two for loops. So, I would say that beginners might use bubble sort because they know how to write it and they know that the context of the sort is over small sets, so it won't hurt anything. 209.149.113.5 (talk) 18:04, 2 January 2017 (UTC)

Links to related articles: Bubble sort, Insertion sort. -- ToE 03:29, 3 January 2017 (UTC)

Bubble sort may be nice for educational purposes, but other simple algorithms perform better. For a more elaborate answer read the wikipedia article Sorting algorithm. Jahoe (talk) 12:44, 3 January 2017 (UTC)

Note that the simplicity of the bubble sort makes it less likely to contain errors, or need maintenance or updating should the data change (other than the number of records), etc. It could also be faster in a case where you do something between the two loops. For example, say you are sending individually customized emails ("Dear Mr Johnson...") out to customers, in alphabetical order, from a list that's not sorted. You could find the first name in the first pass, send that email, then find the 2nd name in the 2nd pass, send that email, etc., rather than having to sort all the records before sending out the first email. Also, the slight delay between sending each email as it takes another sorting pass may be beneficial, if it prevents emails from stacking up and overflowing a queue. StuRat (talk) 18:54, 4 January 2017 (UTC)

Well, standard bubble sort is guaranteed to move the biggest not-yet correct element into position on every iteration of the outer loop. So Mr. Zyhng would get the email before Mr. Abelson. Also, standard bubble sort will terminate when there have been no exchanges during an iteration of the inner loop, so Mr. Abelson might be out of luck completely. But on a more general level: Writing intentionally bad algorithms to avoid overwhelming a downstream system is very bad design. If you have a flow constraint, than implement it with explicit waiting on a clock. Otherwise you are in trouble when someone switches out the old Pentium 3 for a current i7. And to go back to bubble sort: Any reasonably good implementation of bubble sort with shorten the inner loop by one after each iteration, so your delay between emails also shrinks... --Stephan Schulz (talk) 08:00, 5 January 2017 (UTC)

It's simple enough to swap an ascending sort order to descending and to remove the early exit check. For another example, you might display a line on the screen after each run of the outer loop, thus avoiding the annoying delay before the list begins to display, while the sort runs. Thus, even though the total sort time is longer, it would seem shorter because lines would start to display sooner, and the users would be happier. This is similar to a complaint I have about the way many web pages load. They keep jumping all over the places as pics at the top load and resize after lower text was loaded, making it impossible to read until it is complete. If they would load the page in order, from the top down, I could read the top while the rest loads. StuRat (talk) 03:57, 6 January 2017 (UTC)