A ordenação é um conceito fundamental em ciência da computação, essencial para organizar dados de forma eficiente. Este artigo explora diversos algoritmos de ordenação, detalhando suas implementações em C e características de desempenho. Compreender esses algoritmos é crucial para otimizar o processamento e a recuperação de informações em sistemas de software.
A seguir, apresentaremos os algoritmos de ordenação mais comuns, explorando suas lógicas e complexidades.
Ordenação por Inserção Direta
A ordenação por inserção direta é um algoritmo de ordenação simples que constrói a sequência final ordenada um item por vez. Ele funciona iterando sobre o array e, para cada elemento, insere-o em sua posição correta na sub-array já ordenada à sua esquerda.
#include <stdio.h>
#include <stdlib.h>
#include <string.h> // Para memset (usado em Counting Sort)
// Função auxiliar para troca (usada em vários algoritmos)
void trocar(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Algoritmo de Ordenação por Inserção Direta
void ordenarPorInsercaoDireta(int* dados, int tamanho) {
// Itera sobre o array, começando do segundo elemento (índice 1)
for (int i = 1; i < tamanho; ++i) {
int valorAtual = dados[i]; // Valor a ser inserido
int j = i - 1; // Último elemento da sub-array ordenada
// Move os elementos da sub-array ordenada que são maiores que valorAtual
// uma posição para a direita para abrir espaço
while (j >= 0 && dados[j] > valorAtual) {
dados[j + 1] = dados[j];
j--;
}
// Insere o valorAtual na sua posição correta
dados[j + 1] = valorAtual;
}
}
A complexidade de tempo do Insertion Sort é O(N^2) no pior e médio caso, ocorrendo quando o array está em ordem inversa. No melhor caso, quando o array já está ordenado, a complexidade é O(N), pois cada elemento é comparado apenas uma vez. Este algoritmo é eficiente para pequenos conjuntos de dados ou arrays que já estão quase ordenados.
Shellsort
Shellsort, também conhecido como ordenação por inserção com lacunas (gap), é uma otimização do algoritmo de ordenação por inserção. Ele melhora o desempenho ao permitir a troca de elementos distantes, movendo rapidamente elementos para suas posições gerais. O algoritmo funciona comparando e trocando elementos separados por uma lacuna (intervalo) específica, que diminui gradualmente até que se torne 1 (neste ponto, é equivalente a uma ordenação por inserção direta).
// Algoritmo de Shellsort
void ordenarPorShell(int* dados, int tamanho) {
int intervalo = tamanho; // Inicializa o intervalo (gap) com o tamanho do array
// Continua enquanto o intervalo for maior que 0
while (intervalo > 0) {
// Reduz o intervalo usando uma sequência (por exemplo, Knuth: h = h/3 + 1)
intervalo = intervalo / 3 + 1;
// Aplica uma "inserção direta" para cada sub-array definido pelo intervalo
// Iteramos do elemento 'intervalo' até o final do array
for (int i = intervalo; i < tamanho; ++i) {
int valorParaInserir = dados[i]; // O valor a ser posicionado
int j = i; // Posição atual do valor a ser inserido
// Move os elementos maiores que valorParaInserir para a direita
// na sub-array atual, com o passo 'intervalo'
while (j >= intervalo && dados[j - intervalo] > valorParaInserir) {
dados[j] = dados[j - intervalo];
j -= intervalo;
}
// Insere o valorParaInserir na sua posição correta
dados[j] = valorParaInserir;
}
}
}
A complexidade de tempo do Shellsort é difícil de determinar com precisão, pois depende da sequência de intervalos utilizada. Em geral, é significativamente melhor que O(N^2) e, para certas sequências, pode ser próximo de O(N log^2 N) ou O(N^(3/2)). É um algoritmo eficiente para arrays de tamanho médio e possui baixa sobrecarga.
Ordenação por Seleção Direta
A ordenação por seleção direta funciona selecionando repetidamente o menor (ou maior) elemento da parte não ordenada do array e colocando-o no início (ou fim) da parte ordenada. O processo se repete até que todo o array esteja ordenado.
Versão 1: Simples (Seleção do Menor)
// Algoritmo de Ordenação por Seleção Direta (versão 1 - simples)
void ordenarPorSelecaoSimples(int* dados, int tamanho) {
// Itera do primeiro ao penúltimo elemento
for (int i = 0; i < tamanho - 1; ++i) {
int indiceMenor = i; // Assume que o elemento atual é o menor
// Encontra o índice do menor elemento no restante do array
for (int j = i + 1; j < tamanho; ++j) {
if (dados[j] < dados[indiceMenor]) {
indiceMenor = j;
}
}
// Se o menor elemento não estiver na posição correta, troca
if (indiceMenor != i) {
trocar(&dados[i], &dados[indiceMenor]);
}
}
}
Versão 2: Com Dois Ponteiros (Seleção de Menor e Maior)
// Algoritmo de Ordenação por Seleção Direta (versão 2 - com dois ponteiros)
void ordenarPorSelecaoDupla(int* dados, int tamanho) {
int inicio = 0;
int fim = tamanho - 1;
while (inicio < fim) {
int indiceMax = inicio; // Assumimos que o máximo e o mínimo estão no início
int indiceMin = inicio;
// Procura pelo índice do maior e menor elemento no sub-array [inicio, fim]
for (int k = inicio + 1; k <= fim; ++k) {
if (dados[k] > dados[indiceMax]) {
indiceMax = k;
}
if (dados[k] < dados[indiceMin]) {
indiceMin = k;
}
}
// Caso especial: se o maior elemento estiver na posição 'inicio'
// e ele for trocado com o 'indiceMin', o 'indiceMax' original se move.
// Precisamos ajustar 'indiceMax' para apontar para a nova posição do maior valor
if (indiceMax == inicio) {
indiceMax = indiceMin;
}
// Troca o menor elemento para a posição 'inicio'
trocar(&dados[inicio], &dados[indiceMin]);
// Troca o maior elemento para a posição 'fim'
trocar(&dados[fim], &dados[indiceMax]);
inicio++;
fim--;
}
}
Ambas as versões da ordenação por seleção direta têm uma complexidade de tempo de O(N^2). O número de comparações é aproximadamente N^2/2, e o número de trocas é N (para a versão simples) ou N/2 (para a versão dupla). Embora conceitualmente simples, não é efciiente para grandes conjuntos de dados.
Heapsort
A ordenação por Heap (Heapsort) utiliza a estrutura de dados de heap (pilha) para realizar a ordenação. É uma forma de ordenação por seleção, onde o maior (ou menor) elemento é repetidamente extraído da heap e colocado no final (ou início) do array. Para ordenar em ordem crescente, constrói-se uma max-heap; para ordem decrescente, uma min-heap.
Ordenação por Bolha
A ordenação por bolha (Bubble Sort) é um algoritmo de ordenação comparativo que opera repetidamente percorrendo a lista, comparando pares de elementos adjacentes e trocando-os se estiverem na ordem errada. Os elementos maiores "borbulham" para o final da lista em cada passagem.
// Algoritmo de Ordenação por Bolha
void ordenarPorBolha(int* dados, int tamanho) {
// Loop externo para o número de passes
for (int i = 0; i < tamanho - 1; ++i) {
int houveTroca = 0; // Flag para otimização: se nenhuma troca ocorrer, o array está ordenado
// Loop interno para comparar e trocar elementos adjacentes
// A cada pass, o maior elemento 'borbulha' para a posição final correta,
// então não precisamos verificar os últimos 'i' elementos.
for (int j = 0; j < tamanho - 1 - i; ++j) {
if (dados[j] > dados[j + 1]) {
trocar(&dados[j], &dados[j + 1]);
houveTroca = 1; // Marca que houve uma troca
}
}
// Se nenhuma troca ocorreu nesta passagem, o array está ordenado
if (houveTroca == 0) {
break;
}
}
}
A complexidade de tempo do Bubble Sort é O(N^2) no pior e médio caso. No melhor caso (array já ordenado), a complexidade é O(N) devido à otimização da flag de troca. Devido ao seu desempenho quadrático, é raramente usado na prática para grandes conjuntos de dados, sendo mais utilizado para fins didáticos.
Quicksort
Quicksort é um algoritmo de ordenação de divisão e conquista altamente eficiente, desenvolvido por C.A.R. Hoare. Ele funciona selecionando um 'pivô' do array e particionando os outros elementos em dois sub-arrays, de acordo com serem menores ou maiores que o pivô. Os sub-arrays são então ordenados recursivamente. Este processo se repete até que todo o array esteja ordenado.
Versão Recursiva
O coração do Quicksort é a função de particionamento, que reorganiza o sub-array de modo que todos os elementos menores que o pivô venham antes dele e todos os elementos maiores venham depois. Existem várias estratégias de particionamento.
Particionamento de Hoare
A estratégia de particionamento de Hoare utiliza dois ponteiros, um começando da esquerda e outro da direita do sub-array. O ponteiro esquerdo avança procurando um elemento maior que o pivô, e o ponteiro direito retrocede procurando um elemento menor que o pivô. Quando ambos são encontrados, os elementos são trocados. Este processo continua até que os ponteiros se cruzem ou se encontrem. No final, o pivô é colocado em sua posição final.
// Particionamento de Hoare
int particionarHoare(int* dados, int inicio, int fim) {
int pivo = dados[inicio]; // Escolhe o primeiro elemento como pivô
int ptrEsquerda = inicio;
int ptrDireita = fim;
while (ptrEsquerda < ptrDireita) {
// Move ptrDireita para a esquerda enquanto o elemento for maior ou igual ao pivô
// (Encontrando um elemento menor que o pivô)
while (ptrEsquerda < ptrDireita && dados[ptrDireita] >= pivo) {
ptrDireita--;
}
// Move ptrEsquerda para a direita enquanto o elemento for menor ou igual ao pivô
// (Encontrando um elemento maior que o pivô)
while (ptrEsquerda < ptrDireita && dados[ptrEsquerda] <= pivo) {
ptrEsquerda++;
}
// Se os ponteiros não se cruzaram, troca os elementos
if (ptrEsquerda < ptrDireita) {
trocar(&dados[ptrEsquerda], &dados[ptrDireita]);
}
}
// Coloca o pivô em sua posição final
trocar(&dados[inicio], &dados[ptrDireita]);
return ptrDireita; // Retorna o índice final do pivô
}
Particionamento de Lomuto (Método do Buraco)
A técnica de "挖坑法" (método do buraco) é uma variação da partição Lomuto. Ela seleciona um pivô e cria um "buraco" em sua posição. Em seguida, percorre o array da direita para a esquerda, procurando um elemento menor que o pivô para preencher o buraco da esquerda. O elemento movido cria um novo buraco. Depois, percorre da esquerda para a direita, procurando um elemento maior que o pivô para preencher o buraco da direita, e assim sucessivamente, alternando os sentidos até que os ponteiros se encontrem.
// Particionamento de Lomuto (Método do Buraco / "Pit-Filling")
int particionarLomuto(int* dados, int inicio, int fim) {
int pivoValor = dados[inicio]; // Escolhe o primeiro elemento como pivô
int indiceBuraco = inicio; // A posição inicial do "buraco"
int ptrEsquerda = inicio;
int ptrDireita = fim;
while (ptrEsquerda < ptrDireita) {
// Da direita para a esquerda: Encontra um elemento menor que o pivô
while (ptrEsquerda < ptrDireita && dados[ptrDireita] >= pivoValor) {
ptrDireita--;
}
// Se encontrou, move o elemento para a posição do buraco
// e o novo buraco é a posição de onde o elemento veio
if (ptrEsquerda < ptrDireita) {
dados[indiceBuraco] = dados[ptrDireita];
indiceBuraco = ptrDireita;
}
// Da esquerda para a direita: Encontra um elemento maior que o pivô
while (ptrEsquerda < ptrDireita && dados[ptrEsquerda] <= pivoValor) {
ptrEsquerda++;
}
// Se encontrou, move o elemento para a posição do buraco
// e o novo buraco é a posição de onde o elemento veio
if (ptrEsquerda < ptrDireita) {
dados[indiceBuraco] = dados[ptrEsquerda];
indiceBuraco = ptrEsquerda;
}
}
// No final, coloca o valor do pivô no último buraco
dados[indiceBuraco] = pivoValor;
return indiceBuraco; // Retorna o índice final do pivô
}
Particionamento de Lomuto (Ponteiros Anterior/Atual)
O método de ponteiros "anterior e atual" (front-back pointers) para particionamento Lomuto utilliza dois ponteiros, 'anterior' e 'atual'. O ponteiro 'atual' percorre o array. Se um elemento menor ou igual ao pivô for encontrado, o ponteiro 'anterior' é incrementado e o elemento é trocado com o elemento na posição 'anterior'. Ao final, o pivô é trocado com o elemento na posição 'anterior', garantindo que todos os elementos à esquerda do pivô sejam menores ou iguais a ele.
// Particionamento de Lomuto (Ponteiros Anterior/Atual)
int particionarLomutoPonteiros(int* dados, int inicio, int fim) {
int pivo = dados[fim]; // Escolhe o último elemento como pivô
int indiceMenor = inicio - 1; // 'indiceMenor' rastreia o final da sub-array de elementos menores ou iguais ao pivô
// Itera sobre o array da esquerda para a direita, até o elemento antes do pivô
for (int j = inicio; j < fim; ++j) {
if (dados[j] <= pivo) {
indiceMenor++; // Expande a sub-array de elementos menores ou iguais
trocar(&dados[indiceMenor], &dados[j]); // Troca o elemento para a posição correta
}
}
// Coloca o pivô em sua posição final correta
trocar(&dados[indiceMenor + 1], &dados[fim]);
return indiceMenor + 1; // Retorna o índice final do pivô
}
// Função principal recursiva do Quicksort (usando particionamento de Hoare)
void quickSort(int* dados, int inicio, int fim) {
if (inicio >= fim) {
return; // Caso base: sub-array com 0 ou 1 elemento já está ordenado
}
// Escolha um método de particionamento:
// int indicePivo = particionarHoare(dados, inicio, fim);
// int indicePivo = particionarLomuto(dados, inicio, fim);
int indicePivo = particionarLomutoPonteiros(dados, inicio, fim);
// Ordena recursivamente os sub-arrays à esquerda e à direita do pivô
quickSort(dados, inicio, indicePivo - 1);
quickSort(dados, indicePivo + 1, fim);
}
Complexidade de Tempo
A complexidade de tempo do Quicksort é O(N log N) no caso médio, tornando-o um dos algoritmos de ordenação mais rápidos para grandes conjuntos de dados. No pior caso (ocorre quando o pivô é consistentemente o menor ou o maior elemento, por exemplo, em um array já ordenado), a complexidade é O(N^2). Técnicas como a escolha de um pivô aleatório ou o pivô da mediana de três elementos ajudam a mitigar o pior caso.
Versão Não-Recursiva
Uma versão não recursiva do Quicksort pode ser implementada utilizando uma pilha explícita para armazenar os intervalos dos sub-arrays que precisam ser particionados. O algoritmo empilha os limites dos sub-arrays, e então desempilha-os sequencialmente para realizar o particionamento, empilhando os novos sub-arrays resultantes até que a pilha esteja vazia.
// --- Definição de uma pilha simples para o Quicksort Não-Recursivo ---
#define MAX_STACK_SIZE 100 // Ajuste conforme a necessidade (logN é o máximo de profundidade)
typedef struct {
int* elementos;
int topo;
int capacidade;
} PilhaInt;
void inicializarPilha(PilhaInt* p, int capacidade) {
p->elementos = (int*)malloc(sizeof(int) * capacidade);
if (p->elementos == NULL) {
perror("Erro ao alocar memória para a pilha");
exit(EXIT_FAILURE);
}
p->topo = -1;
p->capacidade = capacidade;
}
void destruirPilha(PilhaInt* p) {
free(p->elementos);
p->elementos = NULL;
p->topo = -1;
p->capacidade = 0;
}
int pilhaVazia(const PilhaInt* p) {
return p->topo == -1;
}
void empilhar(PilhaInt* p, int valor) {
if (p->topo >= p->capacidade - 1) {
fprintf(stderr, "Erro: Pilha cheia. Aumente MAX_STACK_SIZE.\n");
exit(EXIT_FAILURE);
}
p->elementos[++(p->topo)] = valor;
}
int desempilhar(PilhaInt* p) {
if (pilhaVazia(p)) {
fprintf(stderr, "Erro: Pilha vazia.\n");
exit(EXIT_FAILURE);
}
return p->elementos[(p->topo)--];
}
// Particionamento padrão de Hoare para Quicksort Não-Recursivo
int particionarNaoRecursivo(int* dados, int inicio, int fim) {
int pivo = dados[inicio]; // Pivô como o primeiro elemento
int ptrEsquerda = inicio;
int ptrDireita = fim;
while (ptrEsquerda < ptrDireita) {
while (ptrEsquerda < ptrDireita && dados[ptrDireita] >= pivo) {
ptrDireita--;
}
while (ptrEsquerda < ptrDireita && dados[ptrEsquerda] <= pivo) {
ptrEsquerda++;
}
if (ptrEsquerda < ptrDireita) {
trocar(&dados[ptrEsquerda], &dados[ptrDireita]);
}
}
trocar(&dados[inicio], &dados[ptrDireita]);
return ptrDireita;
}
// Algoritmo Quicksort Não-Recursivo
void quickSortNaoRecursivo(int* dados, int inicioOriginal, int fimOriginal) {
PilhaInt pilhaSubArrays;
inicializarPilha(&pilhaSubArrays, MAX_STACK_SIZE);
// Empilha os limites do array original
empilhar(&pilhaSubArrays, inicioOriginal);
empilhar(&pilhaSubArrays, fimOriginal);
while (!pilhaVazia(&pilhaSubArrays)) {
// Desempilha os limites do sub-array a ser processado
int fim = desempilhar(&pilhaSubArrays);
int inicio = desempilhar(&pilhaSubArrays);
// Realiza o particionamento
if (inicio < fim) { // Só particiona se houver mais de um elemento
int indicePivo = particionarNaoRecursivo(dados, inicio, fim);
// Empilha os sub-arrays resultantes (se existirem e tiverem mais de um elemento)
// Empilhando o maior sub-array primeiro (direita), depois o menor (esquerda),
// para que o menor seja processado primeiro e minimize a profundidade da pilha.
if (indicePivo + 1 < fim) {
empilhar(&pilhaSubArrays, indicePivo + 1);
empilhar(&pilhaSubArrays, fim);
}
if (inicio < indicePivo - 1) {
empilhar(&pilhaSubArrays, inicio);
empilhar(&pilhaSubArrays, indicePivo - 1);
}
}
}
destruirPilha(&pilhaSubArrays);
}
Mergesort
Mergesort (Ordenação por Intercalação) é um algoritmo de ordenação de divisão e conquista. Ele divide repetidamente o array em duas metades até que cada sub-array contenha apenas um elemento (que é considerado ordenado). Em seguida, mescla (intercala) essas sub-arrays de forma ordenada, combinando-as para produzir sub-arrays maiores e ordenadas, até que todo o array esteja ordenado.
// Função de intercalação (merge) para Mergesort
void intercalar(int* dados, int inicio, int meio, int fim, int* arrayTemporario) {
int ptr1 = inicio; // Ponteiro para a primeira sub-array
int ptr2 = meio + 1; // Ponteiro para a segunda sub-array
int indiceTemp = inicio; // Índice para o array temporário
// Enquanto houver elementos em ambas as sub-arrays
while (ptr1 <= meio && ptr2 <= fim) {
if (dados[ptr1] <= dados[ptr2]) {
arrayTemporario[indiceTemp++] = dados[ptr1++];
} else {
arrayTemporario[indiceTemp++] = dados[ptr2++];
}
}
// Copia os elementos restantes da primeira sub-array (se houver)
while (ptr1 <= meio) {
arrayTemporario[indiceTemp++] = dados[ptr1++];
}
// Copia os elementos restantes da segunda sub-array (se houver)
while (ptr2 <= fim) {
arrayTemporario[indiceTemp++] = dados[ptr2++];
}
// Copia os elementos ordenados do array temporário de volta para o array original
for (int k = inicio; k <= fim; ++k) {
dados[k] = arrayTemporario[k];
}
}
// Algoritmo Mergesort (recursivo)
void mergesortRecursivo(int* dados, int inicio, int fim, int* arrayTemporario) {
if (inicio >= fim) {
return; // Caso base: sub-array com 0 ou 1 elemento já está ordenado
}
int meio = inicio + (fim - inicio) / 2; // Evita overflow para grandes valores de inicio e fim
// Divide recursivamente
mergesortRecursivo(dados, inicio, meio, arrayTemporario);
mergesortRecursivo(dados, meio + 1, fim, arrayTemporario);
// Intercala as duas metades ordenadas
intercalar(dados, inicio, meio, fim, arrayTemporario);
}
// Função wrapper para Mergesort
void mergesort(int* dados, int tamanho) {
// Aloca um array temporário uma única vez para a operação de intercalação
int* arrayTemporario = (int*)malloc(tamanho * sizeof(int));
if (arrayTemporario == NULL) {
perror("Falha na alocação de memória para array temporário");
exit(EXIT_FAILURE);
}
// Chama a função recursiva principal
mergesortRecursivo(dados, 0, tamanho - 1, arrayTemporario);
// Libera a memória do array temporário
free(arrayTemporario);
}
A complexidade de tempo do Mergesort é O(N log N) em todos os casos (melhor, médio e pior), pois o processo de divisão e intercalação sempre leva o mesmo tempo. Ele garante um desempenho consistente e é um algoritmo de ordenação estável. Sua principal desvantagem é a necessidade de espaço adicional de O(N) para o array temporário.
Comparação de Desempenho
Entre os algoritmos de ordenação comparativa, Quicksort e Heapsort são geralmente considerados os mais eficientes em termos de tempo de execução médio, ambos com complexidade O(N log N). Algoritmos como Insertion Sort, Selection Sort e Bubble Sort são mais simples de implementar, mas sua complexidade de O(N^2) os torna inadequados para grandes volumes de dados. Mergesort, embora também O(N log N), tem a desvantagem de requerer espaço adicional.
Ordenação Não Comparativa: Counting Sort
A ordenação por contagem (Counting Sort) é um algoritmo de ordenação não comparativa que funciona bem quando o intervalo dos números a serem ordenados é relativamente pequeno. Ele opera contando o número de ocorrências de cada elemento distinto na entrada e usando essas contagens para determinar as posições finais de cada elemento na saída ordenada.
// Algoritmo de Ordenação por Contagem
void ordenarPorContagem(int* dados, int tamanho) {
if (tamanho <= 1) return;
// 1. Encontrar o valor mínimo e máximo no array
int minValor = dados[0];
int maxValor = dados[0];
for (int i = 1; i < tamanho; ++i) {
if (dados[i] < minValor) {
minValor = dados[i];
}
if (dados[i] > maxValor) {
maxValor = dados[i];
}
}
// 2. Calcular o tamanho do array de contagem
int alcance = maxValor - minValor + 1;
int* arrayContagem = (int*)calloc(alcance, sizeof(int)); // calloc inicializa com zeros
if (arrayContagem == NULL) {
perror("Falha na alocação de memória para array de contagem");
exit(EXIT_FAILURE);
}
// 3. Contar a frequência de cada elemento
for (int i = 0; i < tamanho; ++i) {
arrayContagem[dados[i] - minValor]++;
}
// 4. Reconstruir o array original ordenado
int indiceDados = 0; // Índice para o array 'dados'
for (int i = 0; i < alcance; ++i) {
// Para cada valor 'i + minValor', insira-o 'arrayContagem[i]' vezes no array original
while (arrayContagem[i] > 0) {
dados[indiceDados++] = i + minValor;
arrayContagem[i]--;
}
}
// 5. Liberar a memória do array de contagem
free(arrayContagem);
}
A complexidade de tempo da Ordenação por Contagem é O(N + K), onde N é o número de elementos e K é o intervalo (maxValor - minValor + 1). É muito eficiente quando K é pequeno em relação a N, mas pode ser impraticável se o intervalo de valores for muito grande devido à necessidade de alocação de memória para o array de contagem.
Análise de Complexidade e Estabilidade
A estabilidade de um algoritmo de ordenação refere-se à sua capacidade de preservar a ordem relativa de elementos com chaves iguais. Um algoritmo é considerado estável se, para quaisquer dois elementos 'a' e 'b' com o mesmo valor de chave, onde 'a' aparece antes de 'b' na entrada original, 'a' também aparece antes de 'b' na saída ordenada.
Em termos de complexidade, algoritmos como Mergesort, Quicksort (caso médio) e Heapsort oferecem O(N log N). Insertion Sort, Selection Sort e Bubble Sort são O(N^2). Já o Counting Sort apresenta O(N+K). Quanto à estabilidade, Insertion Sort, Bubble Sort e Mergesort são tipicamente estáveis. Quicksort e Heapsort são geralmente instáveis, enquanto Selection Sort é instável.
Resumo dos Algoritmos de Ordenação
Em suma, os algoritmos de ordenação podem ser amplamente categorizados por suas operações principais. A ordenação por inserção foca em mover (atribuir) um elemento para sua posição correta dentro de uma porção já ordenada. A ordenação por seleção identifica repetidamente o menor (ou maior) elemento e o troca (swap) para sua posição final. Os algoritmos de troca, como o Bubble Sort e Quicksort, baseiam-se na comparação e permuta de elementos com base na sua ordem relativa. A escolha do algoritmo ideal depende das características dos dados (tamanho, intervalo de valores, pré-ordenação) e dos requisitos de desempenho (tempo, espaço, estabilidade).