Introdução
O QuickSort é um algoritmo de ordenação do tipo "Dividir e Conquistar" (Divide-and-Conquer). Ele funciona selecionando um elemento 'pivô' (pivot) do array e particionando os outros elementos em dois sub-arrays, de acordo com se são menores ou maiores que o pivô. Os sub-arrays são então ordenados recursivamente. A complexidade do caso médio do QuickSort é O(n log n). Deve-se notar que o QuickSort não é uma ordenação estável (stable sort), ou seja, as posições relativas de itens de ordenação iguais podem não ser preservadas.
Importar a Classe Arrays
Nesta etapa, você precisa importar a classe java.util.Arrays. Esta classe contém vários métodos para manipular arrays que serão usados para converter os arrays int em Strings.
import java.util.Arrays;
Definir o método partition()
Defina um método auxiliar chamado partition(). O método partition() receberá um array arr, um índice inicial low e um índice final high como entrada. O método partition() selecionará um elemento como pivô (pivot) e particionará os elementos de forma que todos os elementos menores que o elemento pivô estejam à esquerda do pivô, e todos os elementos maiores que o pivô estejam à direita do pivô. O elemento pivô será colocado em sua posição correta.
O método partition() retornará o índice do elemento particionado. O elemento particionado é a posição onde o elemento pivô é colocado.
public static int partition(int[] arr, int low, int high) {
// Select the pivot element
int pivot = arr[high];
int i = (low - 1); // Index of smaller element and indicates the right position of pivot found so far
for (int j = low; j <= high - 1; j++) {
// If current element is smaller than or equal to pivot
if (arr[j] <= pivot) {
i++; // increment index of smaller element
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i + 1] and arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Return the partition index
}
Definir o método quicksort()
Defina um método de ordenação chamado quicksort(). O método quicksort() receberá um array arr, um índice inicial low e um índice final high como entrada. O método quicksort() irá ordenar recursivamente o array arr[].
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi is partitioning index, arr[p] is now
// at right place
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Criar e Atribuir um Array de Inteiros
Crie e atribua arrays de inteiros a serem ordenados ao campo arr.
int[] arr = {7, 9, 1, 2, 10, 15, 6};
Implementar QuickSort
Chame o método quickSort() com o campo arr como entrada, juntamente com o índice inicial e final do array. Ordene e exiba o array usando o método Arrays.toString(arr).
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
Testar com Múltiplos Arrays
Teste sua implementação de QuickSort usando arrays com várias características.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
Selecionar o Pivot Aleatoriamente
Nesta etapa, precisamos selecionar aleatoriamente o pivot (pivô) em cada iteração para evitar o pior cenário (worst-case scenario). Para conseguir isso, vamos atualizar o método partition() e substituir a seguinte linha:
int pivot = arr[high];
por esta linha:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
Testar com Elemento Pivot Aleatorizado
Teste sua implementação de QuickSort usando elementos pivot (pivô) aleatorizados.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
Lidar com Casos Extremos
Nesta etapa, vamos cobrir os casos extremos (edge cases) que o QuickSort pode lidar. Defina esses casos extremos como arrays de inteiros.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
Código Completo
O código completo do QuickSort em Java Lab é fornecido abaixo.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
Resumo
Este laboratório forneceu um guia passo a passo para implementar o algoritmo QuickSort em Java. Aprendemos que a escolha do pivô (pivoting) é um passo crucial no QuickSort e que diferentes técnicas para selecionar um pivô podem afetar o desempenho do algoritmo. O Quicksort é mais adequado para ordenar grandes quantidades de dados. A complexidade de tempo no pior caso do QuickSort é O(N^2), enquanto sua complexidade de tempo no caso médio e no melhor caso é O(NLogN).
