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: 327 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: #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 |
E-Books em PDF |
||||
|
||||
|
||||
Linguagens Mais Populares |
||||
1º lugar: Java |