wheysort

package sorting.divideAndConquer.threeWayQuicksort;

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

import sorting.AbstractSorting;
import util.Util;

public class ThreeWayQuickSort<T extends Comparable<T>> extends
        AbstractSorting<T> {

    /**
     * No algoritmo de quicksort, selecionamos um elemento como pivot,
     * particionamos o array colocando os menores a esquerda do pivot
     * e os maiores a direita do pivot, e depois aplicamos a mesma estrategia
     * recursivamente na particao a esquerda do pivot e na particao a direita do pivot.
     *
     * Considerando um array com muitoe elementos repetidos, a estrategia do quicksort
     * pode ser otimizada para lidar de forma mais eficiente com isso. Essa melhoria
     * eh conhecida como quicksort tree way e consiste da seguinte ideia:
     * - selecione o pivot e particione o array de forma que
     *   * arr[l..i] contem elementos menores que o pivot
     *   * arr[i+1..j-1] contem elementos iguais ao pivot.
     *   * arr[j..r] contem elementos maiores do que o pivot.
     *
     * Obviamente, ao final do particionamento, existe necessidade apenas de ordenar
     * as particoes contendo elementos menores e maiores do que o pivot. Isso eh feito
     * recursivamente.
     **/
    public void shuffle(T[] array, int leftIndex, int rightIndex){
        Random rnd = ThreadLocalRandom.current();
        for (int i = rightIndex; i >= leftIndex; i--){
          int index = rnd.nextInt(i + 1);
          T valor = array[index];
          array[index] = array[i];
          array[i] = valor;
        }
     }

    public void waysort(T[]array, int leftIndex, int rightIndex) {
        if(leftIndex < rightIndex) {
            T pivot = array[leftIndex];

            int low = leftIndex, high = rightIndex;

            int i = leftIndex;
            while(i <= high) {
                int comp = array[i].compareTo(pivot);
                if(comp < 0) Util.swap(array, low++, i++);
                else if(comp > 0) Util.swap(array,  i, high--);
                else i++;
            }

            sort(array, leftIndex, low-1);
            sort(array, high+1, rightIndex);
        }
    }

    @Override
    public void sort(T[]array, int leftIndex, int rightIndex) {
        if(leftIndex < rightIndex && leftIndex >= 0 && rightIndex >= 0) {
            shuffle(array, leftIndex, rightIndex);
            waysort(array, leftIndex, rightIndex);
        }
    }

}