Sorting...?

This is a discussion on Sorting...? within the C++ Programming forums, part of the General Programming Boards category; What is a deterministic quick-sort? What are some good examples of quick-sort and merge-sort. I have like 3 algorithm books, ...

  1. #1
    Registered User
    Join Date
    Nov 2001
    Posts
    241

    Sorting...?

    What is a deterministic quick-sort? What are some good examples of quick-sort and merge-sort. I have like 3 algorithm books, but the pseudo-code is really bad for those sorts.

  2. #2
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,662
    Do a board search.



    ITSA
    Socket Library!

  3. #3
    Registered User
    Join Date
    Nov 2001
    Posts
    241
    You know, I did think of that, but only like 1% of my searches have ever come up with anything that could help me out, and I thought that I should just ask, since that is what I thought these board were for...maybe we just need a search, and eliminate postings, since by now people must have posted so much stuff that any question could be answered somewhere, but with all that info it can be EXTREMELY hard to find what you are looking for, when there is little AI in the search.

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Since you're asking, here's a quick sort I coded after reading a slide show from FSU (Florida State). It's recursive, so probably not the fastest. Maybe someone else has an example of a merge sort.
    Code:
    #include <cstdlib>
    #include <iostream>
    using namespace std;
    
    const int size = 30;
    
    int Partition( int table[], int first, int last );
    void quick_sort( int table[], int first, int last );
    void print( int a[], int size );
    
    int main(void)
    {
       int a[size]; 
       //{1,2,3,4,5,6,7,8,9,10};
       //{10,9,8,7,6,5,4,3,2,1};
       
       srand(unsigned(time(NULL)));
       for (int i=0; i<size; i++)
          a[i] = rand() * 100 / RAND_MAX;
       print( a,size );
    
       quick_sort( a,0,size-1 );
       print( a,size );
    
       return 0;
    }
    
    void quick_sort( int table[], int first, int last )
    {
       if (first < last)
       {
          int pivot_index = Partition( table,first,last );
          quick_sort( table,first,pivot_index-1 );
          quick_sort( table,pivot_index+1,last );
       }
    }
    
    int Partition( int table[], int first, int last )
    {
          int temp;
          int pivot = table[first];
          int up = first;
          int down = last;
          do {
             while (table[++up] <= pivot);
             while (table[down] > pivot)
                down--;
             if (up < down)
             {
                temp = table[up];
                table[up] = table[down];
                table[down] = temp;
             }
          } while (up < down);
          //Exchange the pivot value and the value in down
          temp = table[first];
          table[first] = table[down];
          table[down] = temp;
          int pivot_index = down;
          return pivot_index;
    }
    
    void print( int a[], int size )
    {
       for (int i=0; i<size; i++)
       {
          cout << a[i] << " ";
          if ((i+1)%10 == 0)
             cout << endl;
       }
       cout << endl;
    }

  5. #5
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >What is a deterministic quick-sort?

    I have no clue.

  6. #6
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    By the way I think Prelude has written a Sort tutorial somewhere. I'm not sure where it is.

  7. #7
    Registered User
    Join Date
    Nov 2001
    Posts
    241
    I guess that the quick sort splits the list into lists of five or less, and then finds the median, then the medians of the medians, and then chooses a pivot....Every time it runs, which at least to me seems to be a complete waste of time

  8. #8
    Registered User
    Join Date
    Aug 2001
    Posts
    244
    >> It's recursive, so probably not the fastest.
    Quicksort IS recursive - its a good example how a recursive solution to sorting can be in general faster than any other sorting method.
    mergesort has same complexity as quicksort O(n*log(n))
    but you can't implement mergsort in a single array thus you have to allocate memory all the time.

    quicksort can be implemented to work on a single array.

    >> I guess that the quick sort splits the list into lists of five or less, and then finds the median, then the medians of the medians, and then chooses a pivot....Every time it runs, which at least to me seems to be a complete waste of time

    No, its not a waste of time:

    Quicksort takes an pivot element and shifts all values less than that pivot to one side of the pivot, and all values greater than that pivot to the other side of the pivot.

    thus the pivot reaches its final position in the sorted array!

    now we repeat that step with the array of the left and right side of the pivot until there are only 1 elements in those sub arrays.
    then we are done.

    so the recursion implicitly creates a tree-structure for sorting.
    complexity is also in average O(n*log(n))
    BUT if you take bad pivots (always the smallest or larges element) the complexity becomes worst-case O(n^2)
    signature under construction

  9. #9
    Obsessed with C chrismiceli's Avatar
    Join Date
    Jan 2003
    Posts
    501
    Help populate a c/c++ help irc channel
    server: irc://irc.efnet.net
    channel: #c

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >What is a deterministic quick-sort?
    Quicksort chooses a pivot for partitioning of the list. A deterministic quicksort will use a heuristic to find that pivot (Median of three partitioning is an example of such a heuristic) while a probabilistic quicksort will randomly select a pivot and rely on probability to minimize the worst cases.

    You can find code for various types of quicksort and mergesort all over the web. Google for sorting demos, they offer the source code (usually in Java, but that shouldn't be a problem) for you to read.
    My best code is written with the delete key.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21