How does the Quicksort algorithm work?
I have this class that implements the sort method quicksort but it's not clear to me. How does it sort the values?
public class QuickSortClass {
public static void quickSort(int[] vector, int izquierda, int derecha) {
int pivote = vector[izquierda];
int i = izquierda;
int j = derecha;
int auxIntercambio;
while (i < j) {
while (vector[i] <= pivote && i < j) {
i++;
}
while (vector[j] > pivote) {
j--;
}
if (i < j) {
auxIntercambio = vector[i];
vector[i] = vector[j];
vector[j] = auxIntercambio;
}
}
vector[izquierda] = vector[j];
vector[j] = pivote;
if (izquierda < j - 1) {
quickSort(vector, izquierda, j - 1);
}
if (j + 1 < derecha) {
quickSort(vector, j + 1, derecha);
}
}
public static void main(String[] args) {
int[] numeros = new int[40];
Random rnd = new Random();
System.out.println("Vector desordenado");
for (int i = 0; i < numeros.length; i++) {
numeros[i] = rnd.nextInt(50);
System.out.print(numeros[i] + " ");
}
QuickSortClass.quickSort(numeros, 0, numeros.length - 1);
System.out.println("\nVector Ordenado");
for (int n : numeros) {
System.out.print(n + " ");
}
}
}
3 answers
The quicksort algorithm starts from a very simple concept. Assuming you have an arrangement to:
- you place in an element a [i] where 0
- Place All Elements A [j] > A [i] in the upper or "right" boxes of A[i], while all elements A[k] i is modified.
- after making the changes, you have A1 which is the subset of A from a [0] to a[i-1] and A2 which is the subset of a[i+1] to A[length of A - 1]. Apply this process for A1 and A2.
This is explained very well in the Wikipedia animation .
By: user: RolandH, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=1965827
Let's see how the code you provide in your question corresponds to an implementation of the algorithm:
public static void quickSort(int[] vector, int izquierda, int derecha) {
//1. Elegir el pivote
int pivote = vector[izquierda];
//2. Los elementos > al pivote van a su derecha, los < a su izquierda
//esta parte de la implementación es el corazón del ordenamiento
//se utilizan variables auxiliares:
//- i para controlar los elementos a la izquierda del pivote
//- j para controlar los elementos a la derecha del pivote
int i = izquierda;
int j = derecha;
//esta variable debería tener un alcance menor pero se respeta la implementación
int auxIntercambio;
//mientras que deban evaluarse los elementos en el arreglo
//para ubicar al nuevo pivote
while (i < j) {
//mientras que el elemento vector[i] sea menor o igual al pivote
//se aumenta el valor de i
//cuando este loop se detenga, el elemento en vector[i]
//es mayor a pivote y deberá ir a su derecha
while (vector[i] <= pivote && i < j) {
i++;
}
//mientras que el elemento vector[j] sea mayor al pivote
//se desminuye el valor de j
//cuando este loop se detenga, el elemento en vector[j]
//es menor o igual a pivote y deberá ir a su izquierda
while (vector[j] > pivote) {
j--;
}
//siempre y cuando i sea menor a j, se hace un cambio de los elementos
//puesto que el elemento en vector[i] debe ir a la derecha
//y vector[j] a la izquierda
if (i < j) {
//nota: auxIntercambio podría estar declarada aquí ya que NO tiene otro alcance
auxIntercambio = vector[i];
vector[i] = vector[j];
vector[j] = auxIntercambio;
}
}
//Por los ciclos anteriores, j llegó a una posición donde su elemento (i.e. vector[j])
//es menor o igual al pivote, actualizamos entonces la posición del pivote, mandando vector[j]
//a la ubicación del pivote y viceversa (el pivote a la posicion vector[j])
vector[izquierda] = vector[j];
vector[j] = pivote;
//3. Para A1 y A2, aplicar el mismo proceso.
if (izquierda < j - 1) {
//quicksort aplicado a A1
quickSort(vector, izquierda, j - 1);
}
if (j + 1 < derecha) {
//quicksort aplicado a A2
quickSort(vector, j + 1, derecha);
}
}
The strategy of this algorithm is "divide and conquer", instead of trying to sort a single large list, it separates it several times into smaller partially ordered lists until you have lists of a single element already in the correct position. This is clearer with an example:
Having the initial disordered vector
[5, 1, 3, 9, 6, 10, 2, 8, 4, 7]
Is divided into two parts, taking an element arbitrarily (usually the middle one)
[5, 1, 3, 9, 6] [10, 2, 8, 4, 7]
Now using the selected value (pivot) "6", we move anything less than or equal to the left and anything greater to the right
[5, 1, 3, 4, 2, 6] [10, 9, 8, 7]
This process is repeated for each sublist
[5, 1, 3][4, 2, 6] | [10, 9][8, 7]
[2, 1, 3][4, 5, 6] | [8, 7, 9] [10]
[2, 1][3] | [4, 5][6] | [8, 7][9] | [10]
[1][2] | [3] | [4][5] | [6] | [7][8] | [9] | [10]
Moving everything that is less to one side and everything that is greater to the other eventually manages to sort everything.
Well, let's see, let's assume that we have the following array of integers:
int[] numeros = { 20, 35, 10, 15, 25, 30 }; // Desordenado.
The Quicksort algorithm starts 'picking' as the main value indicating in the parameter, let's assume that it is the first, the 20.
Perform a left-to-right search and find the 35, as the top node and performs a right-to-left Search and finds the 15 as a minor node.
Exchanges them and continues the search with new changes:
int[] numeros = { 20, 15, 10, 35, 25, 30 }
Starting from this point, the array will be split into 2 subarrays, of which will go through the same process until it is computer from minor to major.
Result:
int[] numeros = { 10, 15, 20, 25, 30, 35 } // Ordenado
The recommended, when calling the function is to give an intermediate value, the median.
for more information, as you have left in a comment:
Link to dot Comesunlenguage: Quicksort (where I have relied to answer you)