Tugurium/GTI

Glosario Terminología Informática

quicksort

0 clasificación rápida, ordenación -
Algoritmo de clasificación que particionar la cadena en dos segmentos. En el primer segmento, todos los elementos son inferiores o iguales al valor del pivote. En el segundo segmento, todos los elementos son mayores o iguales al valor del pivote. Procede clasificando las dos sublistas recursivamente. El algoritmo se debe a C. A. R. Hoare.

Una implementación simple en C.
<pre>
void quicksort(int * low, int * high)
{
/* We naively use the first value in the array as the pivot */
/* this will not give good performance real usage */

int * lowbound = low + 1; /* the high boundary of the low subarray */
int * highbound = high - 1; /* the low boundary of the high subarray */
int temp;

while(lowbound <= highbound) /* partition the array */
{
if(*lowbound < *low) /* compare to pivot */
lowbound++; /* move lowbound toward the middle */
else
{
temp = *lowbound; /* swap *lowbound and *highbound */
*lowbound = *highbound;
*highbound = temp;
highbound--; /* move highbound toward the middle */
}
}

highbound++; /* move bounds back to the correct positions */
lowbound--;

temp = *low; /* move the pivot into the middle */
*low = *lowbound;
*lowbound = temp;

if(low != lowbound) /* recurse on the subarrays */
quicksort(low, lowbound);
if(high != highbound)
quicksort(highbound, high);
}
<pre>
2003-11-19