prog 2 - quicksort sem pivo

Prévia do material em texto

1: #include<stdio.h>
2: #include<stdlib.h>
3: #include<time.h>
4: #include<stdbool.h>
5: #define TF 50
6: #define MAX 9999
7: 
8: void cria(int vetor[TF]);
9: void exibe(int vetor[TF], int tl);
10: void quickSort(int vetor[TF], int inicio, int fim);
11: 
12: 
13: int main(){
14: 
15: int vetor[TF];
16: int opcao;
17: bool ordenado = false;
18: int posicao = 0;
19: 
20: while(opcao != 4) {
21: 
22: printf("1-Cria o vetor\n");
23: printf("2-Exibe o vetor\n");
24: printf("3-QUICKSORT\n");
25: printf("4-Sair do programa\n");
26: printf("Digite a opcao?");
27: scanf("%d", &opcao);
28: 
29: switch(opcao) {
30: 
31: case 1: cria(vetor);
32: break;
33: 
34: case 2: exibe(vetor, TF);
35: break;
36: 
37: case 3: quickSort(vetor, 0, TF - 1);
38: ordenado = true;
39: break;
40: }
41: }
42: }
43: 
44: 
45: void cria(int vetor[TF]){
46: 
47: int i;
48: 
49: for(i = 0; i < TF; i++)
50: 
51: vetor[i] = rand() % MAX;
52: }
53: 
54: void exibe(int vetor[TF], int tl){
55: 
56: int i;
57: 
58: for(i = 0; i < tl; i++)
59: printf("[%d] = %d\n", i, vetor[i]);
60: }
61: 
62: void quickSort(int vetor[TF], int inicio, int fim){
63: 
64: int i = inicio;
65: int j = fim;
66: int aux;
67: 
68: do {
69: 
70: while((vetor[i] <= vetor[j]) && (i != j))
71: i++;
72: aux = vetor[i];
73: vetor[i] = vetor[j];
74: vetor[j] = aux;
75: 
76: 
77: while((vetor[i] <= vetor[j]) && (i != j))
78: j--;
79: aux = vetor[i];
80: vetor[i] = vetor[j];
81: vetor[j] = aux;
82: 
83: //i++;
84: //j--;
85: 
86: }while(i != j);
87: 
88: if(j > inicio)
89: quickSort(vetor, inicio, i - 1);//sublista da esquerda
90: if(i < fim)
91: quickSort(vetor, i + 1, fim);//sublista da direita
92: }