BubbleSort VS SelectionSort

Bubblesort is actually used in real applications developed by professionals!

The advantage of bubblesort is Simplicity.

Bubblesort can be implemented in a short amount of time with a low risk of making any bugs. If you know that the number of elements is small and the performance is not an issue then bubblesort is a reasonable choice.

Normally though, you have access to libraries that can do the sorting for you.

If you have to implement the sorting yourself, then the general rule is to use quicksort.

Choose other sorting algorithms only when there is a special reason to do so, for example:

Insertion sort is fastest if you know that the amount of elements is very small.

If you have a grid of data sorted by one column and you resort it by another column, then mergesort preserves the order of equal elements.

Ragnvald_id2a at 2007-7-13 14:06:35 >

The complexities of BubbleSort and SelectionSort are - as far as i know - the same. The choice of a sortalgorithm normally bases on some properties of the data you have to sort. You should always chose the algorithm which works best with your data. So there is no general answer for this question. This is the reason, why sortalgorithms in collections are often hybrids. Some of them check the data first, and then branch depending on some metrics. You can spend some easy thoughts about that to improve your algorithm. For example: Perhaps it's better to search for the low numbers begining at the end of your data. You could easy check this with a metric. It makes sense to spend time analyzing data, because sorting data can take very...very...very long and differences in time depending on algorithms can be very huge :) but, as allready said before: you should better use some implementations of the java.util.Collections. (sort with the Comparator interface: it's very easy, and quick done!)

my favorite searchalgo, by the way, is heapsort. it's really simple and quiet fast for most datastructurs. (heapsort kinda builds on selection sort :))

p.s. sorry for the bad english, it's late and i'm tired... gn8 all!

commya at 2007-7-13 14:06:35 >

Maybe you are confusing selection sort with insertion sort?

Insertion sort is usually the preferable of the simple 0(n^2) algorithms.

Insertion sort is the fastest of the algorithms that work by comparing adjacent elements. It is also proven to be optimal (i.e. it is theoretically impossible to do better).

Insertion sort also has the properties that it is extremely fast for presorted (or almost presorted) data, and that it does not mess up any previous sorting by a different column.

It is often used as a cutoff algorithm for more advanced algorithms (like mergesort or quicksort).

Ragnvald_id2a at 2007-7-13 14:06:35 >

> Bubblesort is actually used in real applications

> developed by professionals!

>

> The advantage of bubblesort is Simplicity.

> Bubblesort can be implemented in a short amount of

> time with a low risk of making any bugs. If you know

> that the number of elements is small and the

> performance is not an issue then bubblesort is a

> reasonable choice.

The mainframe guys where I work use bubblesort extensively. The problem I see this that because some people have made the educated choice you desscribe above, other's are unaware that there are even other sort algorithms! I was at a meeting where they were using quicksort for lists that could contain thousands of items i.e. millions of reads required for a bubblesort. Given that there were thousands of these lists, this could be a huge problem but the designer/developers were resistant to even addressing the concern. For this reason, I would suggest that using bubblesort is not a good idea. If you don't have a sorting library, get one.

dubwaia at 2007-7-13 14:06:35 >

I actually prefer Shellsort for small arrays. It beats most implementations of quicksort on arrays < 1000 elements from what I've seen. And it is really simple to understand and code. It is basically an insertion sort that works on smaller and smaller granularities. Kinda like a series of ever decreasing sieves.

Here is a copy of the code i got from http://www.cs.bell-labs.com/cm/cs/pearls/SortAnim.java

The loops below are rather messy below, but you can reduce this down to just a couple lines by putting the break conditions in the for loops etc.

private void shellsort()

{int i, j, h;

for (h = 1; h < n; h = 3*h + 1)

;

for (;;) {

h /= 3;

if (h < 1) break;

for (i = h; i < n; i++) {

for (j = i; j >= h; j -= h) {

if (a[j-h] < a[j]) break;

swap(j-h, j);

}

}

}

}

The analysis greatly varies depending on the data and the choices of 'h'. The choices above (h = h*3+1) is "about as good as any for arrays less than 1000 elements" according to Knuth's Art of Computer Programming. It seems to be anywhere from O(n*lg(n)) to O(n*sqrt(n)) (tending towards the later).

--Zerothbase

zerothbasea at 2007-7-13 14:06:35 >