Quick Sort §

---

O Quick Sort é um algoritmo de ordenação que segue a abordagem dividir e conquistar. Ele seleciona um elemento como pivô e particiona o array ao redor do pivô, colocando os elementos menores à esquerda e os elementos maiores à direita. Em seguida, o algoritmo é aplicado recursivamente às duas partições resultantes até que o array tenha um único elemento.

Note

O processo de particionamento é a chave para o desempenho eficiente do Quick Sort.

Implementação em C:

#include <stdio.h>
 
// Função para trocar dois elementos em um array
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
 
// Função que implementa o particionamento do Quick Sort
int partition(int arr[], int low, int high) {
    // Escolhe o último elemento como pivô
    int pivot = arr[high];
 
    // Índice do menor elemento
    int i = (low - 1);
 
    // Percorre todos os elementos do array
    // Coloca os elementos menores que o pivô à esquerda e os maiores à direita
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
 
    // Coloca o pivô na posição correta
    swap(&arr[i + 1], &arr[high]);
 
    // Retorna o índice onde o pivô está localizado
    return (i + 1);
}
 
// Função principal que implementa o algoritmo Quick Sort
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Encontra o índice do pivô, o array é particionado ao redor deste índice
        int pi = partition(arr, low, high);
 
        // Aplica o Quick Sort recursivamente às duas partições resultantes
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
 
// Função para imprimir um array
void printArray(int A[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}
 
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
 
    printf("Array original:\n");
    printArray(arr, arr_size);
 
    // Chama a função quickSort para ordenar o array
    quickSort(arr, 0, arr_size - 1);
 
    printf("Array ordenado:\n");
    printArray(arr, arr_size);
 
    return 0;
}

Neste exemplo, a função partition é responsável por escolher o pivô e particionar o array ao redor dele. A função quickSort aplica o Quick Sort recursivamente às duas partições resultantes. A função swap é uma função auxiliar para trocar dois elementos no array. O programa principal demonstra a utilização dessas funções para ordenar um array.

Referências §

---

APII-Semana14-MétodosDeOrdenação2