Comecei recentemente a estudar algoritmos e estruturas de dados e estou realizando as implementações desses algoritmos em Java.
Em Java, temos muitas opções de como realizar essas implementações, justamente pelo legado deixado em cada versão em sua biblioteca padrão. O primeiro algoritmo que vi foi Merge Sort.
O que é Merge Sort?
Merge Sort é um algoritmo de ordenação que adota a estratégia Divide-and-Conquer. Ou seja, ela pega um problema maior e divide em vários sub-problemas, resolvendo primeiramente estes sub-problemas para proceder com uma computação a mais para resolver o problema maior a paritr da resolução desses sub-problemas.
Dito isso, podemos pegar um Array de números por exemplo para poder fazer ordenar ele e dividir este array em vários pequenos arrays, até uma parte atômica. Ordenamos essa parte atômica e vamos juntando estas soluções até formar um array que esteja completamente ordenado. Isto é o Merge Sort.
Implementando
Para saber que minha implementação está correta, vou utilizar um approach básico de TDD: primeiro vou escrever um teste para depois escrever a implementação em si.
O teste é simples:
public class MergeSortTest {
@Test
public void shouldGiveASortedArray () {
final var inputArray = new int[]{ 5, 4, 1, 8, 7, 2, 6, 3 };
final var desiredArray = new int[]{ 1, 2, 3, 4, 5, 6, 7, 8 };
var sorted = MergeSort.sort(inputArray);
IntStream.range(0, sorted.length).forEach(i -> {
assertEquals(desiredArray[i], sorted[i]);
});
}
}
Aqui, estou levando em consideração que em Java, arrays primitivos são reference types. O assertEquals faz uma comparação simples (utilizando um ==) entre cada um dos comparados. Sendo assim, é melhor destrinchar cada um dos itens e fazer essa comparação para assegurar que a ordem está correta!
Primeira implementação: usando apenas primitivos e operações primitivas
A primeira implementação é aquela crua e que é feita para fazer funcionar de fato:
public class MergeSort {
public static int[] sort (int[] unsorted) {
var length = unsorted.length;
if (length == 1) return unsorted;
if (length == 2) {
if (unsorted[0] > unsorted[1]) {
var placeholder = unsorted[1];
unsorted[1] = unsorted[0];
unsorted[0] = placeholder;
}
return unsorted;
}
int halfArrLength = length / 2;
int[] firstHalf = Arrays.copyOfRange(unsorted, 0, halfArrLength);
int[] secondHalf = Arrays.copyOfRange(unsorted, halfArrLength, length);
var firstHalfSorted = sort(firstHalf);
var secondHalfSorted = sort(secondHalf);
var outputSorted = new int[length];
var firstIndex = 0;
var secondIndex = 0;
for (int i = 0; i < length; i++) {
if (firstIndex >= firstHalfSorted.length) {
outputSorted[i] = secondHalfSorted[secondIndex];
secondIndex++;
continue;
}
var oneTerm = firstHalfSorted[firstIndex];
if (secondIndex >= secondHalfSorted.length) {
outputSorted[i] = firstHalfSorted[firstIndex];
firstIndex++;
continue;
}
var secondTerm = secondHalfSorted[secondIndex];
if (oneTerm < secondTerm) {
outputSorted[i] = oneTerm;
firstIndex++;
} else {
outputSorted[i] = secondTerm;
secondIndex++;
}
}
return outputSorted;
}
}
Podemos ver que nesse caso, estamos fazendo de fato uma manipulação muito crua dos arrays e não estamos tirando nenhuma vantagem do que a biblioteca padrão de Java nos oferece. Tecnicamente poderíamos realizar tudo isso com operadores de baixo nível e zero abstração, sem utilizar qualquer classe externa.
Segunda implementação: limpando o código e utilizando alguns recursos
public class MergeSort {
public static int[] sort (int[] unsorted) {
var length = unsorted.length;
if (length == 1) return unsorted;
if (length == 2) {
var firstOfUnsorted = unsorted[0];
var secondOfUnsorted = unsorted[1];
if (firstOfUnsorted > secondOfUnsorted) {
unsorted[1] = firstOfUnsorted;
unsorted[0] = secondOfUnsorted;
}
return unsorted;
}
int halfArrLength = length / 2;
var firstHalfSorted = copyAndSort(unsorted, 0, halfArrLength);
var secondHalfSorted = copyAndSort(unsorted, halfArrLength, length);
var outputSorted = new int[length];
var firstIndex = 0;
var secondIndex = 0;
for (int i = 0; i < length; i++) {
final var actualIndex = i;
Consumer<Integer> assignToOutput =
(value) -> outputSorted[actualIndex] = value;
if (isGreatherOrEquals(firstIndex, firstHalfSorted.length)) {
assignToOutput.accept(secondHalfSorted[secondIndex]);
secondIndex++;
continue;
}
if (isGreatherOrEquals(secondIndex, secondHalfSorted.length)) {
assignToOutput.accept(firstHalfSorted[firstIndex]);
firstIndex++;
continue;
}
var oneTerm = firstHalfSorted[firstIndex];
var secondTerm = secondHalfSorted[secondIndex];
if (oneTerm < secondTerm) {
assignToOutput.accept(oneTerm);
firstIndex++;
} else {
assignToOutput.accept(secondTerm);
secondIndex++;
}
}
return outputSorted;
}
private static boolean isGreatherOrEquals (int i, int j) {
return i >= j;
}
private static int[] copyAndSort (int[] unsorted, int start, int end) {
return sort(Arrays.copyOfRange(unsorted, start, end));
}
}
Na segunda implementação, fiz algumas modificações importantes.
- Eu não quero ter sempre que lembrar de ter que fazer currying com os métodos
sorteArrays::copyOfRange. Neste caso, extrai-se um método em separado para simplificar as chamadas. Então só chamo aquiMergeSort::copyAndSortque já irá fazer as duas operações para mim de uma vez. Ainda sim é uma chamada recursiva. - Uso um lambda para simplificar a inclusão de um elemento para um array destino. Neste caso, basta eu chamar este lambda para adicionar. Não preciso mais fazer
target[i], simplificando minha carga cognitiva ao escrever o código.
Porém, esta segunda implementação não tira vantagem que a biblioteca padrão do java tem.
Terceira Implementação: usando collections.
public class MergeSort {
private static List<Integer> sort (List<Integer> unsorted) {
var size = unsorted.size();
if (size <= 2) {
// simple reordering, behind the scenes is a merge sort
return unsorted.stream()
.sorted(Comparator.naturalOrder())
.collect(Collectors.toList());
}
var halfSize = size / 2;
var firstHalfSorted = sort(unsorted.subList(0, halfSize));
var secondHalfSorted = sort(unsorted.subList(halfSize, size));
var finalList = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
if (firstHalfSorted.isEmpty()) {
finalList.addAll(secondHalfSorted);
break;
} else if (secondHalfSorted.isEmpty()) {
finalList.addAll(firstHalfSorted);
break;
} else if (firstHalfSorted.get(0) < secondHalfSorted.get(0)) {
finalList.add(firstHalfSorted.remove(0));
} else {
finalList.add(secondHalfSorted.remove(0));
}
}
return finalList;
}
public static int[] sort (int[] unsorted) {
var list = Arrays.stream(unsorted).boxed().toList();
var sortedList = sort(list);
return sortedList.stream().mapToInt(x -> x).toArray();
}
}
Neste caso aqui, a manipulação de fato irá acontecer em cima de um ArrayList. O método publico sort irá apenas receber um int[], convertê-lo em List<Integer> e repassa-lo ao método privado.
O resultado será convertido de volta para um int[] e retornado para o caller. Este processo de unboxing é feito através de uma função de identidade (x -> x) que vai converter um Stream<Integer> para um IntStream.
IMPORTANTE: Streams usam Generics para tipagem interna, sendo assim, uma Stream convencional não suporta tipos primitivos, fazendo-se necessário fazer o processo de boxing/unboxing do tipo.
No caso, podemos nos permitir a fazer uma leve trapaça aqui:
if (size <= 2) {
// simple reordering, behind the scenes is a merge sort
return unsorted.stream()
.sorted(Comparator.naturalOrder())
.collect(Collectors.toList());
}
A trapaça se dá pelo fato de que, por baixo dos panos, os métodos de ordenação no Java implementam MergeSort. Nas versões mais modernas eles implementam uma variação chamada TimSort que é mais eficiente que o MergeSort per si.
Como temos apenas dois itens, utilizando este método já vai cair naturalmente no caso base do método de ordenação da biblioteca padrão.
O restante da diferença então se dá em utilizar ArrayLists para realizar a manipulação do Array. Aqui eu tenho que me preocupar menos com índices, me preocupando apenas com o tamanho de cada um dos elementos e realizando a remoção direta de cada um dos ArrayLists resultantes, como uma stack.
for (int i = 0; i < size; i++) {
if (firstHalfSorted.isEmpty()) {
finalList.addAll(secondHalfSorted);
break;
} else if (secondHalfSorted.isEmpty()) {
finalList.addAll(firstHalfSorted);
break;
} else if (firstHalfSorted.get(0) < secondHalfSorted.get(0)) {
finalList.add(firstHalfSorted.remove(0));
} else {
finalList.add(secondHalfSorted.remove(0));
}
}
Neste caso, tenho uma otimização final em que, se um dos arrays ficou vazio, ele pega todo o restante dos outros elementos e adiciona direto no array final, adiantando todo o processo.
Concluindo.
Esta implementação pode ser melhorada em muito mais ordens! Recomendo experimentar em cima disso.
O repositório com a implementação e o histórico se encontram aqui:
https://github.com/EronAlves1996/estruturas-de-dados
Top comments (0)