The Blog

Algoritmo QuickSort - Ordenamiento

2017-07-02 07:25:36

El ordenamiento rápido (quicksort en inglés) es un algoritmo creado por el científico británico en computación C. A. R. Hoare, basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

El algoritmo trabaja de la siguiente forma:

  • Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.
  • Resituar los elementos de la lista de manera que a un lado queden todos los menores que él, y al otro los mayores.
  • La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
  • Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

  • Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
  • En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n·log n).
  • En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de O(n²).
  • En el caso promedio, el orden es O(n·log n).


  • Funcionamiento QuickSort: (2 Ejemplos)


    Código:
    public class QuickSort {
    	
    	public int partition(int arr[], int i, int j)
    	{
    	      int tmp;
    	      int pivote = arr[(i + j) / 2]; //Valor del medio
    	      System.out.println("Pivote escogido: "+pivote);
    
    	      while (i < j) { //Cuando i>j stop!
    	            while (arr[i] < pivote) i++;
    	            while (pivote < arr[j]) j--;
    	            if (i <= j) {
    	                  tmp = arr[i];
    	                  arr[i] = arr[j];
    	                  arr[j] = tmp;
    	                  i++;
    	                  j--;
    	            }
    	            System.out.println("Ordenado: "+Arrays.toString(arr));
    	            System.out.println("Finales: i="+i+" j="+j);
    	      }
    	      System.out.println("");
    	      return i;
    	}
    	 
    	public void quickSort(int arr[], int i, int j) {
    	      
    	      int pivote = partition(arr, i, j);
    	      if (i < pivote - 1){
    		        System.out.println("////// i="+i+" j="+j+" p="+pivote+" Recursividad 1: "+i+"->"+(pivote-1));
    	            quickSort(arr, i, pivote - 1);
    	      }
    	      if (pivote < j){
    		        System.out.println("////// i="+i+" j="+j+" p="+pivote+" Recursividad 2: "+pivote+"->"+j);
    	            quickSort(arr, pivote, j);
    	      }
    	}
         
        public static void main(String a[]){
             
            int[] input = {1,12,5,26,7,14,3,7,2};
            System.out.println("////// i="+0+" j="+(input.length-1)+" Recursividad 0:");
            new QuickSort().quickSort(input,0, input.length-1);
            System.out.println("Lista final ordenada: "+Arrays.toString(input));
        }
    }

    Resultado obtenido:
    ////// i=0 j=8 Recursividad 0:
    Pivote escogido: 7
    Ordenado: [1, 2, 5, 26, 7, 14, 3, 7, 12]
    Finales: i=2 j=7
    Ordenado: [1, 2, 5, 7, 7, 14, 3, 26, 12]
    Finales: i=4 j=6
    Ordenado: [1, 2, 5, 7, 3, 14, 7, 26, 12]
    Finales: i=5 j=5
    Ordenado: [1, 2, 5, 7, 3, 14, 7, 26, 12]
    Finales: i=5 j=4
    
    ////// i=0 j=8 p=5 Recursividad 1: 0->4
    Pivote escogido: 5
    Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
    Finales: i=3 j=3
    Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
    Finales: i=3 j=2
    
    ////// i=0 j=4 p=3 Recursividad 1: 0->2
    Pivote escogido: 2
    Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
    Finales: i=2 j=0
    
    ////// i=0 j=2 p=2 Recursividad 1: 0->1
    Pivote escogido: 1
    Ordenado: [1, 2, 3, 7, 5, 14, 7, 26, 12]
    Finales: i=1 j=-1
    
    ////// i=0 j=4 p=3 Recursividad 2: 3->4
    Pivote escogido: 7
    Ordenado: [1, 2, 3, 5, 7, 14, 7, 26, 12]
    Finales: i=4 j=3
    
    ////// i=0 j=8 p=5 Recursividad 2: 5->8
    Pivote escogido: 7
    Ordenado: [1, 2, 3, 5, 7, 7, 14, 26, 12]
    Finales: i=6 j=5
    
    ////// i=5 j=8 p=6 Recursividad 2: 6->8
    Pivote escogido: 26
    Ordenado: [1, 2, 3, 5, 7, 7, 14, 12, 26]
    Finales: i=8 j=7
    
    ////// i=6 j=8 p=8 Recursividad 1: 6->7
    Pivote escogido: 14
    Ordenado: [1, 2, 3, 5, 7, 7, 12, 14, 26]
    Finales: i=7 j=6
    
    Lista final ordenada: [1, 2, 3, 5, 7, 7, 12, 14, 26]

    Comments (0)

    • ¡Se el primero en comentar!

    Leave a comment

    Su mensaje ha sido enviado correctamente. ¡Muchas gracias!. Recuerda reiniciar la pagina para ver el comentario.

    No ha sido posible enviar el mensaje. Revise los datos