Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca) |
Como implementar a ordenação Quicksort em C - Apostila de C para iniciantesQuantidade de visualizações: 393 vezes |
|
A ordenação Quicksort é um dos algorítmos de ordenação mais encontrados em aplicações reais de programação. No Delphi esta ordenação é encontrada no objeto TList. No Java podemos encontrá-lo no método Arrays.sort(). Na linguagem C a ordenação Quicksort é implementada na função qsort() da biblioteca padrão. O algoritmo de ordenação Quicksort é do tipo dividir para conquistar (divide-and-conquer principle). Neste tipo de algoritmo o problema é dividido em sub-problemas e a solução é concatenada quando as chamadas recursivas atingirem o caso base. O vetor (ou array) a ser ordenado é dividido em duas sub-listas por um elemento chamado pivô, resultando em uma lista com elementos menores que o pivô e outra lista com os elementos maiores que o pivô. Esse processo é repetido para cada chamada recursiva. Sim, a ordenação Quicksort faz uso extensivo de recursividade, razão pela qual devemos ter muito cuidado para não estourar a pilha do sistema. Existem muitos estudos sobre o pivô ideal para a ordenação Quicksort. Nessa dica adotarei o último elemento do array ou sub-array como pivô. Em vetores não ordenados essa estratégia, em geral, resulta em uma boa escolha. Vamos ao código C então? Veja um programa C completo demonstrando o uso da ordenação Quicksort para um array de 10 elementos inteiros: ----------------------------------------------------------------------
Se precisar de ajuda com o código abaixo, pode me chamar
no WhatsApp +55 (62) 98553-6711 (Osmar)
----------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
// função de implementação da ordenação Quicksort
void quick_sort(int vetor[], int inicio, int fim) {
int indice_particao;
// o início é menor que o fim?
if (inicio < fim) {
// vamos obter o novo índice da partição
indice_particao = particionar(vetor, inicio, fim);
// efetuamos novas chamadas recursivas
quick_sort(vetor, inicio, indice_particao - 1);
quick_sort(vetor, indice_particao + 1, fim);
}
}
// função que retorna o índice de partição
int particionar(int vetor[], int inicio, int fim) {
// para guardar o pivô
int pivot = vetor[fim];
int i = (inicio - 1);
int j, temp;
for (j = inicio; j < fim; j++) {
if (vetor[j] <= pivot) {
i++;
// fazemos a troca
temp = vetor[i];
vetor[i] = vetor[j];
vetor[j] = temp;
}
}
// efetua a troca
temp = vetor[i + 1];
vetor[i + 1] = vetor[fim];
vetor[fim] = temp;
return i + 1;
}
// função principal do programa
int main(int argc, char *argv[]){
// vamos declarar um array de 10 elementos
int valores[10];
int i;
// vamos pedir ao usuário para informar os valores para o vetor
for(i = 0; i < 10; i++){
printf("Informe o valor do elemento %d: ", i);
scanf("%d", &valores[i]);
}
// vamos mostrar o array informado
printf("\nO array informado foi:\n\n");
for(i = 0; i < 10; i++){
printf("%d ", valores[i]);
}
// vamos ordenar o vetor usando a ordenação Quicksort
quick_sort(valores, 0, 10 - 1);
// vamos mostrar o array ordenado
printf("\n\nO array ordenado é:\n\n");
for(i = 0; i < 10; i++){
printf("%d ", valores[i]);
}
printf("\n\n");
system("PAUSE");
return 0;
}
Ao executar este código C nós teremos o seguinte resultado: Informe o valor do elemento 0: 7 Informe o valor do elemento 1: 2 Informe o valor do elemento 2: 43 Informe o valor do elemento 3: 1 Informe o valor do elemento 4: 9 Informe o valor do elemento 5: 6 Informe o valor do elemento 6: 22 Informe o valor do elemento 7: 3 Informe o valor do elemento 8: 37 Informe o valor do elemento 9: 5 O array informado foi: 7 2 43 1 9 6 22 3 37 5 O array ordenado é: 1 2 3 5 6 7 9 22 37 43 |
|
|
Desafios, Exercícios e Algoritmos Resolvidos de C |
Veja mais Dicas e truques de C |
Dicas e truques de outras linguagens |
|
JavaScript - Validação de formulários em JavaScript - Como validar um formulário contendo usuário e senha em JavaScript |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
|
1º lugar: Java |






