Algoritmos clássicos de ordenação – Prof. Felipe Túlio de Castro

Ordenação é o processo de reorganizar um conjunto de dados segundo algum critério, normalmente em ordem crescente ou decrescente. Em termos computacionais, ordenar significa rearranjar os elementos de uma estrutura para facilitar operações posteriores, como busca, comparação, apresentação de relatórios e análise de dados. Ziviani (2011) define a ordenação como o processo de rearranjar objetos em ordem ascendente ou descendente, destacando que seu objetivo é facilitar a recuperação posterior dos itens.

Cormen et al. (2012) destacam que a ordenação é um dos problemas fundamentais da computação porque diversos algoritmos a utilizam como sub-rotina, o que faz da eficiência de um método de ordenação um fator de impacto direto sobre o desempenho de sistemas inteiros. Ziviani (2011) reforça essa visão ao afirmar que o estudo dos algoritmos de ordenação constitui uma porta de entrada natural para a compreensão de conceitos centrais de análise de complexidade, como o comportamento assintótico de um algoritmo diante do crescimento do volume de dados.

Neste artigo, o problema será tratado a partir de um cenário aplicado e recorrente na rotina acadêmica: suponha um professor que precisa ordenar as notas de uma prova para gerar relatórios de desempenho, identificar extremos (maior e menor nota) ou calcular estatísticas como a mediana. Considere também que todas as notas estão armazenadas em um vetor estático de números de ponto flutuante (float).

Serão apresentados cinco algoritmos clássicos — Bubble Sort, Selection Sort, Insertion Sort, Merge Sort e Quick Sort —, cada um descrito em três níveis de abstração crescente: uma explicação conceitual em parágrafos, uma lista de passos operacionais e, por fim, um pseudocódigo formal. O objetivo didático é compreender como cada algoritmo trabalha o problema, quais são seus custos no melhor caso, caso médio e pior caso. Ao final, será apresentada uma implementação completa em C++17, com testes empíricos de desempenho para vetores de 5, 10 e 20 notas.

Critérios de análise de algoritmos

Antes de descrever cada algoritmo, é importante fixarmos os critérios usados para compará-los. Toscani e Veloso (2012) explicam que a análise de complexidade de um algoritmo normalmente considera três cenários:

Melhor caso: a configuração de entrada que exige o menor número de operações (por exemplo, um vetor já ordenado);
Pior caso: a configuração que exige o maior número de operações (por exemplo, um vetor ordenado de forma inversa);
Caso médio: uma estimativa do comportamento esperado considerando todas as permutações possíveis da entrada, com a mesma probabilidade de ocorrência.

Essas três métricas serão expressas em notação Big-O, seguindo a convenção amplamente adotada por Cormen et al. (2012) e por Sedgewick e Wayne (2011) para descrever o crescimento assintótico do tempo de execução em função do número de elementos n.

Bubble Sort (Ordenação por Bolha)

Lógica geral

O Bubble Sort é, segundo Ascencio e Campos (2012), um dos métodos de ordenação mais didáticos justamente por sua simplicidade conceitual, embora não seja eficiente para grandes volumes de dados. Sua lógica consiste em percorrer repetidamente o vetor comparando pares de elementos adjacentes e trocando-os de posição sempre que estiverem fora de ordem. A cada passagem completa pelo vetor, o maior elemento ainda não posicionado “borbulha” até sua posição final, à direita — daí o nome do algoritmo. O processo se repete até que uma passagem inteira seja realizada sem nenhuma troca, o que indica que o vetor já está ordenado.

Uma otimização comum, empregada na implementação apresentada adiante, é encerrar o algoritmo antecipadamente quando uma passagem não realiza nenhuma troca — evitando repetições desnecessárias quando o vetor já está ordenado ou próximo disso.

Passos do Bubble Sort

Repita os passos a seguir enquanto houver trocas na passagem anterior (ou até completar n−1 passagens);
Percorra o vetor da posição 0 até a penúltima posição não fixada;
Compare cada elemento com o seu sucessor imediato;
Se o elemento atual for maior que o sucessor, troque-os de posição;
Ao final de cada passagem completa, o maior elemento restante estará posicionado corretamente na extremidade direita;
Se nenhuma troca ocorreu durante toda a passagem, interrompa o algoritmo — o vetor já está ordenado.

Pseudocódigo

ALGORITMO BubbleSort(vetor, n)
  PARA i DE 0 ATÉ n-2 FAÇA
    trocou <- FALSO
    PARA j DE 0 ATÉ n-i-2 FAÇA
      SE vetor[j] > vetor[j+1] ENTÃO
        TROCAR(vetor[j], vetor[j+1])
        trocou <- VERDADEIRO
      FIM SE
    FIM PARA
    SE trocou = FALSO ENTÃO
      INTERROMPER
    FIM SE
  FIM PARA
FIM ALGORITMO

Análise de casos

No melhor caso, quando o vetor já está ordenado, a versão otimizada faz apenas uma passagem e encerra, resultando em O(n). No caso médio, há várias comparações e trocas, resultando em O(n²). No pior caso, quando o vetor está em ordem inversa, o algoritmo realiza muitas trocas, também resultando em O(n²).

Selection Sort (Ordenação por Seleção)

Lógica geral

O Selection Sort adota uma estratégia diferente: em vez de trocar elementos adjacentes repetidamente, ele divide o vetor conceitualmente em duas partes — uma sublista já ordenada, à esquerda, e uma sublista ainda não ordenada, à direita. A cada iteração, o algoritmo percorre a sublista não ordenada em busca do menor elemento e o troca com o primeiro elemento dessa sublista, expandindo assim a região ordenada em uma posição.

Ziviani (2011) observa que, embora esse método também apresente complexidade quadrática, ele realiza um número de trocas muito menor que o Bubble Sort — no máximo n−1 trocas —, o que pode ser vantajoso quando o custo de mover um elemento é alto. Entretanto, o Selection Sort faz muitas comparações. Mesmo que o vetor já esteja ordenado, ele ainda procura o menor elemento em cada rodada. Por isso, sua complexidade permanece O(n²) no melhor, médio e pior caso.

Passos do Selection Sort

Para cada posição i, de 0 até n−2, faça:
1. Considere i como o índice do menor elemento encontrado até o momento;
2. Percorra o restante do vetor, da posição i+1 até n−1;
3. Sempre que encontrar um elemento menor que o atual “menor”, atualize o índice do menor;
4. Ao final da varredura, troque o elemento da posição i com o menor elemento encontrado;
Avance para a próxima posição e repita até que todo o vetor esteja percorrido.

Pseudocódigo

ALGORITMO SelectionSort(vetor, n)
  PARA i DE 0 ATÉ n-2 FAÇA
    menorIndice <- i
    PARA j DE i+1 ATÉ n-1 FAÇA
      SE vetor[j] < vetor[menorIndice] ENTÃO
        menorIndice <- j
      FIM SE
    FIM PARA
    SE menorIndice <> i ENTÃO
      TROCAR(vetor[i], vetor[menorIndice])
    FIM SE
  FIM PARA
FIM ALGORITMO

Análise de casos

No melhor caso, mesmo com o vetor já ordenado, o algoritmo continua procurando o menor valor em cada etapa, portanto executa O(n²) comparações. No caso médio, também executa O(n²). No pior caso, quando os dados estão muito desordenados, o custo continua O(n²). Sua vantagem está no número relativamente pequeno de trocas, não no número de comparações.

Insertion Sort (Ordenação por Inserção)

Lógica geral

O Insertion Sort, ou ordenação por inserção, funciona como a organização de cartas na mão. O algoritmo percorre o vetor da esquerda para a direita e considera que a parte à esquerda já está ordenada. A cada nova nota, ele procura a posição correta dessa nota dentro da parte ordenada e desloca os elementos maiores para abrir espaço.

Segundo Cormen et al. (2012), esse método é particularmente eficiente para vetores pequenos ou já quase ordenados, sendo inclusive utilizado como etapa auxiliar em algoritmos híbridos mais sofisticados, como o Timsort.

Passos do Insertion Sort

Considere o primeiro elemento como uma parte já ordenada.
Pegue o próximo elemento do vetor.
Compare esse elemento com os anteriores.
Desloque para a direita os elementos maiores que ele.
Insira o elemento na posição correta.
Repita até percorrer todo o vetor.

Pseudocódigo

ALGORITMO InsertionSort(vetor, n)
  PARA i DE 1 ATÉ n-1 FAÇA
    chave <- vetor[i]
    j <- i-1
    ENQUANTO j >= 0 E vetor[j] > chave FAÇA
      vetor[j+1] <- vetor[j]
      j <- j-1
    FIM ENQUANTO
    vetor[j+1] <- chave
  FIM PARA
FIM ALGORITMO

Análise de casos

No melhor caso, quando o vetor já está ordenado, cada nota é comparada apenas uma vez com a anterior, resultando em O(n). No caso médio, há deslocamentos parciais, resultando em O(n²). No pior caso, quando o vetor está em ordem inversa, cada nova nota precisa ser deslocada até o início, resultando em O(n²).

Merge Sort (Ordenação por Intercalação)

Lógica geral

O Merge Sort, ou ordenação por intercalação, utiliza a técnica de divisão e conquista. Sua lógica consiste em dividir recursivamente o vetor ao meio até que cada subvetor contenha apenas um elemento — trivialmente ordenado — e, em seguida, combinar (intercalar) esses subvetores dois a dois, produzindo sublistas cada vez maiores e já ordenadas, até reconstituir o vetor original de forma completamente ordenada.

Sedgewick e Wayne (2011) apontam que a etapa crítica do algoritmo é justamente a intercalação (merge): como as duas metades já estão ordenadas antes de serem combinadas, é possível percorrê-las uma única vez, comparando seus elementos e copiando o menor para um vetor auxiliar a cada passo.

Cormen et al. (2012) apontam que o Merge Sort possui tempo assintótico Θ(n log n), mas seu procedimento de intercalação usa memória auxiliar, isto é, não é naturalmente um algoritmo in-place.

Passos do Merge Sort

Se o vetor (ou subvetor) tiver zero ou um elemento, ele já está ordenado — encerre a recursão;
Caso contrário, divida o vetor ao meio em duas metades aproximadamente iguais;
Aplique recursivamente o Merge Sort na metade esquerda;
Aplique recursivamente o Merge Sort na metade direita;
Intercale as duas metades já ordenadas em um único vetor auxiliar, comparando os elementos de cada metade e copiando sempre o menor;
Copie o resultado intercalado de volta para a posição correspondente no vetor original.

Pseudocódigo

Como este algoritmo de ordenação possui dois momentos distintos (MergeSort e Mesclar), separamos a lógica em dois pseudocódigos para facilitar o entendimento de que há uma chamada recursiva para outra função.

ALGORITMO MergeSort(vetor, inicio, fim)
  SE inicio < fim ENTÃO
    meio <- (inicio + fim) / 2
    MergeSort(vetor, inicio, meio)
    MergeSort(vetor, meio+1, fim)
    Merge(vetor, inicio, meio, fim)
  FIM SE
FIM ALGORITMO

ALGORITMO Mesclar(vetor, inicio, meio, fim)
  CRIAR esquerda <- vetor[inicio..meio]
  CRIAR direita  <- vetor[meio+1..fim]
  i <- 0; j <- 0; k <- inicio
  ENQUANTO i < TAM(esquerda) E j < TAM(direita) FAÇA
    SE esquerda[i] <= direita[j] ENTÃO
      vetor[k] <- esquerda[i]; i <- i+1
    SENÃO
      vetor[k] <- direita[j]; j <- j+1
    FIM SE
    k <- k+1
  FIM ENQUANTO
  COPIAR elementos restantes de esquerda ou direita para vetor
FIM ALGORITMO

Análise de casos

Como observam Toscani e Veloso (2012), a principal vantagem do Merge Sort é justamente a garantia de desempenho O(n log n) em qualquer cenário, enquanto a sua principal desvantagem é o uso de memória auxiliar proporcional a n para realizar a intercalação.

Quick Sort (Ordenação Rápida)

Lógica geral

O Quick Sort também segue a estratégia de dividir para conquistar, mas de forma distinta do Merge Sort: em vez de dividir o vetor ao meio, ele escolhe um elemento de referência, chamado pivô, e reorganiza o vetor de modo que todos os elementos menores que o pivô fiquem à sua esquerda e todos os maiores fiquem à sua direita — processo conhecido como particionamento.

Após o particionamento, o pivô já está em sua posição final definitiva, e o algoritmo é aplicado recursivamente às duas partições resultantes. Knuth (1998) já apontava que, apesar de seu pior caso ser quadrático, o Quick Sort tende a apresentar, na prática, desempenho superior a outros algoritmos O(n log n) devido ao baixo custo constante de suas operações e à boa localidade de referência em memória.

Na implementação apresentada, a estratégia de particionamento adotada é o esquema de Lomuto, que utiliza o último elemento do subvetor como pivô.

Passos do Quick Sort

Se o subvetor tiver zero ou um elemento, ele já está ordenado — encerre a recursão;
Escolha um elemento do subvetor como pivô (na implementação que demonstramos será o último elemento);
Percorra o subvetor reorganizando os elementos, de modo que todos os menores ou iguais ao pivô fiquem à sua esquerda e os demais à sua direita;
Posicione o pivô na fronteira entre as duas partições — essa é sua posição final;
Aplique recursivamente o Quick Sort na partição à esquerda do pivô;
Aplique recursivamente o Quick Sort na partição à direita do pivô.

Pseudocódigo

Como este algoritmo também possui dois momentos distintos (QuickSort e Particiona), separamos a lógica em dois pseudocódigos para facilitar o entendimento de que há uma chamada recursiva para outra função.

ALGORITMO QuickSort(vetor, inicio, fim)
  SE inicio < fim ENTÃO
    posPivo <- Particiona(vetor, inicio, fim)
    QuickSort(vetor, inicio, posPivo-1)
    QuickSort(vetor, posPivo+1, fim)
  FIM SE
FIM ALGORITMO

ALGORITMO Particiona(vetor, inicio, fim)
  pivo <- vetor[fim]
  i <- inicio - 1
  PARA j DE inicio ATÉ fim-1 FAÇA
    SE vetor[j] <= pivo ENTÃO
      i <- i+1
      TROCAR(vetor[i], vetor[j])
    FIM SE
  FIM PARA
  TROCAR(vetor[i+1], vetor[fim])
  RETORNAR i+1
FIM ALGORITMO

Análise de casos

No melhor caso, o pivô divide o vetor em partes equilibradas, resultando em O(n log n). No caso médio, o comportamento esperado também é O(n log n). No pior caso, quando o pivô escolhido gera divisões muito desequilibradas, como em vetores já ordenados usando o último elemento como pivô, o custo sobe para O(n²).

Código em C++ para testar todos os algoritmos

O código a seguir reúne os cinco algoritmos descritos, aplicados ao cenário de ordenação de notas de alunos (armazenadas como float). A função main executa baterias de testes, contabilizando o tempo de execução de cada algoritmo com a biblioteca <chrono>.

Para que seja possível observar o desempenho dos algoritmos em conjuntos de tamanhos diferentes, optamos por deixar no código três versões do vetor notasOriginais: uma com 5 notas, outra com 10 e a última com 20 notas. Por padrão, o algoritmo rodará com o vetor no tamanho igual a 5. Mas, descomentando as linhas 10 ou 11 e as linhas 35 ou 38, você terá como testar o código com tamanho igual a 10 ou 20, respectivamente.

#include <iostream>
#include <iomanip>
#include <chrono>

using namespace std;
using namespace std::chrono;

// Para mudar o tamanho do vetor, descomente a linha desejada
const int TAMANHO = 5;
//const int TAMANHO = 10;
//const int TAMANHO = 20;

// ===================== ASSINATURAS FUNCOES =====================

void bubbleSort(float notas[], int tamanho);
void selectionSort(float notas[], int tamanho);
void insertionSort(float notas[], int tamanho);
void mesclar(float notas[], int inicio, int meio, int fim);
void mergeSort(float notas[], int inicio, int fim);
int  particiona(float notas[], int inicio, int fim);
void quickSort(float notas[], int inicio, int fim);

void copiarVetor(const float original[], float copia[], int tamanho);
void imprimirVetor(const float notas[], int tamanho);
void mostrarResultado(const char nomeAlgoritmo[], const float notas[], int tamanho, double tempoMicrossegundos);

// ===================== FUNCAO PRINCIPAL =====================

int main() {

    // ---------- Vetor de teste: 5 notas ----------
    float notasOriginais[TAMANHO] = {7.5, 3.0, 9.2, 5.5, 1.8};
    
    // ---------- Vetor de teste: 10 notas ----------
    //float notasOriginais[TAMANHO] = {8.0, 3.5, 10.0, 6.0, 7.2, 5.8, 9.5, 4.3, 6.7, 8.9};

    // ---------- Vetor de teste: 20 notas ----------
    //float notasOriginais[TAMANHO] = {7.0, 2.5, 9.8, 6.4, 5.5, 8.1, 3.2, 10.0, 4.9, 6.6, 7.7, 8.8, 1.5, 9.0, 5.9, 6.2, 3.8, 7.4, 4.5, 8.3};

    cout << "COMPARATIVO DE ALGORITMOS DE ORDENACAO" << endl;
    cout << "\nVetor original: ";
    imprimirVetor(notasOriginais, TAMANHO);
    cout << endl;

    // ---------- Teste 1: Bubble Sort ----------
    float notasBubble[TAMANHO];
    copiarVetor(notasOriginais, notasBubble, TAMANHO);
    auto inicioBubble = high_resolution_clock::now();
    bubbleSort(notasBubble, TAMANHO);
    auto fimBubble = high_resolution_clock::now();
    duration<double, micro> tempoBubble = fimBubble - inicioBubble;
    mostrarResultado("Bubble Sort", notasBubble, TAMANHO, tempoBubble.count());

    // ---------- Teste 2: Selection Sort ----------
    float notasSelection[TAMANHO];
    copiarVetor(notasOriginais, notasSelection, TAMANHO);
    auto inicioSelection = high_resolution_clock::now();
    selectionSort(notasSelection, TAMANHO);
    auto fimSelection = high_resolution_clock::now();
    duration<double, micro> tempoSelection = fimSelection - inicioSelection;
    mostrarResultado("Selection Sort", notasSelection, TAMANHO, tempoSelection.count());

    // ---------- Teste 3: Insertion Sort ----------
    float notasInsertion[TAMANHO];
    copiarVetor(notasOriginais, notasInsertion, TAMANHO);
    auto inicioInsertion = high_resolution_clock::now();
    insertionSort(notasInsertion, TAMANHO);
    auto fimInsertion = high_resolution_clock::now();
    duration<double, micro> tempoInsertion = fimInsertion - inicioInsertion;
    mostrarResultado("Insertion Sort", notasInsertion, TAMANHO, tempoInsertion.count());

    // ---------- Teste 4: Merge Sort ----------
    float notasMerge[TAMANHO];
    copiarVetor(notasOriginais, notasMerge, TAMANHO);
    auto inicioMerge = high_resolution_clock::now();
    mergeSort(notasMerge, 0, TAMANHO - 1);
    auto fimMerge = high_resolution_clock::now();
    duration<double, micro> tempoMerge = fimMerge - inicioMerge;
    mostrarResultado("Merge Sort", notasMerge, TAMANHO, tempoMerge.count());

    // ---------- Teste 5: Quick Sort ----------
    float notasQuick[TAMANHO];
    copiarVetor(notasOriginais, notasQuick, TAMANHO);
    auto inicioQuick = high_resolution_clock::now();
    quickSort(notasQuick, 0, TAMANHO - 1);
    auto fimQuick = high_resolution_clock::now();
    duration<double, micro> tempoQuick = fimQuick - inicioQuick;
    mostrarResultado("Quick Sort", notasQuick, TAMANHO, tempoQuick.count());

    cout << "\n=====================================================" << endl;
    cout << " Todos os testes foram executados." << endl;
    cout << "=====================================================" << endl;

    return 0;
}

// ===================== ALGORITMOS DE ORDENACAO =====================

void bubbleSort(float notas[], int tamanho) {
    for (int i = 0; i < tamanho - 1; i++) {
        bool trocou = false;
        for (int j = 0; j < tamanho - i - 1; j++) {
            if (notas[j] > notas[j + 1]) {
                float temp = notas[j];
                notas[j] = notas[j + 1];
                notas[j + 1] = temp;
                trocou = true;
            }
        }
        if (!trocou) break;
    }
}

void selectionSort(float notas[], int tamanho) {
    for (int i = 0; i < tamanho - 1; i++) {
        int menorIndice = i;
        for (int j = i + 1; j < tamanho; j++) {
            if (notas[j] < notas[menorIndice]) {
                menorIndice = j;
            }
        }
        if (menorIndice != i) {
            float temp = notas[i];
            notas[i] = notas[menorIndice];
            notas[menorIndice] = temp;
        }
    }
}

void insertionSort(float notas[], int tamanho) {
    for (int i = 1; i < tamanho; i++) {
        float chave = notas[i];
        int j = i - 1;
        while (j >= 0 && notas[j] > chave) {
            notas[j + 1] = notas[j];
            j--;
        }
        notas[j + 1] = chave;
    }
}

void mesclar(float notas[], int inicio, int meio, int fim) {
    int tamanhoEsquerda = meio - inicio + 1;
    int tamanhoDireita = fim - meio;

    float esquerda[TAMANHO];
    float direita[TAMANHO];

    for (int i = 0; i < tamanhoEsquerda; i++) esquerda[i] = notas[inicio + i];
    for (int j = 0; j < tamanhoDireita; j++) direita[j] = notas[meio + 1 + j];

    int i = 0, j = 0, k = inicio;

    while (i < tamanhoEsquerda && j < tamanhoDireita) {
        if (esquerda[i] <= direita[j]) {
            notas[k] = esquerda[i];
            i++;
        } else {
            notas[k] = direita[j];
            j++;
        }
        k++;
    }
    while (i < tamanhoEsquerda) { notas[k] = esquerda[i]; i++; k++; }
    while (j < tamanhoDireita) { notas[k] = direita[j]; j++; k++; }
}

void mergeSort(float notas[], int inicio, int fim) {
    if (inicio < fim) {
        int meio = inicio + (fim - inicio) / 2;
        mergeSort(notas, inicio, meio);
        mergeSort(notas, meio + 1, fim);
        mesclar(notas, inicio, meio, fim);
    }
}

int particiona(float notas[], int inicio, int fim) {
    float pivo = notas[fim];
    int i = inicio - 1;
    for (int j = inicio; j < fim; j++) {
        if (notas[j] <= pivo) {
            i++;
            float temp = notas[i];
            notas[i] = notas[j];
            notas[j] = temp;
        }
    }
    float temp = notas[i + 1];
    notas[i + 1] = notas[fim];
    notas[fim] = temp;
    return i + 1;
}

void quickSort(float notas[], int inicio, int fim) {
    if (inicio < fim) {
        int posicaoPivo = particiona(notas, inicio, fim);
        quickSort(notas, inicio, posicaoPivo - 1);
        quickSort(notas, posicaoPivo + 1, fim);
    }
}

// ===================== FUNCOES AUXILIARES =====================

void copiarVetor(const float original[], float copia[], int tamanho) {
    for (int i = 0; i < tamanho; i++) copia[i] = original[i];
}

void imprimirVetor(const float notas[], int tamanho) {
    cout << "[ ";
    for (int i = 0; i < tamanho; i++) {
        cout << fixed << setprecision(1) << notas[i];
        if (i < tamanho - 1) cout << ", ";
    }
    cout << " ]" << endl;
}

void mostrarResultado(const char nomeAlgoritmo[], const float notas[], int tamanho, double tempoMicrossegundos) {
    cout << left << setw(16) << nomeAlgoritmo << endl;
    cout << "Tempo: " << fixed << setprecision(3) << tempoMicrossegundos << " microssegundos" << endl;
    cout << "Resultado: ";
    imprimirVetor(notas, tamanho);
    cout << endl;
}

Resultado esperado

Ao executar o programa, a saída final do código deve imprimir o arranjo original dos dados, seguido do nome de cada algoritmo de ordenação, o tempo gasto para a execução do processo e o vetor das notas organizado em ordem crescente.

Um exemplo de saída esperada seria igual ao apresentado abaixo:

COMPARATIVO DE ALGORITMOS DE ORDENACAO

Vetor original: [ 7.5, 3.0, 9.2, 5.5, 1.8 ]

Bubble Sort     
Tempo: 0.353 microssegundos
Resultado: [ 1.8, 3.0, 5.5, 7.5, 9.2 ]

Selection Sort  
Tempo: 0.245 microssegundos
Resultado: [ 1.8, 3.0, 5.5, 7.5, 9.2 ]

Insertion Sort  
Tempo: 0.168 microssegundos
Resultado: [ 1.8, 3.0, 5.5, 7.5, 9.2 ]

Merge Sort      
Tempo: 0.656 microssegundos
Resultado: [ 1.8, 3.0, 5.5, 7.5, 9.2 ]

Quick Sort      
Tempo: 0.300 microssegundos
Resultado: [ 1.8, 3.0, 5.5, 7.5, 9.2 ]


=====================================================
 Todos os testes foram executados.
=====================================================

É importante destacarmos que os tempos podem variar conforme computador, compilador, sistema operacional e carga do sistema no momento da execução. Essa ressalva é importante porque Ziviani observa que medidas reais de tempo dependem de fatores como compilador, hardware e uso de memória, embora ainda possam ser úteis para comparar algoritmos em situações práticas (Ziviani, 2011).

Análise de complexidade: melhor caso, caso médio e pior caso

A análise de algoritmos procura estimar o custo de execução conforme o tamanho da entrada. Ziviani (2011) explica que a análise pode investigar quantas vezes cada parte do algoritmo é executada e quanta memória é necessária. Em algoritmos de ordenação que usam a comparação como base, por exemplo, o custo costuma ser medido pelo número de comparações e movimentações realizadas, pois esses elementos expressam o esforço principal do algoritmo.

Normalmente, observa-se três cenários: 1) o melhor caso, que representa a entrada mais favorável possível; 2) o pior caso, que representa a entrada mais desfavorável; e 3) o caso médio, onde estima-se o comportamento esperado para entradas típicas ou aleatórias. Ziviani observa que o melhor caso é o menor tempo de execução para entradas de tamanho n, enquanto o pior caso é o maior tempo para entradas desse mesmo tamanho; já o caso médio depende de uma distribuição de probabilidades sobre as entradas (Ziviani, 2011).

A Tabela 1 resume os custos assintóticos dos algoritmos estudados para cada caso, além de indicar o custo de memória principal de cada um.

Algoritmo	Melhor caso	Caso médio	Pior caso	Memória extra	Estável?
Bubble Sort otimizado	O(n)	O(n²)	O(n²)	O(1)	Sim
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	Não, na forma clássica
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Sim
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Sim
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n), em média	Não, na forma clássica

Didaticamente, podemos organizar os algoritmos da seguinte forma:

O Bubble Sort é simples e visualmente intuitivo, mas pouco eficiente para conjuntos grandes.
O Selection Sort também é simples, mas sua lógica é diferente: ele procura o menor elemento e o coloca em sua posição definitiva.
O Insertion Sort é eficiente para vetores pequenos e quase ordenados.
O Merge Sort apresenta um salto conceitual, pois trabalha com recursividade e “divisão e conquista”. Ele é mais eficiente assintoticamente, mas exige memória auxiliar.
O Quick Sort também usa “divisão e conquista”, mas se baseia no particionamento por pivô. Seu desempenho prático costuma ser muito bom, embora sua versão simples possa cair para O(n²) em entradas desfavoráveis.

Conclusão

Dominar algoritmos clássicos de ordenação é importante para o programador porque esses algoritmos ensinam mais do que apenas “colocar dados em ordem”. Eles introduzem raciocínios fundamentais sobre eficiência, estruturas de dados, memória, recursividade, comparação de casos e escolha adequada de solução para cada cenário. Em sistemas reais, ordenar notas, nomes, preços, datas ou pontuações pode parecer uma tarefa simples, mas a escolha do algoritmo influencia diretamente o desempenho quando o volume de dados cresce.

Como observam Cormen et al., a escolha do algoritmo mais rápido para uma situação específica pode depender de fatores como características dos dados, hierarquia de memória e ambiente de software (Cormen et al., 2012). Essa percepção pode ser o diferencial que você precisa para sair de uma programação meramente funcional e avançar para uma programação mais analítica, eficiente e profissional.

Obrigado pela leitura e bons estudos!

Referências

ASCENCIO, Ana Fernanda Gomes; CAMPOS, Edilene Aparecida Veneruchi de. Fundamentos da programação de computadores: algoritmos, Pascal, Java e C/C++. 3. ed. São Paulo: Pearson Prentice Hall, 2012.

CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

KNUTH, Donald E. The art of computer programming: volume 3, sorting and searching. 2. ed. Boston: Addison-Wesley, 1998.

SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Boston: Addison-Wesley, 2011.

TOSCANI, Laira Vieira; VELOSO, Paulo A. S. Complexidade de algoritmos. 3. ed. Porto Alegre: Bookman, 2012.

ZIVIANI, Nivio. Projeto de algoritmos: com implementações em Java e C++. 3. ed. São Paulo: Cengage Learning, 2011.

Critérios de análise de algoritmos

Bubble Sort (Ordenação por Bolha)

Lógica geral

Passos do Bubble Sort

Pseudocódigo

Análise de casos

Selection Sort (Ordenação por Seleção)

Lógica geral

Passos do Selection Sort

Pseudocódigo

Análise de casos

Insertion Sort (Ordenação por Inserção)

Lógica geral

Passos do Insertion Sort

Pseudocódigo

Análise de casos

Merge Sort (Ordenação por Intercalação)

Lógica geral

Passos do Merge Sort

Pseudocódigo

Análise de casos

Quick Sort (Ordenação Rápida)

Lógica geral

Passos do Quick Sort

Pseudocódigo

Análise de casos

Código em C++ para testar todos os algoritmos

Resultado esperado

Análise de complexidade: melhor caso, caso médio e pior caso

Conclusão

Referências

Criando uma aplicação JS com framework Express.js

Artigos relacionados