Cały QuickSort to funkcja tworząca partycje
pisane na szybko
void quickSort(int[] arr, int left, int right) {
if (right - left < 2) {
return;
}
** int pivotIdx = makePartitions(arr, left, right);**
recSort(arr, left, pivotIdx);
recSort(arr, pivotIdx + 1, right);
}
Przed pogrubieniem: tablica pusta lub o rozmiarze jest już posortowana.
Po pogrubieniu:
sortuj 'quick' rekurencyjnie na lewo od pivot liczby <= arr[pivot]
sortuj 'quick' rekurencyjnie na prawo od pivot liczby > arr[pivot]
W części niepogrubionej nie ma co się skopać. Natomiast makePartitions? To mogą być cuda i złożoność też 'cudowna'. BTW, dawniej to się chyba można było obronić z pracy na ten temat ;)
Co robić, co testować?
Można makePartitions zrobić jako funkcję w dowolny sposób, banalny, byle tylko robiła swoje, nie ważne jak.
Wrzucić taką implementację do quickSort.
Napisać testy. Sprawdzić, że działa:
proste makePartitions
quickSort
Przejść teraz do 'refactor' (red & green już mamy) i zająć się samą funkcją makePartitions.
Później przetestować jak nowsza makePartitions działa z quick sort.
Wiem, armata na wróbla, ale takie rozbijanie problemu pozwala się przy okazji nauczyć jak sobie radzić z czymś bardziej skomplikowanym, jak rozbijać problemy na mniejsze.
PS
Dla sportu sprawdziłem sobie, jakbym napisał QuickSort gdybym musiał 'z palca' napisać.
I jaki sobie sposób partycjonowania wymyślę bez sięgania do Wiki.
Prosta Java, w C nie pisze - sorry, ale chyba da się zrozumieć działanie
void recQuickSort(Integer[] arr, int left, int right) {}
z punktu widzenia kodującego w C
package pl.bv.p58;
public abstract class QuickSort {
private QuickSort(Integer[] arr) {
recQuickSort(arr, 0, arr.length);
}
public static void sort(Integer[] arr) {
recQuickSort(arr, 0, arr.length);
}
private static void recQuickSort(Integer[] arr, int left, int right) {
if (right - left < 2) {
return;
}
final int pivot = makePartitions(arr, left, right);
recQuickSort(arr, left, pivot);
recQuickSort(arr, pivot + 1, right);
}
private static int makePartitions(Integer[] arr, int left, int right) {
int slider = left;
for (int i = slider + 1; i < right; i++) {
if (arr[i] <= arr[left]) {
slider++;
swap(arr, slider, i);
}
}
swap(arr, slider, left);
return slider;
}
private static void swap(Integer[] arr, int slider, int i) {
int temp = arr[i];
arr[i] = arr[slider];
arr[slider] = temp;
}
}
szybki test (dla porządku, bo wiem, że piszący w C niewiele z tym zrobi)
package pl.bv.p58;
import org.junit.Before;
import org.junit.Test;
import java.util.Arrays;
import static org.junit.Assert.*;
import static org.hamcrest.Matchers.*;
public class QuickSortTest {
private Integer[] integers;
private Integer[] sorted;
@Before
public void setUp() throws Exception {
integers = new Integer[]{7, 1, 2, 4, 5, 2, 3, 4, 5, 79, 3, -3, 5, 0, 12, 1, 2, 56, 56, 34, 56};
sorted = new Integer[integers.length];
System.arraycopy(integers, 0, sorted, 0, integers.length);
Arrays.sort(sorted);
}
@Test
public void shoulSortEpmtyArray() {
final Integer[] arr = new Integer[0];
QuickSort.sort(arr);
assertThat(arr.length, is(0));
}
@Test
public void shoulSortOneElementArray() {
final Integer[] arr = new Integer[]{7};
QuickSort.sort(arr);
assertThat(arr.length, is(1));
assertThat(arr, arrayContaining(7));
}
@Test
public void shouldSortUnsortedArray() {
QuickSort.sort(integers);
assertThat(integers, arrayContaining(sorted));
}
@Test
public void shouldSortSortedArray() {
Arrays.sort(integers);
QuickSort.sort(integers);
assertThat(integers, arrayContaining(sorted));
}
@Test
public void shouldSortSameElementsArray() {
integers = new Integer[]{7, 7, 7, 7, 7, 7, 7, 7, 7};
sorted = new Integer[]{7, 7, 7, 7, 7, 7, 7, 7, 7};
QuickSort.sort(integers);
assertThat(integers, arrayContaining(sorted));
}
}