View difference between Paste ID: ir0bkAVH and zwCsZL8a
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
}