El método de ordenación QuickSort

Oct 13, 2010 Codigos C# Tutoriales C# 10 comentarios

Hoy les presento un método de ordenación que ha dado muy buenos resultados y es considerado el método de ordenación más rápido que existe, de ahí viene su nombre tan sugerente: QuickSort. Aunque su caso peor es O(n2), la probabilidad de que esto ocurra es muy baja si tomamos algunas de sus variantes aleatorias. Su caso promedio es O(n log n) y es lo que determina la eficiencia de este método.

La idea de este algoritmo de ordenación es particionar el arreglo de elementos en dos subarreglos, no necesariamente de igual tamaño, donde cualquier elemento de la primera será menor que todo elemento de la segunda partición. Esto se logra seleccionando un valor aleatorio del arreglo, y una vez realizada esta parte del algoritmo, se aplica el algoritmo recursivamente a cada una de los subarreglos semiordenados.

En la práctica, se usa QuickSort hasta obtener subarreglos de un tamaño fijo mucho menor (una longitud que ha traído buenos resultados es 20). Entonces se aplica Ordenación por Inserción a estos subarreglos, que es bastante eficiente cuando el arreglo está casi ordenado y hay pocas inversiones.

Veamos ahora el pseudocódigo, para entender un poco mejor que hace este maravilloso algoritmo de búsqueda:

void QuickSort(int[] A) {
QuickSort(A, 0, A.Length - 1);
}
 
void QuickSort (int[] A, int p, int r){
   if (p < r)
   {
      int q = Partition(A, p, r);
      //ordena los primeros q elementos
      QuickSort (A, p, q);
      //ordena los restantes n - q elementos
      QuickSort (A, q + 1, r);
   }
}
 
int Partition(int[] A, int p, int r)
{
   //elemento pivote del arreglo
   int x = A[p];
   int i = p - 1;
   int j = r + 1;
 
   while (true)
   {
      do j--; while (x < A[j]);
      do i++; while (A[i] > x);
      if (i > j)
         Swap(A, i, j);
      else
         return j;
   }
}

El método Partition(), lo que hace es intercambiar elementos que estén invertidos, en función del pivote seleccionado. O sea, Pone a un lados, los elementos menores que el pivote, y al otro lado, los mayores.

Les dejo una implementación en C# que hice hace algún tiempo, si ven algún problema me dicen. Si tienen alguna duda o pregunta, en los comentarios.

//Ordenacion rapida (QuickSort)
public static void QuickSort(int[] a)
{
   QuickSort(0,a.Length-1,a);
}
 
private static void QuickSort(int ini,int fin,int[] a)
{
   int left=ini;
   int right=fin;
   int mid=a[(ini+fin)/2];
 
   do
   {
      //Este es el Partition
      while(a[left]<mid)
         left++;
      while(a[right]>mid)
         right--;
      if(left<=right)
      {
        //Intercambio los elementos
        //si estan invertidos
        int t=a[left];
        a[left]=a[right];
        a[right]=t;
        left++;
        right--;
      }
   }
   while(left<=right);
 
   //Ordeno recursivamente los dos subarreglos
   if(left<fin)
      QuickSort(left,fin,a);
   if(right>ini)
      QuickSort(ini,right,a);
}

Compartir:

Relacionados

algunos artículos que te pueden interesar

10 comentarios

Forma parte de nuestra discusión y síguela de cerca

quiero tutoriales de c#

Autor: sonia quispe | Fecha: Oct 18, 2010.

ok =P

Autor: kopok | Fecha: Nov 19, 2010.

me gustaria ke me mandaras unas tutorias ami correo please!!!

Autor: luis fernando | Fecha: Mar 29, 2011.

hacer este programa

. Diseñar un programa que determine la media del número de horas trabajadas durante todos los dias de la semana.

Autor: juanm20rd | Fecha: Nov 8, 2011.

Esta muy bien tu explicacion acerca de la ordenacion por quicksort,tengo que implementarlo con lista doblemente enlazada, saludos y gracias.

Autor: Jesus | Fecha: Nov 29, 2011.

como hacer que un array con 10 numero o mas lo ordene de menor a mayor los numeros que contenga el array estos numero pueden ser cifras sin ningun sentido correlativo ejemplo: int [] array = new int[]{1105, 5, 201, 2500, 1, 12, 158};
lo que quiero es que los ordene de mayor a menor

y otro seria como ingresar mi nombre en una lista y que esta la ordene correctamente ejemplo: erick
insertar letra final: k
insertar letra inicial: e
insertar letra media: i
insertar letra ” : r
” ” ” : c
y que todas esta aparescan ordenas de esta forma = ( erick)
utilizando la clase list

Autor: elkzador | Fecha: Abr 23, 2012.

@elkzador: Si quieres ordenar el array de mayor a menor solo tienes q cambiar los signos en el método original… el segundo ejemplo no lo entendí bien, pero recuerda que la clase List tiene varios métodos como Add(char value) e Insert(int position, char value)

Autor: Tomy | Fecha: Abr 26, 2012.

disculpa,que significa ese swap(A,i,j) en la funcion partition()???

Autor: samuel | Fecha: May 13, 2013.

como hago los pseudocodigos de estos codigos

Autor: arturo | Fecha: May 26, 2014.

Como haria asi sin cambiar ese codigo para mostrarlo porque si lo imprimo desde QuickSort me imprimira todo los recorridos. Gracias :)

Autor: Mario Jose | Fecha: Ago 12, 2014.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.