-
Notifications
You must be signed in to change notification settings - Fork 0
/
Quicksort.c
78 lines (60 loc) · 1.46 KB
/
Quicksort.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// Algoritimo de QuickSort
#include<stdlib.h>
#include<stdio.h>
#ifdef WIN32
#define INT64 "%I64d"
#else
#define INT64 "%lld"
#endif
//funções
void qs(long long *vet, long long inicio, long long fim);
long long particiona(long long *vet, long long inicio, long long fim);
//função principal
int main(){
long long n, vet[100000], inicio=0, fim=0, k, j;
scanf(INT64, &n);
for(k=0;k<n;k++){
scanf(INT64, &vet[k]);
}
fim=n-1;
qs(vet, inicio, fim);
for(j=0;j<n;j++){
printf(INT64, vet[j]);
printf(" ");
}
printf("\n");
return 0;
}
void qs(long long *vet, long long inicio, long long fim){
long long pivo;
if(fim>inicio){
pivo=particiona(vet, inicio, fim );
qs(vet, inicio, pivo-1);
qs(vet, pivo+1, fim);//fim ja é n-1
}
}
long long particiona(long long *vet, long long inicio, long long fim){
long long aux, direita, esquerda, pivo;
esquerda=inicio;
direita=fim;
pivo=vet[inicio];
while(esquerda<direita){
//veloresXindices
//anda a esquerda
while(vet[esquerda]<=pivo && esquerda<=fim){
esquerda++;
}
//anda a direita
while(vet[direita]>pivo){
direita--;
}
if(esquerda<direita){
aux=vet[esquerda];
vet[esquerda]=vet[direita];
vet[direita]=aux;
}
}
vet[inicio]=vet[direita];
vet[direita]=pivo;
return direita;
}