CodeUtility
Tornando o seu trabalho de dev mais simples!
Algoritmos C/C++

Ordenação rápida (quick sort) em C e C++

Nesta lição, você vai implementar o quick sort particionando o array em torno de um elemento pivô (pivot).

Introdução

O quick sort escolhe um elemento como pivô (pivot) e reorganiza o array para que os elementos menores que o pivô fiquem à esquerda e os demais à direita. Nesse momento o pivô já está na posição final, e o algoritmo continua ordenando os dois lados com recursão.

Pontos importantes

  • Teste com entradas vazias, com um único elemento, com valores repetidos e já ordenadas.
  • Primeiro faça funcionar corretamente, depois otimize.
  • Em código real, prefira as funções prontas da biblioteca padrão.

Visualizador de Ordenação rápida (quick sort) em C e C++

O(n log n)

Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.

Exemplos de código C e C++

C
Executar →
main.c
#include <stdio.h>

void swap(int *left, int *right) {
    int temporary = *left;
    *left = *right;
    *right = temporary;
}

int partition(int *values, int low, int high) {
    int pivot = values[high];
    int boundary = low;
    for (int scan = low; scan < high; ++scan) {
        if (values[scan] < pivot) {
            swap(&values[boundary++], &values[scan]);
        }
    }
    swap(&values[boundary], &values[high]);
    return boundary;
}

void quick_sort(int *values, int low, int high) {
    if (low >= high) return;
    int pivot = partition(values, low, high);
    quick_sort(values, low, pivot - 1);
    quick_sort(values, pivot + 1, high);
}

int main(void) {
    int values[] = {9, 4, 7, 3, 10, 5};
    quick_sort(values, 0, 5);
    for (int index = 0; index < 6; ++index) {
        printf("%d ", values[index]);
    }
}
Resultado da execução
3 4 5 7 9 10
C++
Executar →
main.cpp
#include <algorithm>
#include <iostream>
#include <vector>

template<class Iterator>
void quick_sort(Iterator first, Iterator last) {
    if (last - first < 2) return;
    auto pivot = *(last - 1);
    auto middle = std::partition(first, last - 1,
        [pivot](int value) { return value < pivot; });
    std::iter_swap(middle, last - 1);
    quick_sort(first, middle);
    quick_sort(middle + 1, last);
}

int main() {
    std::vector values{9, 4, 7, 3, 10, 5};
    quick_sort(values.begin(), values.end());
    for (int value : values) {
        std::cout << value << ' ';
    }
}
Resultado da execução
3 4 5 7 9 10

Comparação entre C e C++

A função partition em C escolhe o último elemento como pivô e usa a variável boundary para marcar o limite da região dos elementos menores que ele. No final, o pivô é trocado para a posição boundary. A versão em C++ usa std::partition para expressar a partição de forma mais curta. A complexidade média é O(n log n), mas um pivô mal escolhido pode levar a O(n²).

C

Laços, ponteiros, tamanhos e buffers temporários são escritos explicitamente.

C++

Iteradores e algoritmos padrão separam o processamento da forma como os dados são guardados.

Exercícios práticos

Execute as duas versões e depois mude o código para observar a diferença de segurança que cada linguagem oferece.

  • Simule cada comparação no papel.
  • Teste com valores repetidos e com valores muito grandes e muito pequenos.
  • Meça o tempo do seu código e compare com a biblioteca padrão.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios