Você está aqui: C ::: Dicas & Truques ::: Ordenação e Pesquisa (Busca)

Como implementar a ordenação Quicksort em C - Apostila de C para iniciantes

Quantidade 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

Link para compartilhar na Internet ou com seus amigos:

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

E-Book 350 Exercícios Resolvidos de Java - PDF com 500 páginas
Domine lógica de programação e a linguagem Java com o nosso E-Book 350 Exercícios Exercícios de Java, para você estudar onde e quando quiser.

Este e-book contém exercícios resolvidos abrangendo os tópicos: Java básico, matemática e estatística, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.
Ver Conteúdo do E-book
E-Book 650 Dicas, Truques e Exercícios Resolvidos de Python - PDF com 1.200 páginas
Domine lógica de programação e a linguagem Python com o nosso E-Book 650 Dicas, Truques e Exercícios Exercícios de Python, para você estudar onde e quando quiser.

Este e-book contém dicas, truques e exercícios resolvidos abrangendo os tópicos: Python básico, matemática e estatística, banco de dados, programação dinâmica, strings e caracteres, entrada e saída, estruturas condicionais, vetores e matrizes, funções, laços, recursividade, internet, arquivos e diretórios, programação orientada a objetos e muito mais.
Ver Conteúdo do E-book

Linguagens Mais Populares

1º lugar: Java
2º lugar: Python
3º lugar: C#
4º lugar: PHP
5º lugar: C
6º lugar: Delphi
7º lugar: JavaScript
8º lugar: C++
9º lugar: VB.NET
10º lugar: Ruby



© 2025 Arquivo de Códigos - Todos os direitos reservados
Neste momento há 56 usuários muito felizes estudando em nosso site.