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
|
// you have to write this function - I put pseudo code in to help you ********************************
int radixSort(int *dta, int n, int *out)
{
// the dta array contains the data to be sorted.
// n is the number of data items in the array
// out is the array to put the sorted data
node *bucket[1000]; // declare an array of 1000 linked lists (head pointers)
int count = 0; // you will use this to count the instructions to graph the big-o
for(int i = 0; i < n; i++)out[i] = dta[i]; // first copy dta into out for use by the shell. Use out from now on in this function
// *********************8 psuedo code follows: **********************
// for (pass = 0, 1, 2) // this is the outer loop
// {
for (int p = 0; p < 3; p++) {
// for(j) 0 -> < 1000, set bucket[] to all zeroes (NULL) for each pass// note we are not deleting the old nodes, this is not good programming because we create a memory leak
// if you want to delete the old nodes, go ahead, but it is not necessary for your grade in this lab. The leaked memory goes away once the program ends.
for (int j = 0; j < 1000; j++) {
bucket[j] = NULL;
}
for (int i = 0; i < n; i++) {
// for(i 0, < n) // inner loop - walk through the out array (which contains the data to be sorted
// {
int index = -1;
int zzz, yyy, xxx;
switch (p) {
case 0:
zzz = out[i] % 1000;
index = zzz; // last three digits
break;
case 1:
yyy = out[i] % 1000000;
yyy = yyy / 1000;
index = yyy; //middle 3 digits
break;
case 2:
xxx = out[i] % 1000000000;
xxx = xxx / 1000000;
index = xxx; //first 3 digits
break;
};
// int index; // where in the bucket do we want to store this data
// switch(pass) // refer to the Powerpoint to see how to parse the digits
// {// refer to the Powerpoint to see how to parse the digits
// case 0:
// set index to the last 3 digits
// break;
// case 1;
// set index to the middle 3 digits
// break;
// case 2:
// set index to the first 3 digits
// break;
// };
if (bucket[index] == NULL) {
bucket[index] = new node(out[i], NULL);
}
else {
bucket[index + 1] = new node(out[i], bucket[index]);
}
// if(bucket[index] == NULL)
// { // nothing is stored here so
// bucket[index] = new node(out[i], NULL); // create a new head node and store this data
// }
// else
// {
// something is already here so make a new node, store the out[i] in the new node
// walk the linked list from the head (bucket[index] to find the last node (tail).
// make tail point to the new node you just created.
// }
// } // end of the inner (i) loop
}
int idx = 0;
for (int i = 0; i < 1000; i++) {
if (bucket[i] == NULL) {
continue;
}
else {
out[idx++] = bucket[i]->data;
}
}
// int idx = 0; // you need this to load the out array
// for(i) 0 -> < 1000 // walk through the bucket
// {
// if(bucket[i] == NULL)continue; nothing was stored here so skip to the next item
// something is stored here, so put it into the out array starting at the beginning (idx)
//out[idx++] = bucket[i]->data[i];
// now see if there are more nodes in the linked list that starts at bucket[i]. If there are, put their data into out[idx++]
// }
// at this point, idx must equal n (use this as a check)
}
// }// end of the outer loop pass). The output (out) from this pass becomes the input for the next pass
return count;
}
// ***********end of function you have to write ******************************************************************************************////
| |
