SHOW:
|
|
- or go back to the newest paste.
1 | /*BIT INDEX SORT DSC*/ | |
2 | ||
3 | #include <stdio.h> | |
4 | #include <stdlib.h> | |
5 | #include <time.h> | |
6 | #define N 10000 | |
7 | ||
8 | int busca_repetidos(int E[], int n) { | |
9 | int i, j; | |
10 | for (i = 0; i < n; i++) { | |
11 | for (j = i + 1; j < n; j++) { | |
12 | if (E[i] == E[j]) | |
13 | return 0; | |
14 | } | |
15 | } | |
16 | return 1; | |
17 | } | |
18 | ||
19 | int cpdelante(unsigned int bit) { | |
20 | int i; | |
21 | int cont = 0; | |
22 | //Se contarán los ceros de la izquierda del 1 más significativo | |
23 | for (i = 0; i < 32; i++) { | |
24 | if ((bit & 1) == 1) //Si se encuentra un 1 más a la derecha | |
25 | cont = 0; //se contará de nuevo | |
26 | else | |
27 | cont++; | |
28 | bit = bit >> 1; //Se mueven los bits a la derecha | |
29 | } | |
30 | return cont; | |
31 | } | |
32 | ||
33 | void bit_index_dsc(int E[], int n) { | |
34 | ||
35 | unsigned int B[N] = {0}; | |
36 | - | int ind = 0; //index (indice) |
36 | + | |
37 | int ind = 0; //index (indice) | |
38 | int off = 0; //offset (desplazamiento)) | |
39 | ||
40 | //Etapa de clasificacion | |
41 | int i; | |
42 | for (i = 0; i < N; i++) { | |
43 | ind = E[i] / 32; | |
44 | off = E[i] % 32; | |
45 | B[ind] |= B[i] | (1 << off); | |
46 | } | |
47 | ||
48 | //Etapa de recuperación | |
49 | int j; | |
50 | i = 0; | |
51 | for (j = (N - 1); j >= 0; j--) { | |
52 | while (B[j] > 0) { | |
53 | off = 31 - cpdelante(B[j]); | |
54 | E[i] = j * 32 + off; | |
55 | B[j] -= (1 << off); | |
56 | i++; | |
57 | } | |
58 | } | |
59 | } | |
60 | ||
61 | void imprime_ordenado(int E[], int n) { | |
62 | int i; | |
63 | for (i = 0; i < n; i++) { | |
64 | printf("%d ", E[i]); | |
65 | } | |
66 | printf("\n"); | |
67 | } | |
68 | ||
69 | int main(int argc, char** argv) { | |
70 | int n = -1; | |
71 | clock_t begin, end; | |
72 | double time_spent; | |
73 | - | while (n) { |
73 | + | |
74 | - | printf("Ingrese el numero de datos del arreglo:\n"); |
74 | + | |
75 | ||
76 | - | scanf("%d", &n); |
76 | + | //while (n) { |
77 | printf("Ingrese el numero de datos del arreglo:\n"); | |
78 | - | if (n > 0) { |
78 | + | |
79 | - | printf("Ingrese los valores a ordenar:\n"); |
79 | + | scanf("%d", &n); |
80 | ||
81 | - | int i; |
81 | + | if (n > 0) { |
82 | - | for (i = 0; i < n; i++) |
82 | + | printf("Ingrese los valores a ordenar:\n"); |
83 | - | scanf("%d", &E[i]); |
83 | + | |
84 | int i; | |
85 | - | if (busca_repetidos(E, n)) { |
85 | + | for (i = 0; i < n; i++) |
86 | - | bit_index_dsc(E, n); |
86 | + | scanf("%d", &E[i]); |
87 | - | imprime_ordenado(E, n); |
87 | + | |
88 | - | } else |
88 | + | if (busca_repetidos(E, n)) { |
89 | - | printf("Hay valores repetidos\n"); |
89 | + | begin = clock(); |
90 | bit_index_dsc(E, n); | |
91 | end = clock(); | |
92 | imprime_ordenado(E, n); | |
93 | } else | |
94 | printf("Hay valores repetidos\n"); | |
95 | } | |
96 | time_spent = (double) (end - begin) / CLOCKS_PER_SEC; | |
97 | printf("%f\n", time_spent * 1000); | |
98 | //} | |
99 | return (EXIT_SUCCESS); | |
100 | } |