PDA

View Full Version : Sorting



vasanth
11-08-2003, 11:40 AM
Guys i need this little info...


What are the easy to implement sorting algorithms both Iterative and Recursive execpt bubble sort.. And please specify wheather its recursive or iterative...


Waiting for reply's
bye

Prelude
11-08-2003, 12:09 PM
The general elementary sorting methods excluding Bubblesort are Insertion sort, Selection sort and Shellsort, then there are variations on those three themes (Shellsort is a variation of Insertion sort for example). All of them are typically iterative, though it's certainly possible to do them recursively. As for easy to implement, it really depends on what level you're at. I have no problem writing an iterative quicksort or mergesort, but many people would find writing something like that without references or sample code a hopeless endeavor.

But, the above elementary sorts are trivial to write. I hope that answers your question.

DavidP
11-08-2003, 04:49 PM
The most popular sorts are:

Bubble sort - iterative - O(n^2)
Insertion sort - iterative - O(n^2)
Selection sort - iterative - O(n^2)
Shell sort - iterative - O(n^2)
Radix sort - iterative - O ( k * N )
Bucket sort - iterative - O ( n )
Quick sort - recursive - O ( n log n )
Merge sort - recursive - O ( n log n )
Heap sort - recursive - O ( n log n )

The radix sort is rarely used, although it is interesting look at.

The bubble sort, quick sort, and merge sort are the most popular.

The bucket sort is awesome if you use it right, however, it has slightly limited capabilities.

The quick sort is fairly easy to implement. So are the selection and insertion sorts. The merge sort is quite easy to implement.

The bucket sort is incredibly easy to implement.

The heap sort is not very common, so I do not know how easy it is to implement. The radix sort and shell sort are also less common than the others.

Lurker
11-08-2003, 07:55 PM
Sorry to stray from the topic a bit, but can someone explain these in a little more detail, such as more about what this sorting is, well, sorting? Thanks for helping an inquisitive idiot :D .

DavidP
11-08-2003, 08:40 PM
In response to Lurker:

The purpose of a sort is to sort something, obviously. Most often times you are sorting arrays when using a sort.

Take the following array of numbers for example:

int a[10] = { 1, 8, 3, 4, 7, 2, 9, 5, 0, 6 };

A sort would put it in order. You could put it in backwards order, forwards order, etc.

0 1 2 3 4 5 6 7 8 9

or

9 8 7 6 5 4 3 2 1 0

The easiest sort to implement is the bubble sort:



for ( int k = 0; k < arrayLength; k++ )
{
for ( int j = 0; j < k; j++ )
{
if ( array[k] > array[j] )
{
temp = array[k];
array[k] = array[j];
array[j] = temp;
}
}
}


Two other sorts are the insertion sort and selection sort...but they are just as slow as the bubble sort and more confusing than the bubble sort, so I see no point to them, so I will not explain those sorts. These 3 sorts are the most commonly known O(n^2) sorts.

The next group of sorts is the O ( n log n ) sorts. These consists of the Quick Sort, Merge Sort, and Heap Sort. The merge and quick sorts are the most common of the 3.

The idea is the same in both the mere and quick. Divide and conquer.

Take our array:

int a[10] = { 1, 8, 3, 4, 7, 2, 9, 5, 0, 6 };

The quick sort would choose a pivot element, most commonly either the first element, middle element, or the last element of the array. I personally like to use the middle element.

It would then check every element in the array to see if it is less than or greater than the pivot element.

All elements that contain data that is less than the pivot element go on the left hand side of it, all elements that contain data that is greater than the pivot element go on the right hand side, as seen here (usng 7 as the pivot element):

int a[10] = { 1, 8, 3, 4, 7, 2, 9, 5, 0, 6 };

1 3 4 2 0 6 5 7 9 8

We then divide two ways and choose two more pivot elements, for example 9 and 4.

1 3 2 0 4 6 5 7 8 9

We then choose more pivot points. Since the right side of our array is sorted, we do not do anything to it.

Take the pivot points 6 and 2.

1 0 2 3 4 5 6 7 8 9

And our last pivot point is 0.

0 1 2 3 4 5 6 7 8 9

The merge sort works in a likewise manner, only slightly differently.

The bucket sort is the fastest of all of the sorts, however, it has limited usage. The bucket sort creates a second array, iterates through the initial array, and puts everything in its slot.

int a[10] = { 1, 8, 3, 4, 7, 2, 9, 5, 0, 6 };

int sortedarray[10];

the bucket sort would look at the first element, which is a 1, and therefore simply put it in array index 1 of sortedarray.

for ( int k = 0; k < arrayLength; k++ )
{
sortedarray[ a[k] ] = a[k];
}

That is one method of doing it. However, that method does not allow duplicates. Take this array for example:

int a[10] = { 2, 8, 2, 4, 2, 2, 9, 5, 2, 6 };

In this case we would have to implement the bucket sort like thus:

for ( int k = 0; k < arrayLength; k++ )
{
sortedarray[ a[k] ]++;
}

This would count how many of each number we had in our original array. We could then use this data to create a new array, already sorted.

The heap sort is not commonly used, however it has its uses. If you want to learn about it, www.google.com

The same with the shell and radix sorts.

The radix sort is probably the least commonly used sort out of all of the sorts. It is kind of weird. It doesnt do any comparisons. It is quite fast though.

DavidP
11-08-2003, 09:08 PM
I just found a very nice website:

http://www.nist.gov/dads/

It defines almost every sort imaginable.

From what i see it defines the following sorts:


Quick Sort
Heap Sort
Shell Sort
Radix Sort
Bucket Sort
Insertion Sort
Selection Sort
Merge Sort
Counting Sort
Histogram Sort
Strand Sort
J Sort
Shuffle Sort
American Flag Sort
Bubble Sort
Bidirectional Bubble Sort
Adaptive Heap Sort
Three-Way Radix Sort
Lucky Sort
Bogo Sort
Bozo Sort
Stooge Sort

Lurker
11-08-2003, 09:37 PM
Thank you for the explanation - that is basically what I expected, but you never know :D .

Perspective
11-09-2003, 04:10 PM
>>
insertion sort and selection sort...but they are just as slow as the bubble sort and more confusing than the bubble sort, so I see no point to them
<<

actually insertion sort is lower bound by 'N' while bubble sort is lower bound by 'N^2'. Insertion sort can be very handy when the set is partailly sorted.


*note, heap sort IS the greatest thing since sliced bread.

DavidP
11-09-2003, 06:01 PM
>Insertion sort can be very handy

You are correct there. The insertion sort does pretty much kill every other N^2 sort except the shell sort.

>heap sort IS the greatest thing since sliced bread

The heap sort is the slowest of all of the O(n log n) sorts.

The fastest of the n log n's is the merge sort. It kills the quick sort and heap sort easily.

The heap sort and quick sort often times tie in speed. The merge sort is O(n log n) best case, average case, and worst case. The others are O(n log n) best case and average case, but not worst case.

The bucket sort is awesome, but is limited. It is not a good sort to use if you have arrays with large numbers in them. But if you have an array with relatively small numbers, the bucket sort is definitely the best sort out there.

laserlight
11-10-2003, 12:03 AM
The fastest of the n log n's is the merge sort. It kills the quick sort and heap sort easily.
hmm... this site claims that quick sort tends to be faster than merge sort, if we're looking at time rather than at complexity:
http://linux.wku.edu/~lamonml/algor/sort/sort.html

I suppose that in the end it really depends on the requirements of the problem to be solved.

DavidP
11-10-2003, 12:15 AM
The merge sort is O(n log n) across the board.

The quick sort CAN kill the merge sort if it picks an excellent pivot point, however, this is usually not the case.

The quick sort has a worst case of O(n^2) because the pivot point it picks might not be the best one.

So in most cases the merge sort will kill the quick sort.

Some quick sort algorithms use Partition-of-Three partitioning or a Quick Select algorithm to try and choose a good pivot point.

This will significantly speed up the quick sort in some cases and decrease the case of an O(n^2) quick sort.

http://cg.scs.carleton.ca/~morin/misc/sortalg/

Go to that site. You can watch sorts race each other.

Don't take me wrong though. I love the quick sort. It has always been one of my favorite sorting algorithms since the 9th grade.

Perspective
11-10-2003, 03:32 PM
>>
The heap sort is the slowest of all of the O(n log n) sorts
<<

true but its an in place sort. merge sort (in general) is a memory hog.

DavidP
11-10-2003, 05:21 PM
That is true, because it must constantly create new arrays.