Ordenação QuickSort
Ordena um vetor usando o método de ordenação QuickSort.
Descrição
Ordena um vetor usando o método de ordenação QuickSort.
#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);
}
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