Quick Sort – Faz da ordenação uma alegria :)

e
(Quik, faz do leite uma alegria!)

É fazendo esse trocadilho com o produto da foto acima, antigo, que começo explicando o Quick Sort, pois o mesmo foi concebido aproximadamente em 1962, quando Charles Antony Richard Hoare visitou a Universidade de Moscovo. Naquela época, Hoare trabalhou em um projeto de tradução de máquina para o National Physical Laboratory. Ele criou o Quicksort ao tentar traduzir um dicionário de inglês para russo, ordenando as palavras, tendo como objetivo reduzir o problema original em subproblemas que possam ser resolvidos mais fácil e rapidamente.

O QuickSort, como o MergeSort, é baseado em uma estratégia de dividir para conquistar e é um dos algoritmos de ordenação mais populares. Veja na figura abaixo um pouco de seu funcionamento.

O método baseia-se na divisão da tabela em duas sub-tabelas, dependendo do pivô, normalmente o 1º elemento da tabela. Uma das sub-tabelas contém os elementos menores que o pivô enquanto a outra contém os maiores. O pivô é colocado entre ambas, ficando na posição correta. As duas sub-tabelas são ordenadas de forma idêntica, até que se chegue à tabela com um só elemento.

Seus passos são:

• Escolha um elemento da lista, denominado pivô;
• Rearranje a lista de forma que todos os elementos anteriores ao pivô sejam menores que ele, e todos os elementos posteriores ao pivô sejam maiores que ele. Ao fim do processo o pivô estará em sua posição final e haverá duas sub-listas não ordenadas. Essa operação é denominada partição;
• Recursivamente ordene a sub-lista dos elementos menores e a sub-lista dos elementos maiores;

Apesar de ser um dos métodos mais rápidos de ordenação, suas partições, às vezes, poderem conduzir a uma ordenação lenta., então cuidado com vetores pequenos e ordenados de forma inversa. É interessante notar o uso do conceito de recursividade.

Reparem no vídeo a seguir como os pivôs delimitam as partições:

QuickSort

Recomendo também, estudarem através do já citado aqui MDA.

Agora vamos a uma breve implementação:

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <time.h>

const int tamanho = 5;

void Trocar(int *a, int *b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int Repartir(int vetor[], int inicio, int fim)
{
    int k = inicio;

    for (int i = inicio + 1; i <= fim; i++)
    {
        if (vetor[i] < vetor[inicio])
        {
            k++;
            Trocar(&vetor[k], &vetor[i]);
        }
    }

    Trocar(&vetor[inicio], &vetor[k]);

    return k;
}

void QuickSort(int vetor[], int inicio, int fim)
{
    if (fim > inicio)
    {
        int parte = Repartir(vetor, inicio, fim);
        QuickSort(vetor, inicio, parte - 1);
        QuickSort(vetor, parte + 1, fim);
    }
}

void Listar(int vetor[])
{
    for (int i = 0; i < tamanho; i++)
    {
        printf("%i\n", vetor[i]);
    }
}

void main()
{   
    srand(time(NULL));

    int vetor[tamanho];

    /*for(int i = 0; i < tamanho; i++)
    {
        vetor[i] = rand() % 100;
    }*/

    vetor[0] = 3;
    vetor[1] = 2;
    vetor[2] = 7;
    vetor[3] = 1;
    vetor[4] = 4;

    printf("Vetor Gerado:\n");
    Listar(vetor);

    QuickSort(vetor, 0, tamanho - 1);
    printf("__________________\n");
    printf("Vetor Ordenado:\n");
    Listar(vetor);

    system("pause");
}

 

E para exercitar a mesma ideia dos exercícios anteriores:

• Implemente um programa, utilizando a linguagem C, que leia 5 ou 11 alunos (composto por: RA, Nome, Ano de Nascimento). Após ler, o usuário irá escolher um tipo de relatório/listagem em tela, podendo ser ordenado por cada um dos atributos do aluno de forma crescente ou decrescente.