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.

Do a board search.

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.

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;
}

---

>What is a deterministic quick-sort?

I have no clue.

By the way I think Prelude has written a Sort tutorial somewhere. I'm not sure where it is.

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

>> 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)

prelude's sort
http://faq.cprogramming.com/cgi-bin/...&id=1073086407

>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.