Thread: Sorting

  1. #1
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683

    Sorting

    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

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    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.
    My best code is written with the delete key.

  3. #3
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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.
    Last edited by DavidP; 11-08-2003 at 04:57 PM.
    My Website

    "Circular logic is good because it is."

  4. #4
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    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 .
    Do not make direct eye contact with me.

  5. #5
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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:

    Code:
    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.
    My Website

    "Circular logic is good because it is."

  6. #6
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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
    My Website

    "Circular logic is good because it is."

  7. #7
    The Defective GRAPE Lurker's Avatar
    Join Date
    Feb 2003
    Posts
    949
    Thank you for the explanation - that is basically what I expected, but you never know .
    Do not make direct eye contact with me.

  8. #8
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>
    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.

  9. #9
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    >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.
    My Website

    "Circular logic is good because it is."

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.

  11. #11
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    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.
    Last edited by DavidP; 11-10-2003 at 12:33 AM.
    My Website

    "Circular logic is good because it is."

  12. #12
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>
    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.

  13. #13
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    That is true, because it must constantly create new arrays.
    My Website

    "Circular logic is good because it is."

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 01:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 02:14 AM
  3. sorting structure members using pointers
    By robstr12 in forum C Programming
    Replies: 5
    Last Post: 07-25-2005, 05:50 PM
  4. Still Needing Help : selection sorting
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 10-14-2001, 08:41 PM
  5. selection sorting
    By Unregistered in forum C Programming
    Replies: 5
    Last Post: 10-13-2001, 08:05 PM