quicksort.h

Go to the documentation of this file.

/****************************************************************************
 * 
 *  MODULE:     iostream
 *

 *  COPYRIGHT (C) 2007 Laura Toma
 *   
 * 

 *  Iostream is a library that implements streams, external memory
 *  sorting on streams, and an external memory priority queue on
 *  streams. These are the fundamental components used in external
 *  memory algorithms.  

 * Credits: The library was developed by Laura Toma.  The kernel of
 * class STREAM is based on the similar class existent in the GPL TPIE
 * project developed at Duke University. The sorting and priority
 * queue have been developed by Laura Toma based on communications
 * with Rajiv Wickremesinghe. The library was developed as part of
 * porting Terraflow to GRASS in 2001.  PEARL upgrades in 2003 by
 * Rajiv Wickremesinghe as part of the Terracost project.

 * 
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *

 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  General Public License for more details.  *
 *  **************************************************************************/



#ifndef _QUICKSORT_H
#define _QUICKSORT_H
 
#include <stdlib.h> //for random()


// The class represented by CMPR, must have a member function called
// "compare" which is used for sorting



/* ---------------------------------------------------------------------- */
// On return from partition(), everything at or below pivot will be
// less that or equal to everything above it.  Furthermore, it will
// not be 0 since this will leave us to recurse on the whole array
// again.
template<class T, class CMPR>
void partition(T *data, size_t n, size_t &pivot, CMPR &cmp) {
    T *ptpart, tpart;
    T *p, *q;
    T t0;
    
    // Try to get a good partition value and avoid being bitten by already
    // sorted input.
    //ptpart = data + (random() % n);
#ifdef __MINGW32__
    ptpart = data + (rand() % n);
#else
    ptpart = data + (random() % n);
#endif

    tpart = *ptpart;
    *ptpart = data[0];
    data[0] = tpart;
    
    // Walk through the array and partition it.
    for (p = data - 1, q = data + n; ; ) {
      
      do {
        q--;
      } while (cmp.compare(*q, tpart) > 0);
      do {
        p++;
      } while (cmp.compare(*p, tpart) < 0);
      
      if (p < q) {
        t0 = *p;
        *p = *q;
        *q = t0;
      } else {
        pivot = q - data;            
        break;
      }
    }
}




/* ---------------------------------------------------------------------- */
template<class T, class CMPR>
void insertionsort(T *data, size_t n, CMPR &cmp) {
  T *p, *q, test;
  
  for (p = data + 1; p < data + n; p++) {
    for (q = p - 1, test = *p; (cmp.compare(*q, test) > 0); q--) {
      *(q+1) = *q;
      if (q==data) {
        q--; // to make assignment below correct
        break;
      }
    }
    *(q+1) = test;
  }
}




/* ---------------------------------------------------------------------- */
template<class T, class CMPR>
void quicksort(T *data, size_t n, CMPR &cmp, size_t min_len = 20)  {

  size_t pivot;
  if (n < min_len) {
    insertionsort(data, n, cmp);
    return;
  }
  //else
  partition(data, n, pivot, cmp);
  quicksort(data, pivot + 1, cmp, min_len);
  quicksort(data + pivot + 1, n - pivot - 1, cmp, min_len);
}




#endif // _QUICKSORT_H