Quicksort's recursion

Good afternoon. I understand recursion but I don't know how the last two instructions of quick sort (the recursive ones) work.

Code:

---


#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#ifndef MAXSIZE
  #define MAXSIZE 10
#endif 

void swap(int*, int*);
void quicksort(int*, int);

void swap(int* a, int* b)
{
  int temp;
 
  temp = *a;
  *a = *b;
  *b = temp;
}

void quicksort(int* a, int size)
{
  int pivot, left, right;
  left = 0;
  right = size - 1;
 
  srand(time(NULL)); 
 
  if(size < 2)
    return;
  pivot = a[rand() % size];
  while(left < right)
  { 
    while(a[left] < pivot)
      left = left + 1;
    while(a[right] > pivot)
      right = right - 1;
    swap(&a[left], &a[right]);   
  }         
 
  /* I don't know how the recursions below work. */
 
  /* ---------------------------------------------------------- */
  quicksort(a, left);
  quicksort(&a[left + 1], size - left - 1);   
  /* ---------------------------------------------------------- */

}

int main(void)
{
    int i;
    int a[MAXSIZE] = {23, 45, 67, 12, 89, 77, 34, 11, 9, 2};
   
    printf("The unordered array: ");
    for(i = 0; i < MAXSIZE; i++)
      printf("%d ", a[i]); 
    putchar('\n');
   
    quicksort(a, MAXSIZE);
    printf("Array after quick sort: ");
    for(i = 0; i < MAXSIZE; i++)
      printf("%d ", a[i]);
    putchar('\n'); 
   
    return 0;   
}

---

Before the recursive calls, you have taken an array, and partitioned it into two parts - one with values above the pivot, and one with values below the pivot. In the recursive calls, each of those two sub-arrays will themselves, be partitioned into two sub-arrays, according to the new pivot value.

The splitting will continue until the number of elements is just two. After that, the sub-array will be sorted, and the return(s) will be made from the recursive calls. The beauty of it is the way that the stack handles the returns so naturally. This looks like magic compared to Quicksort which is coded up without recursive calls.

srand() should be made once, in main(), before the recursive function.

Many thanks Adak.

I'd like to point out a couple of things. First:

Quote:

---

Originally Posted by thames

Code:

---

  srand(time(NULL)); 
 
  pivot = a[rand() % size];

---

---

The above is wasteful. On every invocation, you'll reinitialize the random number generator, based on the current time in seconds. Because the function is called recursively, it will be called in rapid succession, and the rand() will always return the same value. So, it does not really yield a random pivot.

The median-of-three pivot selection is found to be just as good in practice. Basically, you take the first (a[0]), middle (a[size/2]), and last value (a[size-1]), sort the three, and use the middle one (the median of the three) as the pivot.

Second, your loop which moves values less than pivot to the beginning of the array and values greater than the pivot to the end of the array, does not handle pivots correctly. If you supply it with an array containing repeated values, like 1, 5, 1, 1, 5, 2, 2, 4, 4, 4, it will get stuck (at least some of the time).

You need to decide what you do with the pivot values and handle them accordingly.

The typical approach is to first swap the pivot with the final element in the array. After you have sorted the left side of the array, you swap the pivot just after the left side, and sort the rest of the array (not including the pivot). To do that, you can either swap a random index with the final element in the array and take the pivot value from the final element, or use the median-of-three pivot selection in a way that puts the middle value at the end of the array. I warmly recommend the median-of-three pivot selection over random pivot selection.

Quote:

---

On every invocation, you'll reinitialize the random number generator

---

I put srand(time(NULL)) inside main as Adak suggested. I didn't see a median-of-three pivot selection yet. I'd appreciate if you could point to a link which shows the implementation you mentioned (since there are many algorithms. Besides, KnR quicksort's implementation is different from the one I chose).

Quote:

---

Originally Posted by thames

I put srand(time(NULL)) inside main as Adak suggested.

---

Yes, that is the correct location, when you use a random pivot selection.

I don't think Adak noticed the issue with repeated pivots: your code sometimes gets stuck, if there are repeated numbers in the array.

See the Wikipedia article on Quicksort, in particular the pseudocode for the in-place Quicksort, as the paragraph following the pseudocode explains exactly how that is solved by moving the pivot to the end of the array, and swapping it back just before sorting the right side.

Quote:

---

Originally Posted by thames

I didn't see a median-of-three pivot selection yet.

---

I'm sure you'll find a reference to it in your book. If not, then just search for it.

It really is as simple as it sounds: you pick the median (middle value) of the first, middle, and last values of the array, as your pivot.

Like I said, you should do it in a way that puts the middle value of the three at the end of the array, and uses that value as the pivot.

If a[0] is between a[middle] and a[right], then a[0] is the median, and you swap a[0] and a[right].
If a[middle] is between a[0] and a[right], then a[middle] is the median, and you swap a[middle] and a[right].
Otherwise a[right] is the median of the three, and you let it be where it is:

Code:

---

    left = size / 2;

    /* Swap the median of a[0], a[left], a[right], with a[right]. */
    if ((a[0] <= a[left] && a[0] >= a[right]) ||
        (a[0] >= a[left] && a[0] <= a[right]))
        swap(&a[0], &a[right]); /* a[0] was the median */
    else
    if ((a[left] <= a[0] && a[left] >= a[right]) ||
        (a[left] >= a[0] && a[left] <= a[right]))
        swap(&a[left], &a[right]); /* a[left] was the median */
    /* else no swap needed, since a[right] is the median. */

    pivot = a[right];
    left = 0;

---

In your partitioning loop, you need to accept pivots on the right side, or the while loop will get stuck, if it encounters a pivot on the left side. (Your current code will just swap the pivot between a[left] and a[right], ad infinitum, without increasing left or decreasing right. That's how it gets stuck.)

Your second inner while clause will have to be (left < right && a[right] >= pivot) , since you cannot assume left side does not contain pivots. Unless you verify (left < right), you might fall out from the left side, if the first value on the left side matches the pivot or there are no values smaller than the pivot in the array!

Before recursing into the right side, you need to swap the pivot back, i.e. swap(&a[left], &a[size-1]); . Your current recursive calls are correct, since that will move the pivot back to its correct position between the two sides, and the latter call sorts the rest of the array, i.e. elements a[left+1] to a[size-1], inclusive.

I did verify your code by applying the above changes, then running a large set of random arrays, verifying the code produces the correct, expected results. (Like I said, your current code sometimes gets stuck if the array contains repeated values.) I'm sure you can modify your code accordingly; it should not be too difficult.

I don't move the pivot out of the way with Quicksort - although that is the classic way of handling it.

Sorting program with three rounds of sorting: random, ascending, and descending integers, each round is sorted by Bubble sort, Insertion sort, Quicksort, Optimized Quicksort, and Shell sort.

In the second round, notice how Bubble and Insertion sort, ROCK!

Code:

---

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INSERT 64
#define SIZE  100000

void bubbleSort(void);
int checkIt(void);
void insertionSort(int lo, int hi);
void quicksortOpt(int lo, int hi, int optimal);
void fillArray(void);
void shellSort(void);
void swap(int i, int j); 

int A[SIZE]={0};
unsigned long long int SWAPS=0;
int TYPE=0;

int main(void) {
  int i,j;
  char type[3][11]={{"random"},{"ascending"},{"descending"}};
 
  clock_t start,stop;

  for(j=0;j<3;j++) {
      TYPE=j;
      fillArray();
      printf("\nSorting %d integers, initially in %s order. The first 10 numbers:\n\n",SIZE,type[TYPE]);
      for(i=0;i<10;i++)  printf("%6d  ",A[i]);
      printf("\n");
 
      SWAPS=0;
      start=clock();
      bubbleSort();
      stop=clock();
      printf("        Bubble sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
      if(checkIt());

      SWAPS=0;
      fillArray();
      start=clock();
      insertionSort(0,SIZE);
      stop=clock();
      printf("    Insertion sort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
      if(checkIt());

      SWAPS=0;
      fillArray();
      start=clock();
      quicksortOpt(0,SIZE-1, 0);
      stop=clock();
      printf("          Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
      if(checkIt());

      SWAPS=0;
      fillArray();
      start=clock();
      quicksortOpt(0,SIZE-1, 1);
      stop=clock();
      printf("Optimized Quicksort: %15llu swaps in %10.4f seconds\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
      if(checkIt());

      SWAPS=0;
      fillArray();
      start=clock();
      shellSort();
      stop=clock();
      printf("        Shell sort: %15llu swaps in %10.4f seconds\n\n",SWAPS,(double)(stop-start)/CLOCKS_PER_SEC);
      if(checkIt());
  }

  for(i=0;i<10;i++)
      printf("%6d  ",A[i]);
 
 
  printf("\n");
  return 0;
}
//Standard and Optimized Quicksort
void quicksortOpt(int lo, int hi, int optimal) {
  int i, j, pivot;
  if(lo == hi) return;

  if(optimal && (hi - lo) < INSERT) {  //The optimizer. Value of
    insertionSort(lo, hi+1);          //INSERT will vary
    return;
  }

  i=lo;
  j=hi;
  pivot= A[(lo+hi)/2];

  /* Split the array into two parts */
  do {   
      while (A[i] < pivot) i++;
      while (A[j] > pivot) j--;
      if (i<=j) { 
        swap(i, j);  //this line works fine.
        SWAPS++;
        i++;
        j--;
      }
  } while(i<=j);
 
  if (lo < j) quicksortOpt(lo, j,optimal);
  if (i < hi) quicksortOpt(i, hi,optimal);
}
void bubbleSort() { 
  int i, n, swapped;
  n = SIZE-1;
  do {
      swapped = 0;
      for(i =0; i < n; i++) { 
        if(A[i] > A[i + 1 ]) {
            swap(i, i + 1);
            SWAPS++;
            swapped = 1;
        }
      }
      --n;
  }while(swapped);
}
void insertionSort(int lo, int hi) {
  int i, j, val;
  for(i=lo+1;i<hi;i++) { 
      val = A[i];
      j = i-1;
      while(A[j]>val) {
        A[j + 1] = A[j];
        ++SWAPS;
        --j;
        if(j<0)
            break;
      } 
      A[j+1] = val;
  }
}
//Shell sort
void shellSort(void) {
  int i, j, gap, temp;
  for(gap = SIZE/2; gap > 0; gap /= 2) {
    for(i = gap; i < SIZE; i++) {
      for(j = i - gap; j >= 0 && A[j] > A[j + gap]; j -= gap) {
              ++SWAPS;
        temp = A[j];
              A[j] = A[j + gap];
        A[j + gap] = temp;
      }
    }
  }
}
void swap(int i, int j) {   
  int temp;
  temp = A[i];
  A[i] = A[j];
  A[j] = temp;
}
void fillArray(void) {
  int i,j;
  if(TYPE==0) {        //random order
      for(i = 0; i < SIZE; i++)
        A[i] = (rand() % 10000)+1;
  }else if(TYPE==1) {  //ascending order
      for(i=0;i<SIZE;i++)
          A[i]=i;
  }else if(TYPE==2) {  //descending order
      for(j=0,i=SIZE-1;i>=0;i--,j++)
        A[j]=i;
  }
}
int checkIt(void) {
  int i;
  for(i=0;i<SIZE-1;i++) {
      if(A[i]>A[i+1]) {
        printf("Error! Not sorted in ascending order.\n");
        return 1;
      }
  }
  return 0;
}

---

Quote:

---

Originally Posted by Adak

I don't move the pivot out of the way with Quicksort

---

Oh no, that's not what I meant. I meant that in post #2, you did not notice that thames' code will get stuck (never complete) if the pivot occurs more than once in the array.

Quote:

---

Originally Posted by Adak

Sorting program with three rounds of sorting: random, ascending, and descending integers, each round is sorted by Bubble sort, Insertion sort, Quicksort, Optimized Quicksort, and Shell sort.

---

No selection sort?

I prefer to use selection sort (instead of insertion sort) for small lists (< 32 elements, typically, if sorting ints), especially with quicksort.

For quicksort, in cases when I know there is a lot of repeated values, I like to delete the pivots, then insert them back between the sorted arrays afterwards. It seems to give a speed boost (due to reduced recursion) when there are relatively many pivot values, but the added code complexity may make it a bit slower than a typical optimized quicksort.

Hey, how about we start a thread comparing sort function implementations? Perhaps in the contest board? Combining some of our approaches we might arrive at something even better? (Yeah, I'm bored.)

Quote:

---

Originally Posted by Nominal Animal

Oh no, that's not what I meant. I meant that in post #2, you did not notice that thames' code will get stuck (never complete) if the pivot occurs more than once in the array.

---

I noticed the i < j, instead of i <= j, part. That always gets my version of Quicksort, into a snit - but then I thought "if he was getting stuck in an infinite loop, he'd mention it". When he's ready.

I didn't run his program, however.

Quote:

---

No selection sort?

I prefer to use selection sort (instead of insertion sort) for small lists (< 32 elements, typically, if sorting ints), especially with quicksort.

---

I've always found Selection sort to be the simplest sorting algorithm, (inuitively, it gets a 10), but unfortunately, it's always been the slowest one also. I've never took a liking to it, for that reason. Aside from the low number of swaps it makes, I don't know anything to recommend it.

On small (say less than 64) number of items, especially if they're partly sorted, you can't beat Insertion sort, AFAIK. That's why it works so well with the small sub-arrays from recursive Quicksort.

Quote:

---

For quicksort, in cases when I know there is a lot of repeated values, I like to delete the pivots, then insert them back between the sorted arrays afterwards. It seems to give a speed boost (due to reduced recursion) when there are relatively many pivot values, but the added code complexity may make it a bit slower than a typical optimized quicksort.

---

Quote:

---

Hey, how about we start a thread comparing sort function implementations? Perhaps in the contest board? Combining some of our approaches we might arrive at something even better? (Yeah, I'm bored.)

---

My plates piled high right now. I've got a decade old chess game I want to dig into (if I can find it), a Milestone program for my folding@home team, to revise, and my latest idea is to see if I can gather up a frequency word list of British GI's messages in WWII, and possibly decode a pigeon's message that was just found on the dead pigeon's leg, in a chimney in England. (a far fetched idea, I'll grant)

Can't help your boredom, I'm afraid. There's always Project Euler, SPOJ, and Code Chef. :cool:

And learning Go - an interesting language, imo.

I tried to follow Wikipedia's in-place version however my code isn't working:

Code:

---

#include <stdio.h>
#include <stdlib.h>

void swap(int*, int*);
void quicksort(int*, int, int);
int partition(int*, int, int, int);
int getMedian(int* a);

int partition(int* a, int left, int right, int pivotIndex)
{
  int pivotValue, storeIndex, i;
 
  pivotValue = a[pivotIndex];
  swap(&a[pivotIndex], &a[right]);   
  storeIndex = left;
  for(i = left; i < right - 1; i++)
  { 
    if(a[i] < pivotValue)
    { 
      swap(&a[i], &a[storeIndex]);
      storeIndex = storeIndex + 1;
    }
  }
 
  swap(&a[storeIndex], &a[right]);     
  return storeIndex;
}   

int getMedian(int* a)
{
  int i, nElems;
  nElems = 0;
 
  for(i = 0; a[i] != '\0'; i++)
    nElems++;
 
  return (nElems % 2 == 0) ? (nElems + 2) / 2 :  (nElems + 1) / 2;
}   


void quicksort(int *a, int left, int right)
{
  int pivotIndex;
  if(left < right)
  {
      pivotIndex = getMedian(a);
      pivotIndex = partition(a, left, right, pivotIndex);
      quicksort(a, left, pivotIndex - 1);
      quicksort(a, pivotIndex + 1, right);     
    }           
}   

void swap(int* a, int* b)
{
  int temp;
 
  temp = *a;
  *a = *b;
  *b = temp;
}

#ifndef MAXSIZE
  #define MAXSIZE 10
#endif

int main(void)
{
  int i;
  int a[MAXSIZE] = {13, 13, 2, 2, 6, 7, 9, 8, 25, 11};
 
  printf("Unordered elements: ");
  for(i = 0; i < MAXSIZE; i++)     
    printf("%d ", a[i]);
  putchar('\n');
 
  quicksort(a, a[0], a[MAXSIZE - 1]);
  printf("Array after quicksort: ");
  for(i = 0; i < MAXSIZE; i++)     
    printf("%d ", a[i]);
  putchar('\n');
 
  return 0;   
}

---

Whenever I think of Quicksort, I picture a hundred kids out on the school yard, waiting to be sorted by height.

Two kids in red sweaters are standing by at each end of the long straight line. A teacher puts a gold colored hat on a kid somewhere near the middle of the line, and the two kids in red sweaters, start walking down the line toward each other, comparing each kid's height, to the height of the pivot kid with the golden cap.

When each of the red sweater kids have found someone, they yell "swap", and the two kids they're next to, go running to the other's position in the line. That continues until the two red sweater kids, meet.

Now the entire line left of the meeting spot of the kids, takes a big step forward, and the red sweater kids run to get back into their places at the end of the new "line" of kids. Meanwhile, a new pivot student is chosen, and given the golden cap to wear. Now the partitioning continues anew, with this line.

Finally, the new line consists of just one or two students in the line, and they are partitioned by height, as well. Now this short line takes one big step backward, and rejoins the next to last line. Right back into the right place. (the beauty of the stack). This step back is repeated several times, until the entire student line has been reassembled.

But now it's all sorted. :cool:

First, everybody uses Quicksort for in-place sorting. I've never heard it even mentioned as an external/auxiliary memory sorting algorithm. So that first algorithm in Wiki is "on the right ladder, but learning against the wrong house". :(

Second, you don't want to count all the values in the array, before you choose a pivot - you'll be slowing it down a lot on big arrays, because every sub-array has to have a pivot selected, not just the first array. And Quicksort is used for big arrays - you can use Shell or Insertion sort for smaller sorting jobs.

Third, the pseudo code they go into, is useful to help illustrate their discussion, not to make a coherent practical program. There is no reason to make Quicksort into 3 functions. If you're going to make it so onerous to use it, then very few people would bother with it. That's the problem with FLASH sort and Comb sort - they work fine, but they're way to long to be practical - and can't beat Quicksort, anyway.

That's why I like that version I posted so much - it's clear - I can see those kids out on the school yard, being sorted, and it's fast. There are faster versions, (not many), but those that are faster, begin to lose their clarity, imo.

Look over the version I previously posted, and see if you can't picture the kids out on the school yard, waiting to be sorted by height.

I believe this is from K&R. It's shorter and easier to understand, as well.

Code:

---


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* from: The Practice of Programming (pp: 32-34)
 *  by: Brian W. Kernighan and Rob Pike
 */
/* swap: interchange v[i] and v[j] */
void swap( int v[], int i, int j )
{
  int tmp;
  tmp = v[i];
  v[i] = v[j];
  v[j] = tmp;
}
/* quicksort: sort v[0]..v[n-1] into increasing
 * order
 */
void quicksort( int v[], int n )
{
  int i = 0, last = 0;
  if ( n <= 1 )              /* nothing to do */
    return;
  swap( v, 0, rand() % n );  /* move pivot elem
                                to v[0] */
  for ( i = 1; i < n; i++ )  /* partition */
    if ( v[i] < v[0] )
      swap( v, ++last, i );
  swap( v, 0, last );        /* restore pivot */
  quicksort( v, last );      /* sort smaller
                                values */
  quicksort( v+last+1, n-last-1 );  /* sort larger
                                      values */
}
void print_array( const int array[], int elems )
{
  int i;
  printf("{ ");
  for ( i = 0; i < elems; i++ )
    printf( "%d ", array[i] );
  printf("}\n");
}
#define NUM 9
int main( void )
{
  int arr[NUM] = { 6, 12, 4, 18, 3,
                  27, 16, 15, 19 };
  /* commented out to aid in predictability
  * srand( (unsigned int) time(NULL) ); */
  print_array(arr, NUM);
  quicksort(arr, NUM);
  print_array(arr, NUM);
  return EXIT_SUCCESS;
}

---

Quote:

---

Originally Posted by Nominal Animal

No selection sort?

I prefer to use selection sort (instead of insertion sort) for small lists (< 32 elements, typically, if sorting ints), especially with quicksort.

---

I tend to stay away from selection sort (for small N) for two reasons.
1. It does a fixed number of comparisons and this makes it end up typically slower than say insertion sort where the number of comparisons depends on the ordering.
2. It is not a stable sort, so it isn't suitable for producing the initial runs of e.g. a stable merge sort.

Quote:

---

For quicksort, in cases when I know there is a lot of repeated values, I like to delete the pivots, then insert them back between the sorted arrays afterwards. It seems to give a speed boost (due to reduced recursion) when there are relatively many pivot values, but the added code complexity may make it a bit slower than a typical optimized quicksort.

---

As soon as you delete values you lose the ability to sort items which are equivalent for the purposes of comparison, but not equal in terms of every other measure.
One can move all items equivalent to the pivot to one end, which is called "three way quicksort".
The thing I tend to do is to check which portion is smaller, then recurse on that one and just iterate on the other. It is also the only way to implement quicksort that guarantees that you avoid stack overflow, and that includes implementations that make use of an explicit stack.

Quote:

---

Hey, how about we start a thread comparing sort function implementations? Perhaps in the contest board? Combining some of our approaches we might arrive at something even better? (Yeah, I'm bored.)

---

That would work for me. You could also check out the sorting pages of my website if you haven't already. ;)

Quote:

---

Originally Posted by iMalc

I tend to stay away from selection sort (for small N)

---

Good points (and by Adak, as well). I think I'll switch to insertion sort, too.

Like I said earlier, the data I sort tends to be large enough for radix sorting, so I've never paid much attention to sorting small arrays.

For lists -- my structures tend to be chained --, I've used Mergesort. I've played with combining the first pass with detecting sorted sequences (merged into one sorted sequence if more than one consecutive sequence is detected), with a three-way merge at the end. It's very simple to implement, and theoretically the time spent in the extra tests should be masked completely because that first pass is limited by memory bandwidth. I've never bothered to compare it, or even write it up.

Quote:

---

Originally Posted by iMalc

The thing I tend to do is to check which portion is smaller, then recurse on that one and just iterate on the other.

---

That sounds like a good approach: smaller list size should mean fewer iterations.

Quote:

---

Originally Posted by iMalc

That would work for me. You could also check out the sorting pages of my website if you haven't already. ;)

---

I have, and just did again, but you use C++ and I prefer C.

Fortunately, the way you avoided the standard C++ library features means there are very few C++-specific details (temporary arrays; I didn't really notice anything else). You also use a Windows environment, and I'm POSIX/Linux, so we'd have to first write some kind of testing harness that'd compile and run on both OSes.

The numeric types I'm most interested in are the standard ones: int32_t, uint32_t, int64_t, uint64_t, float, and double (finite normalize values usig the IEEE-754 Binary32 and Binary64 formats, respectively).

A Xorshift generator is fast, portable, and easy to seed (from say command-line parameter), and very suitable for generating random input data. We'd probably also need a way to load specific test cases from test files (standard input).

For lists, it would make sense defining a node that contains only the next pointer and a value (of one of the above types), with a variable amount of padding per node.

In Linux, I've used the dynamic link facilities (dlopen() etc.) to ensure I can play with the compiler optimizations for the tested functions without affecting the timing facilities (and I've used the TSC since my processors all have constant_tsc). If we compile the sort functions in separate units, and take care to not allow link time optimization, we should achieve the same portably. After all, timing-wise, we'll want to compare the functions, not the machines or OSes; only the relative differences of the sort functions run on a single machine are meaningful. (And, of course, also the differences in relative differences on different CPUs.)

I'd rather have this be more like open collaboration between any interested members than a question or a competition (I don't need the stress of any sort of competition!), but there does not seem to be a suitable forum here.

Moderators? Where to start such a discussion?

I was studying the function checkIt and I understood it's evaluating if the array was already sorted. However what are the situations in which the array wouldn't be sorted?

edit:

is selection sort too slow for small arrays? and bubble sort ?

Quote:

---

Originally Posted by thames

However what are the situations in which the array wouldn't be sorted?

---

Programming errors?

Verifying the functions work is a simple form of unit testing. When I fiddle with sort functions, I write a test harness: a main() that generates test cases, sorts them, usually also timing the execution, and verifies that the data is in sorted order.

I usually start with a test sorter, something like

Code:

---

static int compare_foo(const void *const ptr1, const void *const ptr2)
{
    const foo val1 = *(const foo *)ptr1;
    const foo val2 = *(const foo *)ptr2;

    if (val1 < val2)
        return -1;
    else
    if (val1 > val2)
        return +1;
    else
        return  0;
}

void sort_foo(foo *const data, const size_t size)
{
    qsort(data, size, sizeof (foo), compare_foo);
}

---

which I use to make sure the test harness works correctly, foo being the numeric data type I'm interested in at that point. (Just omit the qsort call to simulate a failing sort.)

That way you don't waste time looking for bugs all over your code, but can concentrate on doing each one thing well, and then immediately test.

Quote:

---

Originally Posted by thames

is selection sort too slow for small arrays? and bubble sort ?

---

No, they are not.

It is true that insertion sort is more efficient than selection sort, and selection sort is faster than bubble sort. The links are to Wikipedia articles, with pseudocode example implementations.

Bubble sort has the very nice feature that it only swaps adjacent entries. It also does no extra work if the array is already sorted.

Selection sort is easy to program correctly, and uses at most as many swaps as there are elements in the array. It does do a large number of comparisons, however.

Insertion sort does fewer comparisons, and instead of swaps, moves parts of the array to be able to insert the value in the correct position.

In other words, the sort algorithms have different features. I personally think that alone makes them all worth learning, because it shows how you can use different approaches to crack a nut. That there is not just one vendor-provided nutcracker you need to use for everything, but have an entire toolbox to choose from:

Pick your tools wisely, with consideration; not with haste and conviction.

For the optimized quicksort case, where a faster-for-smaller-arrays sort function is called when the part to sort is small, insertion sort does beat selection and bubble sort. Because quicksort is designed for large arrays, a single quicksort() invocation will involve a lot of those calls. So, picking one that is efficient means a more efficient quicksort() overall.

Examples:

If you have a small array of relatively large structures, both bubble sort and insertion sort would mean you'd need to swap or move the data in those structures a lot. The amount of memory copied might be the bottleneck here. And you might have other restrictions why you don't want to modify the data structure or organization. With selection sort, you know you need very few (at most the number of elements in the array). So, you could use selection sort for that case.

If you have a small array of data you know is almost surely sorted, you could choose between insertion sort and bubble sort. Bubble sort uses swaps, whereas insertion sort uses insertion/memory moves. Bubble sort is slower, but since the array is small, the execution times you're comparing are "very short" and "even shorter": usually lost in the noise.

Of course, a good programmer will eventually want their solution to be robust, and avoid making unconfirmed assumptions. So, instead of assuming there are just a few elements of data, you'll eventually use a sort function that checks, and uses the appropriate algorithm for data. Even then, the most important thing, in my opinion, is to document the logic, the intentions you have as a programmer, in the source code, in descriptive comments: not what the code does, but why.

That way, when the purpose of the code changes, you or the future developer can check the code, see the assumptions made and their limitations, and adjust the code accordingly. Even things like cache architecture developments may change the balance of which algorithm turns out most efficient in practice, so knowing and documenting those reasons, is very useful in long term.

Quote:

---

Originally Posted by thames

I was studying the function checkIt and I understood it's evaluating if the array was already sorted. However what are the situations in which the array wouldn't be sorted?

edit:

is selection sort too slow for small arrays? and bubble sort ?

---

It is used to check whether the sort program sorted correctly or not. It wouldn't sort correctly because when I wrote the code, I made zee leetle airrare, eh? <smile>

I have a Combsort that is quite "brittle", also an iterative Quicksort that is just like glass I swear - used to run fine, but on the newer cpu's and chipsets, it's WAY too touchy. Also, a FAST sort program that was published with an error in it, in Byte Magazine - things like that.

I have no use whatsoever for Selection sort. Never liked it, and on my PC's, it was always the slowest sorter. I view it's algorithm as the worst of any (somewhat popular) sorting algorithm. Pathetic about covers it. (sorry Nominal!).

Bubble sort is OK for small number of things, but mostly, it just has a catchy name. IMO Insertion sort should be the "low end" sorting algorithm, because:

1) It's stable, by design
2) It's very fast with a small number of things to sort, and with values that are already sorted (it happens).
3) It's shorter than Bubble sort after Bubble sort is optimized.
4) It's about 3.5 times faster on random integers, with small arrays, than Bubble sort. (With optimizations, the sorting speeds even out as the size of the array grows larger). By that time, you'll definitely want something better!

Quote:

---

Originally Posted by Adak

I have no use whatsoever for Selection sort. Never liked it, and on my PC's, it was always the slowest sorter.

---

Really? My measurements disagree.

Using Athlon II X4 640 (with a stable time stamp counter), median cycle counts for test sorts for uniform random input were

Code:

---

#  N ints, no padding, 100000 tests, +66 cycles overhead
#  N    Bubble Selection Insertion
  4        59        41      116
  6      149      167      284
  8      321      335      459
  12      804      750      882
  16      1391      1224      1373
  24      2901      2436      2522
  32      4850      3969      3858
  40      7253      5804      5358
  48    10127      7923      7012
  56    13493    10321      8799
  64    17363    12996    10750

#  N ints, 12 chars padding, 100000 tests, +66 cycles overhead
#  N    Bubble Selection Insertion
  4        75        60      119
  6      171      189      269
  8      321      375      422
  12      845      809      778
  16      1514      1313      1203
  24      3120      2588      2154
  32      5092      4208      3282
  40      7430      6182      4562
  48    10145      8499      5959
  56    13230    11160      7500
  64    16847    14145      9160

#  N ints, 124 chars padding, 100000 tests, +66 cycles overhead
#  N    Bubble Selection Insertion
  4      240      167      224
  6      573      352      488
  8      1074      600      794
  12      2624      1134      1593
  16      4748      1748      2408
  24    10862      3228      4733
  32    18602      4925      7566
  40    28238      7031    11066
  48    40846      9410    15161
  56    55593    12045    19851
  64    71924    14864    25133

---

Here is the array element the above functions sort:

Code:

---

typedef int  key_t;

struct data {
    key_t key;
#ifdef PADDING
#if PADDING > 0
    char  padding[PADDING];
#endif
#endif
};

---

with PADDING defined at compile time as per comments in the above results. The actual sort functions were compiled optimized (gcc -W -Wall -O3 -fomit-frame-pointer) separately from other parts. The sort functions themselves, should you care to test, are:

Code:

---

/* Swap two data entries.
*/
static inline void data_swap(struct data *const data, const size_t dst, const size_t src)
{
    if (dst != src) {
        struct data  temp;
        temp      = data[src];
        data[src] = data[dst];
        data[dst] = temp;
    }
}

/* Insert src into dst, if src > dst.
*/
static inline void data_insert(struct data *const data, const size_t dst, const size_t src)
{
    if (dst < src) {
        struct data  temp;
        temp = data[src];
        memmove(data + dst + 1, data + dst, (src - dst) * sizeof *data);
        data[dst] = temp;
    }
}


void no_sort(struct data *const data __attribute__((unused)), size_t const elements __attribute__((unused)))
{
    return;
}


void bubble_sort(struct data *const data, size_t const elements)
{
    size_t  n = elements + 1;

    while (n-- > 0) {
        size_t  i = 1;

        while (i < n && data[i-1].key <= data[i].key)
            i++;

        if (i >= n)
            return;

        while (i < n) {
            if (data[i-1].key > data[i].key)
                data_swap(data, i-1, i);
            i++;
        }
    }
}


void selection_sort(struct data *const data, size_t const elements)
{
    size_t  i = elements;

    while (i-- > 1) {
        size_t  max_ref = i;
        key_t  max_key = data[i].key;

        size_t  k = i;
        while (k-- > 0)
            if (data[k].key > max_key) {
                max_key = data[k].key;
                max_ref = k;
            }

        data_swap(data, max_ref, i);
    }
}


void insertion_sort(struct data *const data, size_t const elements)
{
    size_t  i;

    for (i = 1; i < elements; i++) {
        const key_t  key_i = data[i].key;

        if (data[0].key > key_i)
            data_insert(data, 0, i);
        else {
            size_t  k = i;

            while (data[k - 1].key > key_i)
                k--;

            data_insert(data, k, i);
        }
    }
}

---

I did try to avoid cache effects -- each function sorted their own arrays, with identical new data generated for each before each timing iteration. As mentioned above, the median cycle counts were collected from hundred thousand iterations.

You could say that sorting small arrays of large structures (124 chars or 31 ints of payload per sort key) is silly, but I won't rule it out. That's where I said selection sort works well, and the data above seems to back me up on that.

My insertion sort routine could do with a bit more finesse, too. If the cutoff for quicksort is around the 32 element mark, as I've used, then selection sort does not look too bad. Remember that the idea is to use the least number of cycles overall, not pick the one that gives the minimum in some corner case. So you need to consider the relative differences, and the typical array size.

These results are not conclusive in any way, as only uniformly random source data was even tested: bubble sort and insertion sort would have much more of an advantage with nearly-sorted or even partially-sorted inputs. However, these are the basis for my earlier statements, and I definitely refuse to discard any of the sorting algorithms outright.

Your bubble sort has a separate pass to determine the sortedness, that's probably what's slowing it down. Normally one would optimise over the naieve bubblesort by either using a flag to detect if the pass made any swaps, or even better you'd remember the position of the highest swap in that pass, allowing you to not only detect when no more passes are required, but also when you can skip a whole lot of longer passes and go pick up from one of the shorter ones.
This makes bubble sort also able to perform fewer compares than selection sort, and beat the performance of selection sort in many cases.
It's why the two most commonly used algorithms for small N are those two, with selection sort probably coming in third.

Really?

There are two optimizations that I know of, commonly used with Bubble sort. Your Bubble sort, has neither of them. :(

In Insertion sort - although I haven't seen the assembly code it generates, it appears you've stretched out the tight inner loop that is it's best feature.

Why don't you just add your favorite version of Selection sort, into the program I posted previously?

I've tested Selection sort hundreds of times, on several PC's, because it's part of my larger program that tests sorting algorithms on random int's.

It sucks. ;) But I have not tested it on miniscule quantities of 5 or 12, or anything less than 50 integers.

Adapting the best bubble sort version off my website:

Code:

---

void bubble_sort(struct data *const a, size_t const n) {
    size_t i = n-1;
    do {
        size_t k = 0;
        for (size_t j = 0; j < i; ++j) {
            if (a[j + 1].key < a[j].key) {
                data_swap(j, j + 1);
                k = j;
            }
        }
        i = k;
    } while (i > 0);
}

---

I write every sorting algroithm on my website that I can, in terms of the less-than operator for comparing items.

I would Remove the unecessary test for swapping with self inside data_swap. It only saves time in very very few cases, and adds extra effort in every case.

I don't particularly like using the same identifier as the type of the struct and the name of the struct variable, since that is not legal in C++.

Oh and just to be clear, I had found that of the O(n*n) sorting algorithms used for values of small N, within other algorithms wuch as merge sort, that insertion sort was most common, followed closely by bubble sort, and finally by insertion sort.

Quote:

---

Originally Posted by iMalc

Normally one would optimise over the naieve bubblesort by either using a flag to detect if the pass made any swaps

---

Obviously.

My code is a two-state state machine, where the first inner while loop locates the initial pair to swap. If none, it is done. Otherwise it continues into the actual swapping loop. The second inner while loop, the swapping loop, is only executed when swaps are done, thus it also doubles as the swapped flag.

Quote:

---

Originally Posted by Adak

Why don't you just add your favorite version of Selection sort, into the program I posted previously?

---

clock() does not have enough precision on my machine. It reports zero execution times.

Also, I'd rather have the sort functions compiled separately, and work on argument arrays, not on global arrays.

Quote:

---

Originally Posted by Adak

I have not tested it on miniscule quantities of 5 or 12, or anything less than 50 integers.

---

It seems that quicksort is faster for uniform random data at much smaller sizes, roughly 30 on my machine. I don't use bubblesort/selection sort/insertion sort on large arrays, only on these minuscule ones.

(My data tends to be clustered, nearly quantized, but rarely sorted.)

---

Attached is a zip file containing a simple C/C++ harness for testing in-place sort algorithms. Any improvements, fixes, et cetera are warmly welcome. You can even run with it as your own, since I consider the contents of the zip file either public domain, CC-0, or non-copyrightable (due to obviousness and so on).

I haven't tested it on Windows, but I included code that I think should use the performance counters Windows provides. On other systems it uses the realtime POSIX.1-2008 clock_gettime(CLOCK_PROCESS_CPUTIME_ID) clocks. You can add others by modifying the cputime.h file.

The idea of the harness is that you only need to add your sort function to the sort.c file, add its name and function to the array of structures at the end of the file, and recompile and run the program. I use GCC-4.6.3, and it compiles also on GNU G++, but again, I haven't tested other compilers.

I expect results to differ on different compilers, but it would be useful if the harness produced reproducible results, so the sort functions could be compared against each other on different compilers and architectures. It might provide interesting insights on the implementation specifics wrt. different C/C++ compilers, too.

Running make will compile and run an example set of sort tests. It will output verbose data, and save tabular data in result files.

(The harness program itself takes one or more command-line parameters, defining the number of iterations, the size of the array, and optionally the amount of sorted data in the array -- actually I was just lazy, and shuffle the data instead; that should be fixed to using insertion shuffle to get short sorted runs too. The Makefile contains a default set of commands. Run ./main without parameters to see the usage details. Tabular data is to standard output, verbose to standard error.)

If you have Bash and Gnuplot, run ./plots.sh to display the plots of the run times. It will also save them as SVG files in the working directory. (I thought of attaching them to this post, but I decided against that: I'd prefer to collaborate, not compete.)

I would quite much enjoy discussing these algorithms and implementations constructively. Perhaps in another thread, as we're pretty far from the original topic here.

Unless we have something hands-on we can test, we're just expressing our opinions -- which is not that useful; I'm more interested in hard facts and results and theories that can be tested. (I don't care if we disagree, but I care why we disagree. If that makes sense.)

In particular, my result sets do not match iMalc's and Adak's comments. I'd be interested to discuss why, but we'd need to be able to run the sorts in a comparative environment, so we can compare our results, and fine-tune the harness, so the results can be repeated and demonstrated by others. Opinions and results from other tests are not comparable, as there are too many variables that affect the results.

At minimum, if you could extract and compile the attached files, and report any errors (preferably with fixes, please!) when compiled on Windows, I'd be very grateful.

Quote:

---

Originally Posted by iMalc

Oh and just to be clear, I had found that of the O(n*n) sorting algorithms used for values of small N, within other algorithms wuch as merge sort, that insertion sort was most common, followed closely by bubble sort, and finally by insertion sort. (you meant Selection sort).

---

I couldn't get your Selection sort to work Nominal Animal, but I grabbed one from Wiki, and added it onto my new comparative sort program I posted above.

And I can see that Selection sort has benefited greatly from the old DOS days on a (286).

It handily beats Bubble sort on every sorting run except where the data is nearly sorted/already sorted. It even beats Insertion sort by a length, on two out of the three tests - which is a big surprise!

Any sorting program that can beat Insertion sort on randomized data, is OK by me - Selection sort is back from the ashes!

The specialty of Insertion sort still give it the better marks (inherently a stable sort, and absolutely blinding speed with near sorted or sorted data), but there is no doubt that Selection sort is capable, and still has it's unique gift of being THE most intuitive sorting algorithm ever discovered imo, AND makes far fewer swaps than most algorithms, on random data.

I don't know if it's the larger cache sizes in the chips today, or better compilers (probably both), but two sorting algorithms have really benefited:

Shell sort. Used to be an ugly step-sister to the big three (Merge, Heap, and Quicksort), but now it's really stepped up. In my tests, it sorts 100,000 random int's, neck and neck with Quicksort.

Only with a larger number of integers, does Shell sort begin to fall behind.

and of course,

Selection sort. I grew to really dislike Selection sort because it was such a weiner dog in the tests that I made. In fact, I had deleted it from my test programs.

Thanks for the tip on this, Nominal Animal!

I'll check out your "harness" for sorting.

is the classic Data Structures Using C (the blue book) a good Data Structures book ?

Quote:

---

Originally Posted by Adak

I can see that Selection sort has benefited greatly from the old DOS days on a (286).

---

The CPU architectures have undergone some serious changes. We now have branch prediction, efficient caching algorithms, even speculative execution, on typical processors. I suspect the relative cost of comparison has significantly decreased compared to the other operations, making Selection sort useful at least for some cases.

Which is exactly my point with regards to sorting algorithms: investigating them, and looking at their features, strengths, and weaknesses, you can find scenarios where any one will beat the others. Some of the scenarios are not realistic -- or are not realistic right now --, but as a programmer, it is very good to have a varied tool box to pick your tools from.

I cannot find a reference to it right now, but I remember an article about algorithms that were first discovered in the early 1900s, and are now being re-discovered, as they become very useful again -- only this time implemented in hardware, and not by humans.

Quote:

---

Originally Posted by Adak

Shell sort. Used to be an ugly step-sister to the big three (Merge, Heap, and Quicksort), but now it's really stepped up.

---

Yes. As the Wikipedia article on Shellsort describes, there has been a lot of theoretical (and practical) research into the different gap sequences. While many of them have either the same or nearly the same theoretical complexity or bounds, each sequence tends to have different real-world behaviour wrt. different types of input.

In particular, different Shellsorts implemented into my harness will very likely exhibit different relative strengths/weaknesses for different types of data -- as if they were different algorithms altogether.

Current CPUs tend to be able to do rather complicated computations in the same time they can access a random memory location; given sufficient amounts of data, the memory bandwidth is surprisingly often the bottleneck[*]. This has moved more complex algorithms, and algorithms like Shellsort that need to e.g. compute an integer expression to determine what to do next, from theoretical curiosities to very practical tools.
[*] The converse is also true. If you have an array with just a few items, that fits in a cache line (32 bytes is very common currently), a linear search over sorted data may be faster than a binary search. This is due to the CPU architecture; long pipelines, speculative execution, fast local caches -- basically, the CPU has features that allow it to execute the "slow dumb" code faster than it would the "fast smart" code. The only way to keep your code at peak efficiency, really, is to not assume too much, and to test and verify any assumptions you do make.

Quote:

---

Originally Posted by Adak

I'll check out your "harness" for sorting.

---

If you have any fixes or enhancements or anything, I'd very much like to have your input. And as I said before, I'd like to have the code splayed out here somewhere, so we could try out different solutions, and compare them against each other. Collaboration, not competition.

Theoretical discussions about the number of comparisons or swaps or insertions or the complexity or bounds is fine, but it does not a program make. Real-world results depend on much more details, some of which are out of our control -- which means testing on different compilers and hardware is really the only way to find out which real-world effects are due to the algorithm, and infer the real-world causes for the rest of the effects.

The way I try to do my measurements is such that the lower 80% to 95% of measurements are reliable, and errors are likely clustered to the upper end of the spectrum. (In some cases I can see CPU usage spikes in the measurements, for example.) It also means that if the curves don't look smooth, better retry the tests a few times (with different concurrent loads on the machine), to see if the results are true, or just an artefact of extraneous events.

Since minimum really maps to "optimum" conditions, I like to use median, as you know that you'll achieve the median (or faster) at least 50% of the time. (In real world usage, you'll have other overheads, of course, but those overheads don't usually depend on the algorithm at all.)

If we could tell what fraction of the measurements were erroneous -- they're almost certainly at the end, so we could just forget about those by truncating the sorted elapsed CPU times -- we could compute the expected times for each sort function. Since I don't have any real basis (other than inspecting the timing histograms) for any specific figure, I don't do that.

Finally, the "harness" does not generate the partially sorted data as it should. Now, it just does half the unsorted number of swaps. It really should do insertions instead of swaps, or perhaps swap two consecutive nonoverlapping sequences of data. So, where the results say "50% sorted" or some such, it is just for some weird definition on "50% sorted" :) It should be easy to fix for any interested person; just modify the data.c file, shuffle_data()function.

0 1 2 3 4 5 6 7 8 9

Quote:

---

Bubble sort: 0 swaps in 0.0000 seconds
Insertion sort: 0 swaps in 0.0000 seconds
Quicksort: 65535 swaps in 0.0100 seconds
Optimized Quicksort: 2047 swaps in 0.0000 seconds
Shell sort: 0 swaps in 0.0100 seconds

---

why is quicksort sorting if the numbers are already sorted ?

Quote:

---

Originally Posted by thames

why is quicksort sorting if the numbers are already sorted ?

---

Is that the version of quicksort that moves (swaps) the pivot to the start/end first?

Quicksort is a partitioning sort. Unlike Bubble sort or Insertion sort, it has no initial test to see if the data is already sorted or not. In the course of it's looping, the pivot it picks will usually not be the ideal one, and whenever it is NOT the ideal one, it will begin making swaps. Only when it's done will stop.

You can see how the optimized version (which uses insertion sort for the smaller sub-arrays), knocks down the number of swaps needed, and saves just a bit of time, as well.

That is a problem with Quicksort, btw - if the data is already sorted, then the time needed to finish re-sorting, is far longer than if the data is NOT sorted! Just the way partitioning works, in Quicksort. You don't want to send sorted data to Quicksort - it's a real problem, especially if it's an dumb version of Quicksort, in the way it chooses it's pivot. (Say, by taking the first data value as the pivot - that would be a disaster).

No, neither version moves the pivot. I was taught that moving the pivot was "old fashioned", and a hindrance to Quicksort. In my tests of several versions, there was no version which moved the pivot, and was as fast as the unoptimized version, I posted, and as clear.

Quote:

---

Originally Posted by Adak

No, neither version moves the pivot.

---

That's not why I asked.

The reason I asked was because there are many variants of quicksort that do not cause any swaps to happen if the data is linear and ascending: ith data element being A*i+B, where A > 0, and A and B are constants over the entire dataset.

In this thread, I've seen iMalc's median pivot, and the median-of-three pivot scheme, which both cause a quicksort to behave that way.

Those quicksort variants happen to pick the actual median for the pivot for every range (because the median is in the middle of every range; it's a direct result of the above data rule). Therefore, those variants should have zero swaps for such consecutive sorted input.

Therefore, in my mind, there were two possible causes for the swaps: either the pivot selection was random/non-middle/non-median-of-three (probably random), or the swap count counted the pivot swaps and either the swaps were summed over a number or calls, or there was something seriously wrong about the recursion part in the quicksort function. 2047 = 2·2¹⁰-1 swaps for a ten-entry array seemed suspicious to me.

10 entry array??

My array sizes were either 100,000 or 50,000 numbers. I have it only show the first 10 digits of each sort.

Quote:

---

Originally Posted by Adak

I have it only show the first 10 digits of each sort.

---

Ah, so you have. I only now realized the output thames showed was from your program. Okay, the swap count makes sense then, because your code uses random pivot selection. This thread has meandered so much I've lost track, sorry ;)

If you're running Windows, then check out the app I made for animating them. It shows the assignment counts and comparison counts.
I measure the number of item assignments rather than swaps because it's easy to record that from the overloaded assignment operator (yeah that's C++). Also because some algorithms don't work by swapping, (like data_insert) and it doesn't make for a sensible comparison when several algorithms just always show zero.

Your sorting project compiles and runs fine for me in code blocks under windows. What I couldn't figure out is why the version with a mere flag is beating the version with the float limit in every case.
However, upon running my own sorting demo app, I was eventually able to find an ordering where the float-limit strategy pays off. One example is where the data is ordered as if you visited a balanced binary tree in pre-order traversal. e.g. (3, 1, 0, 2, 5, 4, 6)
So, although the flag version came out faster here, the float-limit version often performs fewer comparisons and should fare better for real-world sized items where the cost of the item comparisons outweighs the tiny assembly differences that give the flag version an advantage here.

sorry, the only thing I could picture about the optimized quicksort implementation was

Code:

---


  if (low == high) return;

---

because it's very similar to

Code:

---


  if (left == right) return;

---

when left is incremented until it encounters right.

actually, I don't know how a quicksort works together with an insertion sort :confused: .