QuickSort(Java)
実装コード:
テストコード:
public class QuickSort {
public void sort(int[] input) {
quickSort(input, 0, input.length - 1);
}
private void quickSort(int[] input, int begin, int end) {
if (begin >= end) return;
int mid = partition(input, begin, end);
quickSort(input, begin, mid-1);
quickSort(input, mid+1, end);
}
private int partition(int[] input, int begin, int end) {
int x = input[begin];
int smallIndex = begin, bigIndex = begin;
while(++bigIndex <= end) {
if (input[bigIndex] >= x) continue;
else {
smallIndex++;
swap(input, smallIndex, bigIndex);
}
}
swap(input, begin, smallIndex);
return smallIndex;
}
private void swap(int[] input, int lhs, int rhs) {
int temp = input[lhs];
input[lhs] = input[rhs];
input[rhs] = temp;
}
}
テストコード:
import org.junit.*;
import static org.junit.Assert.assertArrayEquals;
public class QuickSortTest {
private QuickSort quickSort;
@Before
public void setUp() {
quickSort = new QuickSort();
}
@Test
public void should_return_1_for_quick_sort_1() {
int[] input = {1};
int[] expect = {1};
quickSort.sort(input);
assertArrayEquals(expect, input);
}
@Test
public void should_return_12_for_quick_sort_21() {
int[] input = {2, 1};
int[] expect = {1, 2};
quickSort.sort(input);
assertArrayEquals(expect, input);
}
@Test
public void should_return_1234_for_quick_sort_3124() {
int[] input = {3, 1, 2, 4};
int[] expect = {1, 2, 3, 4};
quickSort.sort(input);
assertArrayEquals(expect, input);
}
@Test
public void should_return_12345678_for_quick_sort_46835217() {
int[] input = {4, 6, 8, 3, 5, 2, 1, 7};
int[] expect = {1, 2, 3, 4, 5, 6, 7, 8};
quickSort.sort(input);
assertArrayEquals(expect, input);
}
}