Algoritmo QuickSort Eficiente de Divisão e Conquista

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).