/*
+---------------------------+
| ORDENACION RAPIDA (QSORT) |
+---------------------------+

        En este  programa se realiza  la ordenación creciente  de un
vector de números enteros.

        El  método de  ordenación seguido  ha sido  el de ordenación
rápida.

        La ordenación rápida, inventada y nombrada por C.A.R. Hoare,
está considerada  como el mejor  algoritmo de ordenación  disponible
actualmente.  Está  basada  en  la   ordenación  por  el  método  de
intercambio.

        La ordenación rápida se basa  en la idea de las particiones.
El procedimiento general es  seleccionar un valor llamado comparando
y entonces  dividir el  array en  dos partes.  En un  lado todos los
elementos mayores  o iguales al valor  de partición y en  otro todos
los elementos menores  que el valor. Este proceso  se repite en cada
parte restante hasta que el array está ordenado.

        Como se  puede ver, este proceso  es esencialmente recursivo
por naturaleza  y, de hecho,  las implementaciones más  claras de la
ordenación rápida es por algoritmos recursivos.

        La  selección del  valor comparado  se puede  obtener de dos
formas. Se  puede seleccionar aleatoriamente o  haciendo la media de
un  pequeño  conjunto  de  valores   tomados  del  array.  Para  una
ordenación   óptima  es   mejor  seleccionar   un  valor   que  esté
precisamente en medio del rango de  valores. Sin embargo, esto no es
fácil de hacer  en la mayoría de los conjuntos  de datos. En el caso
peor,  el valor  escogido está  en un  extremo. Incluso  en este, la
ordenación rápida todavía funciona bien. La versión de la ordenación
rápida que sigue  selecciona el elemento mitad del  array. Aunque no
siempre será  una buena elección,  la ordenación sigue  funcionanado
correctamente.

  Ejemplo:

    Secuencia inicial   8   2   5   3   9
    Elemento comparando: 5
    Primer paso         3   2   5   8   9
    Ahora se ordena con el mismo  procedimiento los vectores '3 2' y
    '8 9'
*/

#include <stdio.h>  /* printf () */
#include <stdlib.h> /* rand ()   */
#include <conio.h>  /* getch ()  */

#define NUM_ELEMENTOS_VECTOR 100

void ordenar (int vect[], int ind_izq, int ind_der);

void main (void)
{
  int vector [NUM_ELEMENTOS_VECTOR]; /* declaración de un vector de
                                     elementos int */

  register int i; /* declaración de una variable registro de tipo
                  entera */

  /* Escritura de la cabecera. */
  printf ("ORDENACION DE UN VECTOR DESORDENADO POR EL METODO DE "
         "ORDENACION RAPIDA:");

  /* Relleno aleatorio de los 100 componentes del vector. A cada
  componente se le asigna un valor aleatorio entre 0 y 999. Las
  componentes del vector van desde la 0 hasta la
  NUM_ELEMENTOS_VECTOR-1 inclusive. */


  for (i = 0; i < NUM_ELEMENTOS_VECTOR; i++)
    vector[i] = rand () % 1000;

  /* Escritura en pantalla del vector desordenado. */
  printf ("\n   Vector desordenado:\n");
  for (i = 0; i < NUM_ELEMENTOS_VECTOR; i++)
    printf ("%d\t", vector[i]);

  /* Ordenación del vector por el método de inserción directa. */
  ordenar (vector, 0, NUM_ELEMENTOS_VECTOR-1);

  /* Escritura en pantalla del vector ordenado. */
  printf ("\n Vector ordenado:\n");
  for (i = 0; i < NUM_ELEMENTOS_VECTOR; i++)
    printf ("%d\t", vector[i]);

  /* Espera la pulsación de cualquier tecla para finalizar el
  programa. */
  getch ();
}

void ordenar (int vect[], int ind_izq, int ind_der)
{ /* vect: vector, ind_izq: índice izquierdo, ind_der: índice
  derecho */
  register int i, j; /* variables índice del vector */
  int elem; /* contiene un elemento del vector */

  i = ind_izq;
  j = ind_der;
  elem = vect[(ind_izq+ind_der)/2];

  do
    {
      while (vect[i] < elem && j < ind_der) /* recorrido del vector
                                            hacia la derecha */
        i++;
      while (elem < vect[j] && j > ind_izq) /* recorrido del vector
                                            hacia la izquierda */
        j--;
      if (i <= j) /* intercambiar */
        {
          int aux; /* variable auxiliar */
          aux = vect[i];
          vect[i] = vect[j];
          vect[j] = aux;
          i++;
          j--;
        }
    } while (i <= j);
  if (ind_izq < j)
    ordenar (vect, ind_izq, j);
  if (i < ind_der)
    ordenar (vect, i, ind_der);
}