• Post Reply Bookmark Topic Watch Topic
  • New Topic

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

 
Flo Powers
Ranch Hand
Posts: 57
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Your sorting will be
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks, all. This has been very educational.
Flo
 
fred rosenberger
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ahhh, sorry, Fred, I edited your post instead of replying.

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
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!