Quick Sorting

Sort.java

package web.cheff;

import java.util.Random;

/**
 * Created by yura on 30.03.16.
 */
public class Sort {
    private int[] sorted;
    private int found;

    public Sort(int[] values, int start, int end) {
        this.sorted = values;
        randomizedQuickSort(start, end);
    }
    public Sort(int[] values, int start, int end, int i) {
        this.sorted = values;
        this.found = randomizedSelect(start,end,i);
    }
    private void quickSort(int p, int r) {
        if (p < r) {
            int q = partition(p, r);
            quickSort(p, q - 1);
            quickSort(q + 1, r);
        }
    }

    private void randomizedQuickSort(int p, int r){
        if(p<r){
            int q = randomizedPartition(p,r);
            randomizedQuickSort(p,q-1);
            randomizedQuickSort(q+1,r);
        }
    }

    private int partition(int p, int r) {
        int x = this.sorted[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if (this.sorted[j] <= x) {
                i++;
                substitute(i, j);
            }
        }
        substitute(i + 1, r);
        return i + 1;
    }

    private int randomizedPartition(int p, int r){
        Random rand = new Random();
        int i = rand.nextInt(r-p+1)+p;
        substitute(r,i);
        return partition(p,r);
    }

    private void substitute(int index1, int index2) {
        int temp = this.sorted[index1];
        this.sorted[index1] = this.sorted[index2];
        this.sorted[index2] = temp;
    }
    private int randomizedSelect(int p, int r, int i){
        if(p==r){
            return this.sorted[p];
        }
        int q = randomizedPartition(p,r);
        int k = q - p + 1;
        if(i==k){
            return this.sorted[q];
        } else if(i<k){
            return randomizedSelect(p,q-1,i);
        }
        return randomizedSelect(q+1,r,i-k);
    }
    public int[] getSorted(){
        return this.sorted;
    }
    public int getValue(){
        return this.found;
    }
}