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

Ordenação QuickSort

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

[ Hits: 66.492 ]

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

Inserir e remover caracter da matriz

Equação dos Gases Ideais

Teorema de Pitágoras em C++

Sequência de Fibonacci

Uma implementação do HeapSort

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