COUNTINGSORT

package sorting.linearSorting;

import java.util.Arrays;

import sorting.AbstractSorting;

/**
 * Classe que implementa a estratégia de Counting Sort vista em sala. Procure
 * evitar desperdicio de memoria alocando o array de contadores com o tamanho
 * sendo o máximo inteiro presente no array a ser ordenado.
 *
 */
public class CountingSort extends AbstractSorting<Integer> {

    @Override
    public void sort(Integer[] array, int leftIndex, int rightIndex) {

        Integer maior = achaMaior(array,leftIndex,rightIndex);

        Integer[] aux = new Integer[maior];
        Integer[] resp = new Integer[array.length];

        preencherZero(aux);

        for (int i = leftIndex; i < rightIndex; i++) {
            Integer num = array[i];
            aux[num - 1]++;
        }
        Arrays.toString(aux);

        for (int i = leftIndex + 1; i < rightIndex; i++) {
            aux[i] += aux[i - 1];
        }

        for (int i = rightIndex - 1; i >= leftIndex; i--) {
            Integer num = aux[array[i]] - 1;
            resp[num] = array[i];
        }
    }

    private void preencherZero(Integer[] aux) {
        for (int i = 0; i < aux.length; i++) {
            aux[i] = 0;
        }

    }

    private Integer achaMaior(Integer[] array, int leftIndex, int rightIndex) {
        Integer maior = array[0];

        for(int i = leftIndex; i < rightIndex ; i++){
            if(array[i] > maior){
                maior = array[i];
            }
        }
        return maior;
    }

    public static void main (String[] args){

        Integer[] a = {3,1,4,1};

        CountingSort cs = new CountingSort();

        cs.sort(a, 0, a.length);

        Arrays.toString(a);

    }
}