DoubleQuickSortC/serial.h at master · hectorhmx/DoubleQuickSortC · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>

int obtenerMedio(Lista *A,int p, int r){
	if(r-p == 0){
		return p;
	}
	int medio = p;
	int prom = 0;
	int i;
	for(i=p;i<=r;i++){
		prom +=A->elementos[i];
	}
	prom = prom/(r-p);
	int anterior = NULL;
	int actual;
	for(int i = p;i<=r;i++){
		actual = prom - A->elementos[i];
		if(anterior = NULL 	|| anterior > abs(actual)){
			anterior = abs(actual);
			medio = i;
		}
	}
	return medio;
}

int particionar(Lista *A,int p,int r){
	int x = A->elementos[r];
	int j = p-1;
	int i;
	for(i=p;i<r;i++){
		if(A->elementos[i]<=x){
			j+=1;
			swap(A,i,j);
		}
	}
	swap(A,j+1,r);
	return j+1;
}
int particionarB(Lista *A,int p,int r){
	int y =obtenerMedio(A,p,r);
	swap(A,y,r);
	int x = A->elementos[r];
	int j = p-1;
	int i;
	for(i=p;i<r;i++){
		if(A->elementos[i]<=x){
			j+=1;
			swap(A,i,j);
		}
	}
	swap(A,j+1,r);
	return j+1;
}


void quickSort(Lista *A,int p,int r){
	if(p<r){
		int q;
		q = particionar(A,p,r);
		quickSort(A,p,q-1);
		quickSort(A,q+1,r);
	}
}

void quickSortB(Lista *A,int p,int r){
	if(p<r){
		int q;
		q = particionarB(A,p,r);
		quickSortB(A,p,q-1);
		quickSortB(A,q+1,r);
	}
}

void doubleQuickSort(Lista *A){
    int contdir = 0,continv = 0;
    for(int i = 1;i < A->tam;i++){
        if(A->elementos[i-1] <= A->elementos[i]){
            contdir+=1;
        }
    }
    if(contdir == A->tam -1){
        return;
    }
    for(int i = 1;i < A->tam;i++){
        if(A->elementos[i-1] >= A->elementos[i]){
            continv+=1;
        }
    }
    if(continv == A->tam -1){
        int i;
        for(i = 0;i<A->tam/2;i++){
            swap(A,i,A->tam-1-i);
        }
        return;
    }
    double cerc = 1.7;
    if((continv >= (A->tam-1)/cerc) || (contdir >= (A->tam-1)/cerc)){
        /*
		printf("######################\n");
        printf("quickSortB");
        printf("######################\n");
		*/
        quickSortB(A,0,A->tam-1);
    }
	else{
		/*
        printf("######################\n");
        printf("quickSort\n");
        printf("######################\n");
		*/
        quickSort(A,0,A->tam-1);
    }
}