Skip to content

Commit 3eff872

Browse files
varunu28varunu28
authored
Merge pull request TheAlgorithms#490 from lq920320/Development
add some tests for Sort
2 parents 90a4c36 + 89f1c37 commit 3eff872

11 files changed

Lines changed: 452 additions & 0 deletions

‎src/main/com/java/sorts/BubbleSort.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package src.main.com.java.sorts;
2+
3+
import static src.main.com.java.sorts.SortUtils.less;
4+
import static src.main.com.java.sorts.SortUtils.swap;
5+
6+
public class BubbleSort {
7+
/**
8+
* This method implements the Generic Bubble Sort
9+
*
10+
* @param array The array to be sorted
11+
* Sorts the array in increasing order
12+
**/
13+
public <T extends Comparable<T>> T[] sort(T[] array) {
14+
int last = array.length;
15+
//Sorting
16+
boolean swap;
17+
do {
18+
swap = false;
19+
for (int count = 0; count < last - 1; count++) {
20+
if (less(array[count + 1], array[count])) {
21+
swap = swap(array, count, count + 1);
22+
}
23+
}
24+
last--;
25+
} while (swap);
26+
return array;
27+
}
28+
}

‎src/main/com/java/sorts/HeapSort.java‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
package src.main.com.java.sorts;
2+
3+
import java.util.ArrayList;
4+
import java.util.Arrays;
5+
import java.util.List;
6+
7+
import static src.main.com.java.sorts.SortUtils.less;
8+
import static src.main.com.java.sorts.SortUtils.swap;
9+
10+
public class HeapSort {
11+
12+
13+
private static class Heap<T extends Comparable<T>> {
14+
/**
15+
* Array to store heap
16+
*/
17+
private T[] heap;
18+
19+
/**
20+
* Constructor
21+
*
22+
* @param heap array of unordered integers
23+
*/
24+
Heap(T[] heap) {
25+
this.heap = heap;
26+
}
27+
28+
/**
29+
* Heapifies subtree from top as root to last as last child
30+
*
31+
* @param rootIndex index of root
32+
* @param lastChild index of last child
33+
*/
34+
private void heapSubtree(int rootIndex, int lastChild) {
35+
int leftIndex = rootIndex * 2 + 1;
36+
int rightIndex = rootIndex * 2 + 2;
37+
T root = heap[rootIndex];
38+
if (rightIndex <= lastChild) {
39+
// if has right and left children
40+
T left = heap[leftIndex];
41+
T right = heap[rightIndex];
42+
if (less(left, right) && less(left, root)) {
43+
swap(heap, leftIndex, rootIndex);
44+
heapSubtree(leftIndex, lastChild);
45+
} else if (less(right, root)) {
46+
swap(heap, rightIndex, rootIndex);
47+
heapSubtree(rightIndex, lastChild);
48+
}
49+
} else if (leftIndex <= lastChild) {
50+
// if no right child, but has left child
51+
T left = heap[leftIndex];
52+
if (less(left, root)) {
53+
swap(heap, leftIndex, rootIndex);
54+
heapSubtree(leftIndex, lastChild);
55+
}
56+
}
57+
}
58+
59+
60+
/**
61+
* Makes heap with root as root
62+
*
63+
* @param root index of root of heap
64+
*/
65+
private void makeMinHeap(int root) {
66+
int leftIndex = root * 2 + 1;
67+
int rightIndex = root * 2 + 2;
68+
boolean hasLeftChild = leftIndex < heap.length;
69+
boolean hasRightChild = rightIndex < heap.length;
70+
if (hasRightChild) {
71+
//if has left and right
72+
makeMinHeap(leftIndex);
73+
makeMinHeap(rightIndex);
74+
heapSubtree(root, heap.length - 1);
75+
} else if (hasLeftChild) {
76+
heapSubtree(root, heap.length - 1);
77+
}
78+
}
79+
80+
/**
81+
* Gets the root of heap
82+
*
83+
* @return root of heap
84+
*/
85+
private T getRoot(int size) {
86+
swap(heap, 0, size);
87+
heapSubtree(0, size - 1);
88+
// return old root
89+
return heap[size];
90+
}
91+
92+
93+
}
94+
95+
public <T extends Comparable<T>> T[] sort(T[] unsorted) {
96+
return sort(Arrays.asList(unsorted)).toArray(unsorted);
97+
}
98+
99+
private <T extends Comparable<T>> List<T> sort(List<T> unsorted) {
100+
int size = unsorted.size();
101+
102+
@SuppressWarnings("unchecked")
103+
Heap<T> heap = new Heap<>(unsorted.toArray((T[]) new Comparable[unsorted.size()]));
104+
105+
// make min heap using index 0 as root.
106+
heap.makeMinHeap(0);
107+
List<T> sorted = new ArrayList<>(size);
108+
while (size > 0) {
109+
T min = heap.getRoot(--size);
110+
sorted.add(min);
111+
}
112+
113+
return sorted;
114+
}
115+
}

‎src/main/com/java/sorts/QuickSort.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
package src.main.com.java.sorts;
2+
3+
import static src.main.com.java.sorts.SortUtils.less;
4+
import static src.main.com.java.sorts.SortUtils.swap;
5+
6+
public class QuickSort {
7+
8+
9+
/**
10+
* This method implements the Generic Quick Sort
11+
*
12+
* @param array The array to be sorted
13+
* Sorts the array in increasing order
14+
**/
15+
public <T extends Comparable<T>> T[] sort(T[] array) {
16+
doSort(array, 0, array.length - 1);
17+
return array;
18+
}
19+
20+
21+
/**
22+
* The sorting process
23+
*
24+
* @param left The first index of an array
25+
* @param right The last index of an array
26+
* @param array The array to be sorted
27+
**/
28+
29+
private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
30+
if (left < right) {
31+
int pivot = partition(array, left, right);
32+
doSort(array, left, pivot - 1);
33+
doSort(array, pivot, right);
34+
}
35+
}
36+
37+
/**
38+
* This method finds the partition index for an array
39+
*
40+
* @param array The array to be sorted
41+
* @param left The first index of an array
42+
* @param right The last index of an array
43+
* Finds the partition index of an array
44+
**/
45+
46+
private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
47+
int mid = (left + right) / 2;
48+
T pivot = array[mid];
49+
50+
while (left <= right) {
51+
while (less(array[left], pivot)) {
52+
++left;
53+
}
54+
while (less(pivot, array[right])) {
55+
--right;
56+
}
57+
if (left <= right) {
58+
swap(array, left, right);
59+
++left;
60+
--right;
61+
}
62+
}
63+
return left;
64+
}
65+
}

‎src/main/com/java/sorts/SelectionSort.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package src.main.com.java.sorts;
2+
3+
import static src.main.com.java.sorts.SortUtils.less;
4+
import static src.main.com.java.sorts.SortUtils.swap;
5+
6+
public class SelectionSort {
7+
8+
/**
9+
* This method implements the Generic Selection Sort
10+
*
11+
* @param arr The array to be sorted
12+
* Sorts the array in increasing order
13+
**/
14+
public <T extends Comparable<T>> T[] sort(T[] arr) {
15+
int n = arr.length;
16+
for (int i = 0; i < n - 1; i++) {
17+
// Initial index of min
18+
int min = i;
19+
for (int j = i + 1; j < n; j++) {
20+
if (less(arr[j], arr[min])) {
21+
min = j;
22+
}
23+
}
24+
// Swapping if index of min is changed
25+
if (min != i) {
26+
swap(arr, i, min);
27+
}
28+
}
29+
30+
return arr;
31+
}
32+
}

‎src/main/com/java/sorts/ShellSort.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package src.main.com.java.sorts;
2+
3+
import static src.main.com.java.sorts.SortUtils.less;
4+
import static src.main.com.java.sorts.SortUtils.swap;
5+
6+
public class ShellSort {
7+
8+
/**
9+
* This method implements Generic Shell Sort.
10+
*
11+
* @param array The array to be sorted
12+
*/
13+
public <T extends Comparable<T>> T[] sort(T[] array) {
14+
int length = array.length;
15+
int n = 1;
16+
17+
while (n < length / 3) {
18+
n = 3 * n + 1;
19+
}
20+
21+
while (n >= 1) {
22+
for (int i = n; i < length; i++) {
23+
for (int j = i; j >= n && less(array[j], array[j - n]); j -= n) {
24+
swap(array, j, j - n);
25+
}
26+
}
27+
n /= 3;
28+
}
29+
30+
return array;
31+
}
32+
}

‎src/main/com/java/sorts/SortUtils.java‎

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package src.main.com.java.sorts;
2+
3+
final class SortUtils {
4+
5+
6+
/**
7+
* Helper method for swapping places in array
8+
*
9+
* @param array The array which elements we want to swap
10+
* @param idx index of the first element
11+
* @param idy index of the second element
12+
*/
13+
static <T> boolean swap(T[] array, int idx, int idy) {
14+
T swap = array[idx];
15+
array[idx] = array[idy];
16+
array[idy] = swap;
17+
return true;
18+
}
19+
20+
21+
/**
22+
* This method checks if first element is less then the other element
23+
*
24+
* @param v first element
25+
* @param w second element
26+
* @return true if the first element is less then the second element
27+
*/
28+
static <T extends Comparable<T>> boolean less(T v, T w) {
29+
return v.compareTo(w) < 0;
30+
}
31+
32+
33+
/**
34+
* Swaps all position from {@param left} to @{@param right} for {@param array}
35+
*
36+
* @param array is an array
37+
* @param left is a left flip border of the array
38+
* @param right is a right flip border of the array
39+
*/
40+
static <T extends Comparable<T>> void flip(T[] array, int left, int right) {
41+
while (left <= right) {
42+
swap(array, left++, right--);
43+
}
44+
}
45+
}

‎src/test/com/java/sorts/BubbleSortTest.java‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package src.test.com.java.sorts;
2+
3+
4+
import org.junit.Assert;
5+
import org.junit.Test;
6+
import src.main.com.java.sorts.BubbleSort;
7+
8+
import java.util.Arrays;
9+
10+
public class BubbleSortTest {
11+
12+
@Test
13+
public void bubbleSortTest() {
14+
BubbleSort bubbleSort = new BubbleSort();
15+
Integer[] unsortedInt = new Integer[]{0, 5, 9, 2, 1, 3, 4, 8, 6, 7};
16+
Integer[] sortedInt = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
17+
System.out.println(Arrays.toString(bubbleSort.sort(unsortedInt)));
18+
19+
Assert.assertArrayEquals(sortedInt, bubbleSort.sort(unsortedInt));
20+
21+
Character[] unsortedChar = new Character[]{'f', 'h', 'c', 'a', 'b', 'd', 'g', 'e'};
22+
Character[] sortedChar = new Character[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
23+
System.out.println(Arrays.toString(bubbleSort.sort(unsortedChar)));
24+
25+
Assert.assertArrayEquals(sortedChar, bubbleSort.sort(unsortedChar));
26+
27+
}
28+
29+
}

‎src/test/com/java/sorts/HeapSortTest.java‎

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package src.test.com.java.sorts;
2+
3+
4+
import org.junit.Assert;
5+
import org.junit.Test;
6+
import src.main.com.java.sorts.HeapSort;
7+
8+
import java.util.Arrays;
9+
10+
public class HeapSortTest {
11+
12+
@Test
13+
public void heapSortTest() {
14+
HeapSort heapSort = new HeapSort();
15+
Integer[] unsortedInt = new Integer[]{0, 5, 9, 2, 1, 3, 4, 8, 6, 7};
16+
Integer[] sortedInt = new Integer[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
17+
System.out.println(Arrays.toString(heapSort.sort(unsortedInt)));
18+
19+
Assert.assertArrayEquals(sortedInt, heapSort.sort(unsortedInt));
20+
21+
Character[] unsortedChar = new Character[]{'f', 'h', 'c', 'a', 'b', 'd', 'g', 'e'};
22+
Character[] sortedChar = new Character[]{'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'};
23+
System.out.println(Arrays.toString(heapSort.sort(unsortedChar)));
24+
25+
Assert.assertArrayEquals(sortedChar, heapSort.sort(unsortedChar));
26+
}
27+
}

0 commit comments

Comments
 (0)