Ordenação QuickSort [C/C++]

Ordenação QuickSort

Publicado por Perfil removido (última atualização em 17/06/2010)

[ Hits: 66.824 ]

Download 4635.QuickSort.c

6 0

Denuncie Favoritos Indicar

Ordena um vetor usando o método de ordenação QuickSort.

Esconder código-fonte

#include<stdio.h>
void Quick(int vetor[10], int inicio, int fim);
int main(){
   
   int vetor[10] = {7, 9, 4, 3, 6, 1, 18, 2, 10, 5};
   
   int i;   
   printf("Vetor desordenado:\n");
   for(i = 0; i < 10; i++){
      printf("%d ", vetor[i]);
   }
   printf("\n");   
   
   Quick(vetor, 0, 9);
   
   printf("Vetor ordenado:\n");
   for(i = 0; i < 10; i++){
      printf("%d ", vetor[i]);
   }
   printf("\n");   
}

void Quick(int vetor[10], int inicio, int fim){
   
   int pivo, aux, i, j, meio;
   
   i = inicio;
   j = fim;
   
   meio = (int) ((i + j) / 2);
   pivo = vetor[meio];
   
   do{
      while (vetor[i] < pivo) i = i + 1;
      while (vetor[j] > pivo) j = j - 1;
      
      if(i <= j){
         aux = vetor[i];
         vetor[i] = vetor[j];
         vetor[j] = aux;
         i = i + 1;
         j = j - 1;
      }
   }while(j > i);
   
   if(inicio < j) Quick(vetor, inicio, j);
   if(i < fim) Quick(vetor, i, fim);   

}

Scripts recomendados

Jogo da Forca em C

Soma dos dígitos de um número decimal

Conversão do número de dias em anos (meu segundo programa em C)

Cálculo da circunferência de um círculo

Calcula valor da prestação atrasada

Comentários

[1] Comentário enviado por Ezequias Rocha em 23/06/2010 - 07:57h

No wikipedia também há um exemplo:

Quick Sort in c++

#include < iostream.h >
#include < stdio.h >
#include < conio.h >

void print(int a[]) {
for (int i = 0; i < 10; i++) {
cout << a[i] << "-";
}
cout << endl;
}

int partition(int a[], int p, int r) {
int x = a[r];
int j = p - 1;
for (int i = p; i < r; i++) {

if (x <= a[i]) {
j = j + 1;
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
a[r] = a[j + 1];
a[j + 1] = x;

return (j + 1);
}

void quickSort(int a[], int p, int r) {
if (p < r) {
int q = partition(a, p, r);
quickSort(a, p, q - 1);
quickSort(a, q + 1, r);
}
}

void main() {

int a[] = {
1, 9, 0, 5, 6, 7, 8, 2, 4, 3};
quickSort(a, 0, 9);
print(a);
getch();
}

Obs: Para aplicações embarcadas, alguns ambientes podem não aceitar a versão recursiva (problemas de gerenciamento de stack, ponteiros, etc), deve-se optar por uma modificação, se houver.

Ezequias Rocha

2 0