qsort

package sorting.divideAndConquer;


import java.util.Collections;
import java.util.Random;
import java.util.concurrent.ThreadLocalRandom;

import sorting.AbstractSorting;
import util.*;
/**
 * Quicksort is based on the divide-and-conquer paradigm. The algorithm chooses
 * a pivot element and rearranges the elements of the interval in such a way
 * that all elements lesser than the pivot go to the left part of the array and
 * all elements greater than the pivot, go to the right part of the array. Then
 * it recursively sorts the left and the right parts. Notice that if the list
 * has length == 1, it is already sorted.
 */
public class QuickSort<T extends Comparable<T>> extends AbstractSorting<T> {


    public void shuffle(T[] array){
        Random rnd = ThreadLocalRandom.current();
        for (int i = array.length - 1; i > 0; i--){
          int index = rnd.nextInt(i + 1);
          T valor = array[index];
          array[index] = array[i];
          array[i] = valor;
        }
     }

    public void qsort(T[] array, int leftIndex, int rightIndex) {
        if(leftIndex < rightIndex && leftIndex >= 0 && rightIndex < array.length) {
            T pivot = array[rightIndex];
            int divisor = leftIndex-1;
            for(int j = leftIndex; j <= rightIndex-1; j++) {
                if(array[j].compareTo(pivot) <= 0) {
                    Util.swap(array, ++divisor, j);
                }
            }
            Util.swap(array, ++divisor, rightIndex);
            qsort(array, leftIndex, divisor-1);
            qsort(array, divisor+1, rightIndex);
        }
    }

    @Override
    public void sort(T[] array, int leftIndex, int rightIndex) {
        shuffle(array);
        qsort(array, leftIndex, rightIndex);
    }

}