Algoritmo de Ordenación QuickSort

Este método aplica la técnica "divide y vencerás", subdividiendo el vector en vectores más pequeños y ordenando éstos. Para hacer esta división, se toma un valor cualquiera del vector, que se suele denominar pivote, y se realiza el desplazamiento de todos los elementos menores que él a la izquierda de éste. De la misma forma, los elementos mayores que él se desplazarán a su derecha. Con esto se garantiza que los elementos colocados a la izquierda del pivote son menores o iguales que éste, mientras los situados a su derecha serán mayores o iguales a él. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el vector. El procedimiento se repite de forma recursiva hasta que al final todas las particiones son de tamaño 1, con lo que el vector queda ordenado.
Por tanto, dado un vector V de N elementos, el método de ordenación aplicará los siguientes pasos básicos:
  1. Se elige un elemento como pivote.
  2. Si el tamaño del vector es 1, está ordenado. En caso contrario se divide el vector en 2 vectores, V1 y V2, de forma que los elementos de V1 sean menores (o iguales, si hay valores repetidos) que los de V2.
  3. Se ordenan V1 y V2 aplicando QuickSort.
  4. Se devuelve la concatenación de V1 y V2, obteniendo el vector V ordenado.
La elección del pivote no es algo trivial. Aunque en principio se podría elegir cualquier valor, una elección inadecuada reducirá considerablemente la eficiencia del método de ordenación. En nuestro caso se ha optado por tomar, como elemento pivote, el valor de la posición central del vector, o del subvector que se está ordenando.

PSEUDOCÓDIGO
    MÓDULO ordenacion_rapida

    DATOS
       PARÁMETROS
           Transforma V() de tipo T
           Recibe IZQ entera
           Recibe DER entera
       VARIABLES
           I, J enteras
           PIVOTE, AUX de tipo T
    INICIO
           I ← IZQ
           J ← DER
           PIVOTE ← V((IZQ+DER)\2)   ** división entera
           Mientras ( I ≤ J ) hacer
              Mientras ( V(I) < PIVOTE ) hacer
                 I ← I+1
              fin-mientras
              Mientras ( V(J) > PIVOTE ) hacer
                 J ← J-1
              fin-mientras
              Si ( I ≤ J ) entonces
                 AUX ← V(I)
                 V(I) ← V(J)
                 V(J) ← AUX
                 I ← I + 1
                 J ← J - 1
              fin-si
           fin-mientras
           Si ( IZQ < J ) entonces
              ordenacion_rapida(V, IZQ, J)
           fin-si
           Si ( DER > I ) entonces
              ordenacion_rapida(V, I, DER)
           fin-si
    FIN

CÓDIGO C
/*Ordena un vector (de menor a mayor) por el método de quickSort
**Nota: Utiliza Divide y vencerás */
quickSort(int *v, int izq, int der)
{
int i, j, pivo, aux;

i=izq;
j=der;
pivo=v[(izq+der)/2];

	while(i<=j)
	{
		while(v[i]pivo)
		{
		j=j-1;
		}

		if(i<=j)
		{
		aux=v[i];
		v[i]=v[j];
		v[j]=aux;
		i=i+1;
		j=j-1;
		}
	}
	
	if(izqi)
	{
	quickSort(v,i,der);
	}
}

Volver al índice

Volver a Búsqueda y Ordenación Interna



Comentarios

Publicar un comentario

Entradas populares de este blog

Algoritmo de ordenación por mezcla natural

El método de ordenación por mezcla natural, al igual que el de clasificación por mezcla directa, realiza sucesivas particiones y mezclas, pero intenta aprovechar el orden existente en los datos, considerando secuencias de longitud variable. En cada iteración, en primer lugar se separan los registros del fichero origen en otros dos ficheros, copiando en cada uno las secuencias de registros consecutivos que ya están ordenados entre sí en el origen. A continuación, se mezclan los dos ficheros auxiliares, obteniendo de cada dos tramos ordenados otro ordenado. El proceso de ordenación se repite hasta que se obtiene un solo tramo. PSEUDOCÓDIGO MÓDULO Clasificacion_mezcla_natural DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES L entera ** num. de subsecuencias ordenadas mez...
Leer más

Algoritmo de ordenación por mezcla directa

La ordenación por mezcla directa realiza sucesivas operaciones de partición y mezcla, que producen secuencias ordenadas de longitud cada vez mayor. La primera partición se hace en secuencias de longitud 1, y la fusión correspondiente produce sobre el archivo inicial secuencias ordenadas de longitud 2. En cada nueva partición y fusión se duplica la longitud de las secuencias ordenadas obtenidas. El proceso termina cuando la longitud de la secuencia ordenada es mayor o igual que la longitud del archivo a ordenar. PSEUDOCÓDIGO MÓDULO Ordenacion_mezcla_directa DATOS PARÁMETROS Recibe NOMBRE_F cadena ** fichero a ordenar Recibe NOMBRE_F1 cadena ** primer fichero auxiliar Recibe NOMBRE_F2 cadena ** segundo fichero auxiliar VARIABLES NUM_ELEM entero ** num. de registros a ordenar TAM_SEC entero ** tamaño de la secuencia actual INICIO TAM_SEC ← 1 ...
Leer más

Algoritmo de Ordenación por Intercambio Directo (Burbuja)

Este método también se conoce como método de la burbuja. Tiene dos versiones basadas en la misma idea: recorrer sucesivamente el vector comparando los elementos consecutivos e intercambiándolos cuando estén descolocados. En una de las versiones el vector se recorre de izquierda a derecha, desplazando los valores mayores hacia su derecha, y en la otra se recorre de derecha a izquierda, desplazando los valores menores hacia su izquierda, ambos para la clasificación en orden ascendente. Cada pasada sobre el vector lleva un nuevo elemento a su posición definitiva, y en orden, en el extremo de la zona de comparación considerada (extremo derecho en el caso de recorrido de izquierda a derecha y en el extremo izquierdo en el caso de recorrido de derecha a izquierda), por lo que en la siguiente pasada se excluye de las comparaciones. El algoritmo consiste en aplicar los siguientes pasos, considerando inicialmente todas las posiciones del vector: Se comparan los valores de las posicione...
Leer más