-
Notifications
You must be signed in to change notification settings - Fork 0
/
bucket_sort.c
135 lines (115 loc) · 2.75 KB
/
bucket_sort.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
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <stdlib.h>
#include "list.h"
#include "bucket_sort.h"
static void merge(List *lst, List *lst1, int (*compare)(const void *data1, const void *data2));
int bucket_init(Bucket *buk,
void (*destroy)(void *data),
int (*compare)(const void *data1, const void *data2),
int (*hash)(const void *key),
unsigned int size){
if(buk == NULL || compare == NULL || hash == NULL || size < 1 ){
return -1;
}
if((buk->buckets = (List **)malloc(sizeof(List *) * size)) == NULL){
return -1;
}
for(int i=0; i<size; i++){
buk->buckets[i] = NULL;
}
buk->destroy = destroy;
buk->compare = compare;
buk->hash = hash;
buk->size = size;
}
void bucket_destroy(Bucket *buk){
for(int i=0; i<buk->size; i++){
if(buk->buckets[i] != NULL){
list_destroy(buk->buckets[i]);
/* free the list */
free(buk->buckets[i]);
}
}
memset(buk, 0, sizeof(*buk));
}
int bucket_insert(Bucket *buk, const void *data){
if(buk == NULL || data == NULL){
return -1;
}
int index = buk->hash(data) % buk->size;
if(buk->buckets[index] == NULL){
if((buk->buckets[index] = (List *)malloc(sizeof(List))) == NULL){
return -1;
}
list_init(buk->buckets[index], buk->destroy, buk->compare);
}
Node *pNode = list_head(buk->buckets[index]);
if(pNode == NULL){
list_push(buk->buckets[index], data);
}
else{
while(pNode){
if(buk->compare(data, list_node_data(pNode)) < 0){
list_insert(buk->buckets[index], pNode, data);
return 0;
}
pNode = list_node_next(pNode);
}
list_push(buk->buckets[index], data);
}
return 0;
}
int bucket_sort(Bucket *buk, List *lst){
if(buk == NULL || lst == NULL){
return -1;
}
for(int i=0; i<buk->size; i++){
if(buk->buckets[i] != NULL){
merge(lst, buk->buckets[i], buk->compare);
}
}
return 0;
}
/*
* Internal Functions
*/
void merge(List *lst, List *lst1, int (*compare)(const void *data1, const void *data2)){
Node *pNode=NULL, *pNode1=NULL;
pNode = list_head(lst);
pNode1 = list_head(lst1);
List temp;
list_init(&temp, NULL, NULL);
while(pNode != NULL && pNode1 != NULL) {
int cmpval = compare(list_node_data(pNode), list_node_data(pNode1));
if(cmpval < 0){
list_push(&temp, list_node_data(pNode));
pNode = list_node_next(pNode);
}
else{
list_push(&temp, list_node_data(pNode1));
pNode1 = list_node_next(pNode1);
}
}
if(pNode != NULL){
while(pNode){
list_push(&temp, list_node_data(pNode));
pNode = list_node_next(pNode);
}
}
if(pNode1 != NULL){
while(pNode1){
list_push(&temp, list_node_data(pNode1));
pNode1 = list_node_next(pNode1);
}
}
void *data = NULL;
while(list_pop(lst, &data) == 0){
/* nothing */
}
pNode = list_head(&temp);
while(pNode){
list_push(lst, list_node_data(pNode));
pNode = list_node_next(pNode);
}
list_destroy(&temp);
return 0;
}