quicksort.h

   1 /* vim: set et sts=4 sw=4 fdm=marker fmr={,} fdn=1 fo+=t tw=80:
   2  *
   3  * Taller de Programación (75.42).
   4  *
   5  * Ejercicio Número 4:
   6  * Ordena texto ASCII o Unicode.
   7  *
   8  * Copyleft 2003 - Leandro Lucarella <llucare@fi.uba.ar>
   9  * Puede copiar, modificar y distribuir este programa bajo los términos de
  10  * la licencia GPL (http://www.gnu.org/).
  11  *
  12  * Creado: dom sep 28 17:37:48 ART 2003
  13  *
  14  * $Id$
  15  */
  16
  17 #ifndef QUICKSORT_H
  18 #define QUICKSORT_H
  19
  20 #include <cstdlib>
  21 #include <vector>
  22 #include <cmath>
  23
  24 /// Intercambia 2 índices del vector.
  25 template < class T >
  26 void swap(std::vector< T >& v, int i, int j) {
  27     T tmp = v[i];
  28     v[i] = v[j];
  29     v[j] = tmp;
  30 }
  31
  32 /// Genera un índice al azar.
  33 int rnd(int i, int j) {
  34     return i + rand() % (j-i+1);
  35 }
  36
  37 /// Algoritmo de ordenamiento genérico para ordenar un vector.
  38 template < class T >
  39 void quicksort(std::vector< T >& v, int left, int right) {
  40     // Asigno como último al de la izquierda.
  41     int last = left;
  42     // Si los extremos se juntan, termina.
  43     if (left >= right) {
  44         return;
  45     }
  46     // Intercambia.
  47     swap(v, left, rnd(left, right));
  48     for (int i = left + 1; i <= right; i++) {
  49         if (v[i] < v[left]) {
  50             swap(v, ++last, i);
  51         }
  52     }
  53     swap(v, left, last);
  54     // Llama recursivamente para los fragmentos.
  55     quicksort(v, left, last - 1);
  56     quicksort(v, last + 1, right);
  57 }
  58
  59 #endif // QUICKSORT_H