Algoritmo QuickSort

Tabla de contenido

¿Cómo funciona QuickSort?
Algoritmo de clasificación rápida
Ejemplos de Python, Java y C / C ++
Complejidad Quicksort
Aplicaciones de clasificación rápida

En este tutorial, aprenderá cómo funciona la ordenación rápida. Además, encontrará ejemplos prácticos de ordenación rápida en C, C ++ Python y Java.

Quicksort es un algoritmo basado en el enfoque de dividir y conquistar en el que la matriz se divide en subarreglos y estos subarreglos se llaman de forma recursiva para ordenar los elementos.

¿Cómo funciona QuickSort?

Se elige un elemento pivote de la matriz. Puede elegir cualquier elemento de la matriz como elemento pivote.
Aquí, hemos tomado el más a la derecha (es decir, el último elemento) de la matriz como elemento pivote. Seleccione un elemento pivote
Los elementos más pequeños que el elemento pivote se colocan a la izquierda y los elementos mayores que el elemento pivote se colocan a la derecha. Coloque todos los elementos más pequeños a la izquierda y los más grandes a la derecha del elemento de pivote.
La disposición anterior se logra mediante los siguientes pasos.
1. Un puntero se fija en el elemento pivote. El elemento pivote se compara con los elementos a partir del primer índice. Si se alcanza el elemento mayor que el elemento pivote, se establece un segundo puntero para ese elemento.
2. Ahora, el elemento pivote se compara con los otros elementos (un tercer puntero). Si se alcanza un elemento más pequeño que el elemento pivote, el elemento más pequeño se intercambia con el elemento más grande encontrado anteriormente. Comparación del elemento pivote con otros elementos
3. El proceso continúa hasta que se alcanza el penúltimo elemento.
  Finalmente, el elemento pivote se intercambia con el segundo puntero. Cambiar elemento de pivote con el segundo puntero
4. Ahora, las subpartes izquierda y derecha de este elemento de pivote se toman para su posterior procesamiento en los pasos siguientes.
Los elementos de pivote se eligen nuevamente para las subpartes izquierda y derecha por separado. Dentro de estas subpartes, los elementos de pivote se colocan en su posición correcta. Luego, se repite el paso 2. Seleccione el elemento pivote de en cada mitad y colóquelo en el lugar correcto usando la recursividad
Las subpartes se vuelven a dividir en subpartes más pequeñas hasta que cada subparte está formada por un solo elemento.
En este punto, la matriz ya está ordenada.

Quicksort utiliza la recursividad para ordenar las subpartes.

Sobre la base del enfoque Divide y vencerás, el algoritmo de clasificación rápida se puede explicar como:

Dividir
La matriz se divide en subpartes tomando pivote como punto de partición. Los elementos menores que el pivote se colocan a la izquierda del pivote y los elementos mayores que el pivote se colocan a la derecha.
Conquista
Las subpartes izquierda y derecha se dividen de nuevo mediante la selección de elementos pivote para ellas. Esto se puede lograr pasando de forma recursiva las subpartes al algoritmo.
Combinar
Este paso no juega un papel importante en la clasificación rápida. La matriz ya está ordenada al final del paso de conquista.

Puede comprender el funcionamiento de la clasificación rápida con la ayuda de las siguientes ilustraciones.

Ordenar los elementos a la izquierda de pivote usando recursividad

Ordenar los elementos a la derecha de pivote usando recursividad

Algoritmo de clasificación rápida

 quickSort (matriz, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partición (matriz, leftmostIndex, rightmostIndex) quickSort (matriz, leftmostIndex, pivotIndex) quickSort (matriz, pivotIndex + 1, rightmostIndex) partición (matriz, leftmostIndex, rightmostIndex) ) establece rightmostIndex como pivotIndex storeIndex <- leftmostIndex - 1 para i <- leftmostIndex + 1 a rightmostIndex si elemento (i) <pivotElement swap element (i) y elemento (storeIndex) storeIndex ++ swap pivotElement y element (storeIndex + 1) return storeIndex + 1

Ejemplos de Python, Java y C / C ++

Python Java C C +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Complejidad Quicksort

Complejidades de tiempo

Complejidad en el peor de los casos (Big-O) : ocurre cuando el elemento pivote elegido es el elemento más grande o el más pequeño. Esta condición conduce al caso en el que el elemento de pivote se encuentra en un extremo de la matriz clasificada. Una submatriz siempre está vacía y otra submatriz contiene elementos. Por lo tanto, solo se llama a quicksort en esta submatriz. Sin embargo, el algoritmo de clasificación rápida tiene un mejor rendimiento para pivotes dispersos.O(n²)
n - 1
Mejor complejidad de caso (Big-omega) : O(n*log n)
Ocurre cuando el elemento pivote es siempre el elemento intermedio o cerca del elemento intermedio.
Complejidad de casos promedio (Big-theta) : O(n*log n)
Ocurre cuando las condiciones anteriores no ocurren.