Quicksort es un algoritmo de divide y vencerás. Primero divide una lista grande en dos sublistas más pequeñas y luego ordena recursivamente las dos sublistas. Si queremos ordenar una matriz sin ningún espacio adicional, la ordenación rápida es una buena opción. En promedio, la complejidad del tiempo es O (n log (n)).
El paso básico para ordenar una matriz es el siguiente:
- Seleccione un pivote
- Mueva elementos más pequeños a la izquierda y mueva elementos más grandes a la derecha del pivote
- Ordenar recursivamente la parte izquierda y la parte derecha
Esta publicación muestra dos versiones de la implementación de Java. El primero elige el elemento más a la derecha como pivote y el segundo elige el elemento del medio como pivote.
Versión 1: elemento más a la derecha como pivote
La siguiente es la implementación de Java que usa el elemento más a la derecha como pivote.
public class QuickSort { public static void main(String[] args) { int[] arr = {4, 5, 1, 2, 3, 3}; quickSort(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int start, int end){ int partition = partition(arr, start, end); if(partition-1>start) { quickSort(arr, start, partition - 1); } if(partition+1<end) { quickSort(arr, partition + 1, end); } } public static int partition(int[] arr, int start, int end){ int pivot = arr[end]; for(int i=start; i<end; i++){ if(arr[i]<pivot){ int temp= arr[start]; arr[start]=arr[i]; arr[i]=temp; start++; } } int temp = arr[start]; arr[start] = pivot; arr[end] = temp; return start; } } |
Puede usar el siguiente ejemplo para revisar el código.
Versión 2: elemento intermedio como pivote
public class QuickSort { public static void main(String[] args) { int[] x = { 9, 2, 4, 7, 3, 7, 10 }; System.out.println(Arrays.toString(x)); int low = 0; int high = x.length - 1; quickSort(x, low, high); System.out.println(Arrays.toString(x)); } public static void quickSort(int[] arr, int low, int high) { if (arr == null || arr.length == 0) return; if (low >= high) return; // pick the pivot int middle = low + (high - low) / 2; int pivot = arr[middle]; // make left < pivot and right > pivot int i = low, j = high; while (i <= j) { while (arr[i] < pivot) { i++; } while (arr[j] > pivot) { j--; } if (i <= j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i++; j--; } } // recursively sort two sub parts if (low < j) quickSort(arr, low, j); if (high > i) quickSort(arr, i, high); } } |
Producción:
2 3 4 7 7 9 10
Aquí es una muy buena animación de quicksort.
