public class Sort implements SortInterface {
    @Override
    public void sort(SwapStoreInterface ss) {
        for (int line = 0; line < ss.length(); line++) {
            quicksort(ss, line, 0, ss.lineLength(line)-1);
        }
    }
    private void quicksort(SwapStoreInterface ss, int line, int i, int k) {
        if (i < k) {
            int p = partition(ss, line, i, k);
            quicksort(ss, line, i, p-1);
            quicksort(ss, line, p+1, k);
        }
    }
    private int partition(SwapStoreInterface ss, int line, int left, int right) {
        //pivotIndex defaults to right; O(n^2) for already sorted arrays
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (ss.compare(line, i, right) < 0) {
                ss.swap(line, i, storeIndex);
                storeIndex++;
            }
        }
        ss.swap(line, storeIndex, right);
        return storeIndex;
    }
}