Quicksort

[Matheus Weber 4]

To tentando fazer um quicksort aqui, mas por algum motivo ele não ordena, transcrevi o código de português estruturado por C, tentei várias modificações, depurei com printf, e nada =/

 

Se alguém puder me ajudar, segue o código:

 

 

 

 

int partition(int A[],int p,int r){

int j,x,aux,i;

x = A[r];

i = p;

for(j=p; j < r-1; ++j){

if(A[j] < x){

i++;

aux = A;

A = A[j];

A[j] = aux;

}

}

aux = A[i+1];

A[i+1] = A[r];

A[r] = aux;

return i;

}

void quicksort(int A[],int p,int r){

int q;

if(p<r){

q = partition(A,p,r);

quicksort(A,p,q-1);

quicksort(A, q+1, r);

}

}

 

 

 

 

quicksort(vet1,0,TAMANHO);

 

 

Alguns testes:

Vetor desordenado: 
0 - 801047
1 - 749537
2 - 875235
3 - 445025
4 - 40885
 
Vetor ordenado com quick sort: 
0 - 875235
1 - 801047
2 - 40885
3 - 445025
4 - 749537

Vetor desordenado: 
0 - 547342
1 - 31663
2 - 807533
3 - 898793
4 - 458703
 
Vetor ordenado com quick sort: 
0 - 458703
1 - 31663
2 - 458703
3 - 898793
4 - 807533

Vetor desordenado: 
0 - 882433
1 - 478206
2 - 71064
3 - 481412
4 - 45963
 
Vetor ordenado com quick sort: 
0 - 71064
1 - 882433
2 - 45963
3 - 481412
4 - 478206

Compila tudo direitinho, mas não funciona de jeito nenhum =/

[_Isis_ 202]

Compare a sua implementação com esta p/ poder identificar as falhas de transcrição:

 

 

void swap(int* a, int* b) {
  int tmp;
  tmp = *a;
  *a = *b;
  *b = tmp;
}
 
int partition(int vec[], int left, int right) {
  int i, j;
 
  i = left;
  for (j = left + 1; j <= right; ++j) {
    if (vec[j] < vec[left]) {
      ++i;
      swap(&vec[i], &vec[j]);
    }
  }
  swap(&vec[left], &vec[i]);
 
  return i;
}
 
void quickSort(int vec[], int left, int right) {
  int r;
 
  if (right > left) {
    r = partition(vec, left, right);
    quickSort(vec, left, r - 1);
    quickSort(vec, r + 1, right);
  }
}