Similar a Combinar ordenar algoritmo, el algoritmo de clasificación rápida es un algoritmo de divide y vencerás. Inicialmente selecciona un elemento como elemento pivote y divide la matriz dada alrededor del pivote elegido. Hay muchas versiones diferentes de QuickSort que seleccionan el pivote de diferentes maneras.
- Elija siempre el primer elemento como pivote (implementado a continuación).
- Elija siempre el último elemento como pivote.
- Elija un elemento aleatorio como pivote.
- Elija la mediana como pivote.
El proceso clave en QuickSort es el proceso de partición(). El objetivo de la función partición() es recibir una matriz y un elemento x de la matriz como pivote, colocar x en su posición correcta en una matriz ordenada y luego colocar todos los elementos más pequeños (menores que x) antes de x, y colocar todos los elementos mayores (mayores que x) después de x. Todo esto debe hacerse en tiempo lineal, es decir, Big O(n) .
Pseudocódigo para la función recursiva QuickSort:
/* low -->Índice inicial, alto --> Índice final */ quickSort(arr[], low, high) { if (low Método-1: CPP // C++ Implementación del algoritmo de clasificación rápida. #include usando el espacio de nombres std; int partición(int arr[], int inicio, int fin) { int pivot = arr[inicio]; int recuento = 0 para (int i = inicio + 1; i;<= end; i++) { if (arr[i] <= pivot) count++; } // Giving pivot element its correct position int pivotIndex = start + count; swap(arr[pivotIndex], arr[start]); // Sorting left and right parts of the pivot element int i = start, j = end; while (i pivotIndex) { while (arr[i] <= pivot) { i++; } while (arr[j]>pivote) { j--; } if (i pivotIndex) { swap(arr[i++], arr[j--]); } } devuelve índicepivote; } void quickSort(int arr[], int start, int end) { // caso base if (inicio>= fin) return; // particionando la matriz int p = partición(arr, inicio, fin); // Ordenando la parte izquierda quickSort(arr, start, p - 1); // Ordenando la parte derecha quickSort(arr, p + 1, end); } int principal() { int arreglo[] = { 9, 3, 4, 2, 1, 8 }; int norte = 6; ordenación rápida(arr, 0, n - 1); para (int i = 0; i cout<< arr[i] << ' '; } return 0; } Output 1 2 3 4 8 9 Method-2 : This method’s space complexity is O(n). As we will take an extra array in partition function like in merge function of merge sort . Algorithm explanation and steps of partition function: Make a new array of size equal to given array. push all the smaller elements than pivotElement to the new array. Push pivotElement to new array now. finally, push all the greater elements than pivotElement to the new array. Now, copy the new array to the original array. Store the index of the pivotElement from the original array. Return this index. After this, all the elements in the original array are in the order : smaller than pivotElement ->pivotElement -> mayor que pivotElement. Complejidad del tiempo: θ(nlogn). Complejidad espacial: O (n). C++ // agregado por Manish Sharma #include usando el espacio de nombres std; int particion(int* arr, int start, int end) { // asumiendo el último elemento como pivotElement int index = 0, pivotElement = arr[end], pivotIndex; int* temp = nuevo int[fin - inicio + 1]; // creando una matriz cuyo tamaño sea igual al rango de partición actual... for (int i = start; i<= end; i++) // pushing all the elements in temp which are smaller than pivotElement { if(arr[i] { temp[index] = arr[i]; index++; } } temp[index] = pivotElement; // pushing pivotElement in temp index++; for (int i = start; i // pushing all the elements in temp which are greater than pivotElement { if(arr[i]>elementopivote) { temp[índice] = arreglo[i]; índice++; } } // todos los elementos ahora en la matriz temporal están en orden: // los elementos más a la izquierda son menores que pivotElement y los elementos más a la derecha son mayores que pivotElement index = 0; para (int i = inicio; i<= end; i++) // copying all the elements to original array i.e arr { if(arr[i] == pivotElement) { // for getting pivot index in the original array. // we need the pivotIndex value in the original and not in the temp array pivotIndex = i; } arr[i] = temp[index]; index++; } return pivotIndex; // returning pivotIndex } void quickSort(int* arr, int start, int end) { if(start { int partitionIndex = partition(arr, start, end); // for getting partition quickSort(arr, start, partitionIndex - 1); // sorting left side array quickSort(arr, partitionIndex + 1, end); // sorting right side array } return; } int main() { int size = 9; int arr[size] = {5, 12, 7, 1, 13, 2 ,23, 11, 18}; cout << 'Unsorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } printf('
'); quickSort(arr, 0, size - 1); cout << 'Sorted array : '; for (int i = 0; i { cout << arr[i] << ' '; } return 0; } Output Unsorted array : 5 12 7 1 13 2 23 11 18 Sorted array : 1 2 5 7 11 12 13 18 23 Please refer complete article on QuickSort for more details!>