Quicksort: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Na forma que estava escrito, a complexidade do algoritmo seria O(N*N*log), o que não faz sentido, o correto seria O(N*log(N)) |
Adição do codigo em C |
||
Linha 186:
return 0;
}
</syntaxhighlight>Uma versão em C:
</syntaxhighlight>Tendo os valores como saída respectivamente, desorganizados e organizados através da função ''quicksort'';<syntaxhighlight lang="console">▼
Entra: tamanho do vetor a ser organizado e vetor de números.
Saida: vetor organizado.<syntaxhighlight lang="c++">
#include<stdio.h>
#include<stdlib.h>
void troca (int * x, int * y) {
int aux;
aux = *x;
*x = *y;
*y = aux;
}
int partition (int * v, int p, int r) {
int i, j, pivo;
pivo = v[r-1];
i = p-1;
for (j = p-1; j < r-1; j++)
if (v[j] <= pivo) {
troca (&v[i], &v[j]);
i++;
}
troca (&v[i], &v[r-1]);
return i+1;
}
void quicksort(int * v, int p, int r) {
int q;
if (p < r) {
q = partition (v, p, r);
quicksort (v, p, q-1);
quicksort (v, q+1, r);
}
}
int main(){
int *v,*vetor,i,tam,n;
scanf("%d",&tam);
v=(int*)malloc(tam*sizeof(int));
for(i=0;i<tam;i++){
scanf("%d",&v[i]);
}
n=tam;
vetor=(int*)malloc(tam*sizeof(int));
vetor=v;
quicksort (vetor, 1, n);
v=vetor;
for(i=0;i<tam;i++){
printf("%d ",v[i]);
}
return 0;
}
</syntaxhighlight>
▲
5 8 1 2 7 3 6 9 4 10
1 2 3 4 5 6 7 8 9 10
| |||