7 Years
Discussion Span
Last Post by jephthah

The quicksort is a comparison sorting algorithm.

The shell sort is arranging the data sequence in a two-dimensional array and sorting the columns of the array.

The bubble sort algorithm works similar to bubbles finding their own level in water. It compares pair of array elements, moving the larger up.

The shaker algorithm sorts in both directions each pass through the list.


>Plz provide me complete discription of four algorithms used for sorting arrays e.g bubble sort.
How about you tell us what you came up with first, because this is clearly homework.

>Four bad sorts:

>bubble sort
Works for me.

>insertion sort
Insertion sort is not a bad sort. It's a quadratic sort, which means using it on larger lists is a bad idea. However, insertion sort is often the preferred finalizer for the higher performance algorithms. It's also one of the few algorithms that can sort streamed input.

>selection sort
I'll let you keep this one with the caveat that selection sort is good in special cases where data movement is extremely expensive because this algorithm is about as efficient as can be when it comes to copies.

>shell sort
This I disagree with. Shell sort is a mid-range algorithm, where one of the quadratics would be too slow but the overhead of the higher performance algorithms is prohibitive. Keep in mind that before quicksort came around, shell sort was one of the forerunners.


Four bad sorts:
bubble sort
insertion sort
selection sort
shell sort

I wouldn't call them "bad" sorts - it's all relative. In the days when processor speed was measured in MHz, sure, the first three would seem slow for data sets of any considerable size ( how big a problem do we ever do in an classroom?)

On modern machinery, what once was derided can now be satisfactory, for problems that are larger than we might ever have considered before.

Example - Pentium D, 3.2GHz, list size 10,000 integers.
Bubble sort (done well) takes about 2 seconds
Selection sort - about 1/2 second
Insertion sort - about 1/2 second.

Given that most situations are a sort once, search many times, is that such a huge price to pay? For the student writing the code, the simplicity of these sorts, the ability to easily understand how they function, still has merit.

You want "bad" sorts - look up bozosort or bogosort. Those are bad, really bad.


Excellent info, Narue and vmanes!
(I'm beginning to like being proved wrong.)
And wikipedia does have some decent info, especially the complexity tables.

This article has been dead for over six months. Start a new discussion instead.
Please be thoughtful and detailed and be sure to adhere to our posting rules.