programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# It's a bird, it's a plane, no, it's a ... bubble sort?

Flo Powers
Ranch Hand
Posts: 57
Hi, I have a question about sorting methods. I have been using what I thought was a bubble sort (just for learning purposes), but on reading a bit about them I noticed that mine is not quite according to the recipe. Could what I have below be considered a version of a bubble sort, or is it a hybrid sorting algorithm, or is it perhaps some other inefficient sorting algorithm with a name I don�t know? In terms of Big O notation, would it rank somewhere on the same level as a bubble sort?

Thanks for enlightening me!

Francis Siu
Ranch Hand
Posts: 867
I have been using what I thought was a bubble sort

Please imagine that shaking a soft drink bottle,after shaking, the contents are a mixture of bubbles and soft drink, distributed randomly.
Because bubbles are lighter than the soft drink, they rise to the surface, displacing the soft drink downwards.
This is how bubble sort got its name, because the smaller elements continue "float" to the top, while the larger elements "sink" to the bottom.
Assume that left hand side is top and right hand side is bottom.
Using an example to illustrate
11,7,9,2,16,32,2,3
Step 1: 7,11,9,2,16,32,2,3 a[0]>a[1]
Step 2: 7,11,9,2,16,32,2,3 a[0]>a[2]
Step 3: 2,11,9,7,16,32,2,3 a[0]>a[3]
Step 4...............................

Do you think that the smaller elements continue "float" to the top, while the larger elements "sink" to the bottom?

In bubble sorting
Step 1: 7,11,9,2,16,32,2,3 a[0]>a[1]
Step 2: 7,9,11,2,16,32,2,3 a[1]>a[2]
Step 3: 7,9,2,11,16,32,2,3 a[2]>a[3]

Please notice the number 11 and you will know more about the bubble sorting.

Tom Hill
Ranch Hand
Posts: 115
You can have many different algorithms that come up with the same result. If the outcome is equivalent for all cases for two algorithms then then algorithms are equivalent in principle. The difference comes at runtime and efficiency of the algorithms. A fast Bubble sort will recognise that the last element(or first element) is already in the correct place, and will not compare it with the current element going through the list, for example.

Flo Powers
Ranch Hand
Posts: 57
Thanks to you both. As far as I could tell from testing my algorithm with inputting values in different orders (ascending, descending, mixed in various random'ish ways), it always resulted in the array being sorted in ascending order. However, I see the difference from the bubble sort now.

Thanks again.

Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
You've got more or less a selection sort here. Like bubble sort, it's an O(n^2) algorithm, but unlike bubble sort it always has worst-case performance -- i.e., bubble sort can finish in less that O(n^2) time for data which is already sorted or mostly sorted.

Here's a good Java implementation of bubble sort (from http://leepoint.net/notes-java/25data/35arrays/32arraybubblesort.html

In any case, do realize that O(n^2) sorting algorithms are the worst kind; quicksort, mergesort, and other O(n ln n) algorithms are vastly more efficient for sorting a nontrivial amount of data.
[ August 12, 2004: Message edited by: Ernest Friedman-Hill ]

Flo Powers
Ranch Hand
Posts: 57
But slightly more complex and less intuitive?

I like that version of a bubble sort. Elegant way of avoiding the use of the nested for-loop - I found it easier to trace in my mind, so to speak.

I've spent the last two hours studying insertion sort, selection sort and bubble sort, and was actually beginning to feel that my abhorration of an algorithm actually had more in common with the selection sort than the bubble sort, in that it starts at one end and compares with all the rest of the elements, and for each round of the outer loop swaps the current element (a[i] with the lowest element in the rest of the array (provided there is a later element that is lower).

However, does not my version above actually perform worse than the selection sort, in that it not only compares a[i] with all the later elements, but also swaps with every single element after it in the array that contains a lower value? I.e. there is unnecessary moving of data, as the algorithm doesn't wait until it has identified the lowest value in the rest of the elements of the array. Instead, the inner for-loop swaps with every element that is lower, until it has gone through the rest of the array.

I think...

Flo

Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Originally posted by Flo Powers:

However, does not my version above actually perform worse than the selection sort, in that it not only compares a[i] with all the later elements, but also swaps with every single element after it in the array that contains a lower value? I.e. there is unnecessary moving of data, as the algorithm doesn't wait until it has identified the lowest value in the rest of the elements of the array. Instead, the inner for-loop swaps with every element that is lower, until it has gone through the rest of the array.

Yes, I suppose you're right.

Flo Powers
Ranch Hand
Posts: 57
Thanks, all. This has been very educational.
Flo

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49

Fred said this, along with some other stuff:

If the data is already mostly sorted, quicksort is exceedingly slow. a bubble sort can be exceedingly fast in such cases.

And then I said:

This is absolutely true for naive implementations of quicksort -- if you choose the pivot element to be the center of an interval, for example, and if you use "qucksort all the way down." But it's possible to choose pivot elements more wisely, and also to switch from quicksort to insertion sort when the interval size gets small, and end up with something which virtually always avoids this worst-case behavior. The versions of java.util.Arrays.sort() which sort arrays of primitive types are quicksorts with these optimizations.
[ August 12, 2004: Message edited by: Ernest Friedman-Hill ]

fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
re: editing my post - not a problem

re: smart implementations of q-sort...

I should have known there were smarter people than me. My "real-world" case was actually on a VMS system in C. so who knows how the sort was actually implemented.

thanks for clarifying for me!!!

 It is sorta covered in the JavaRanch Style Guide.