public class QuickSort {
    private int[] arr;

    public QuickSort(int[] arr) {
        this.arr = arr;
    }

    public int[] sort() {
        quickSort(0, arr.length - 1);

        return arr;
    }

    private void quickSort(int start, int end) {
        if (start < end) {
            int pIndex = partition(start, end);

            quickSort(start, pIndex - 1);
            quickSort(pIndex + 1, end);
        }
    }

    private int partition(int start, int end) {
        int pivot = arr[end];
        int pIndex = start;

        for (int i = start; i < end; i++) {
            if (arr[i] <= pivot) {
                swap(i, pIndex);
                pIndex++;
            }
        }

        swap(pIndex, end);

        return pIndex;
    }

    private void swap(int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}