Skip to content

Commit cce4377

Browse files
patrickyevsukovpatrickyevsukov
committed
Add Unit Test
Refactor Sort Algorithm To Easily Work With Unit Test
1 parent 03184be commit cce4377

2 files changed

Lines changed: 134 additions & 49 deletions

File tree

‎Radix_Sort/Java/PatrickYevsukov/radix_sort.java‎

Lines changed: 57 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,76 +1,84 @@
1-
// Patrick Yevsukov
2-
3-
// 2013 CC BY-NC-SA 4.0 http://patrick.yevsukov.com
4-
1+
// Patrick Yevsukov
2+
3+
// 2013 CC BY-NC-SA 4.0 http://patrick.yevsukov.com
4+
55
// github.com/PatrickYevsukov/Sorting-Algorithms
6-
7-
public static void RadixSort(ArrayList<Integer> list) {
86

9-
final int NUM_BASE = 10;
7+
package PatrickYevsukov;
108

11-
int maximum = 0;
9+
import java.util.ArrayList;
1210

13-
ArrayList<ArrayList<Integer>> buckets;
11+
public class radix_sort {
1412

15-
buckets = new ArrayList<ArrayList<Integer>>(NUM_BASE);
13+
public static void RadixSort(ArrayList<Integer> list) {
1614

17-
// New buckets are added to the bucket list; one for each digit
18-
// in the numeral system of the data being sorted.
19-
20-
for (int ii = 0; ii < NUM_BASE; ii++) {
15+
final int NUM_BASE = 10;
2116

22-
buckets.add(new ArrayList<Integer>());
23-
}
17+
int maximum = 0;
2418

25-
// Identifying the list item with the most place values.
26-
27-
for (int ii = 0; ii < list.size(); ii++) {
19+
ArrayList<ArrayList<Integer>> buckets;
2820

29-
if (list.get(ii) > maximum) {
21+
buckets = new ArrayList<ArrayList<Integer>>(NUM_BASE);
3022

31-
maximum = list.get(ii);
23+
// New buckets are added to the bucket list; one for each digit
24+
// in the numeral system of the data being sorted.
25+
26+
for (int ii = 0; ii < NUM_BASE; ii++) {
27+
28+
buckets.add(new ArrayList<Integer>());
3229
}
33-
}
3430

35-
// List items are sorted by place value. The place value is
36-
// multiplied by the numeric base with each pass of the loop.
37-
38-
for (int power = 1; maximum / power != 0; power *= NUM_BASE) {
31+
// Identifying the list item with the most place values.
3932

4033
for (int ii = 0; ii < list.size(); ii++) {
4134

42-
// List items are added to the bucket which corresponds
43-
// to the place value which they are being sorted by.
44-
45-
buckets.get(list.get(ii) / power % NUM_BASE)
46-
.add(list.get(ii));
35+
if (list.get(ii) > maximum) {
36+
37+
maximum = list.get(ii);
38+
}
4739
}
4840

49-
int index = 0;
41+
// List items are sorted by place value. The place value is
42+
// multiplied by the numeric base with each pass of the loop.
43+
44+
for (int power = 1; maximum / power != 0; power *= NUM_BASE) {
5045

51-
for (int ii = 0; ii < buckets.size(); ii++) {
46+
for (int ii = 0; ii < list.size(); ii++) {
5247

53-
for (int jj = 0; jj < buckets.get(ii).size(); jj++) {
48+
// List items are added to the bucket which corresponds
49+
// to the place value which they are being sorted by.
5450

55-
// The buckets, sorted by the current place value
56-
// under consideration, have their values written
57-
// back to original list, overwriting its previous
58-
// contents.
59-
60-
list.set(index, buckets.get(ii).get(jj));
61-
index++;
51+
buckets.get(list.get(ii) / power % NUM_BASE).add(list.get(ii));
52+
}
53+
54+
int index = 0;
55+
56+
for (int ii = 0; ii < buckets.size(); ii++) {
57+
58+
for (int jj = 0; jj < buckets.get(ii).size(); jj++) {
59+
60+
// The buckets, sorted by the current place value
61+
// under consideration, have their values written
62+
// back to original list, overwriting its previous
63+
// contents.
64+
65+
list.set(index, buckets.get(ii).get(jj));
66+
67+
index++;
68+
}
6269
}
63-
}
6470

65-
// At the end of each pass of the loop, the contents of the
66-
// buckets are dumped out.
67-
68-
for (int ii = 0; ii < buckets.size(); ii++) {
71+
// At the end of each pass of the loop, the contents of the
72+
// buckets are dumped out.
6973

70-
buckets.get(ii).clear();
74+
for (int ii = 0; ii < buckets.size(); ii++) {
75+
76+
buckets.get(ii).clear();
77+
}
7178
}
7279
}
73-
}
74-
80+
7581
// Above is my implementation of a radix sort. I
7682
// wrote it to be as human readable as possible.
83+
84+
}

‎Radix_Sort/Java/PatrickYevsukov/radix_sort_test.java‎

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
// Patrick Yevsukov
2+
3+
// 2013 CC BY-NC-SA 4.0 http://patrick.yevsukov.com
4+
5+
// github.com/PatrickYevsukov/Sorting-Algorithms
6+
7+
package PatrickYevsukov;
8+
9+
import java.util.Random;
10+
11+
import java.util.ArrayList;
12+
13+
public class radix_sort_test {
14+
15+
private static Random random;
16+
17+
private static final int COLUMNS = 9;
18+
19+
private static final int VAL_COUNT = 10;
20+
21+
private static final int TRUNCATE = 10000000;
22+
23+
private static ArrayList<Integer> randomDataList;
24+
25+
public static void main(String[] args) {
26+
27+
TestRadixSort();
28+
}
29+
30+
public static void TestRadixSort() {
31+
32+
random = new Random();
33+
34+
randomDataList = GenRandomArrayList();
35+
36+
37+
System.out.print("Unsorted List:\t");
38+
39+
PrintArrayList(randomDataList);
40+
41+
42+
radix_sort.RadixSort(randomDataList);
43+
44+
45+
System.out.print("Sorted List:\t");
46+
47+
PrintArrayList(randomDataList);
48+
49+
}
50+
51+
public static ArrayList<Integer> GenRandomArrayList() {
52+
53+
ArrayList<Integer> ints = new ArrayList<Integer>(VAL_COUNT);
54+
55+
for (int ii = 0; ii < VAL_COUNT; ii++) {
56+
57+
ints.add(Math.abs(random.nextInt() / TRUNCATE));
58+
}
59+
60+
return ints;
61+
}
62+
63+
public static <T> void PrintArrayList(final ArrayList<T> ints) {
64+
65+
for (int ii = 0; ii < ints.size(); ii++) {
66+
67+
System.out.print(ints.get(ii) + "\t");
68+
69+
if ((ii % (COLUMNS + 1)) == COLUMNS) {
70+
71+
System.out.println();
72+
}
73+
}
74+
75+
System.out.println();
76+
}
77+
}

0 commit comments

Comments
 (0)