Introdução
O Merge Sort é um algoritmo de ordenação eficiente e estável que utiliza a técnica de "Dividir e Conquistar" (Divide and Conquer) para ordenar um array. Neste laboratório, você aprenderá como implementar o Merge Sort em Java usando uma abordagem recursiva.
Criar um método Merge Sort
Crie um método público estático chamado mergeSort() com três parâmetros inteiros: int arrToSort[], startIdx, endIdx. Você precisa verificar se o comprimento do array é menor que 2 e, em caso afirmativo, retornar. Caso contrário, calcule o índice do meio do array e divida o array em metades esquerda e direita. As metades esquerda e direita também devem ser divididas recursivamente. Após dividi-las, você deve uni-las para formar um array ordenado.
public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
if (startIdx >= endIdx) {
return;
}
int midIdx = startIdx + (endIdx - startIdx) / 2;
mergeSort(arrToSort, startIdx, midIdx);
mergeSort(arrToSort, midIdx + 1, endIdx);
merge(arrToSort, startIdx, midIdx, endIdx);
}
Criar um método Merge
Crie outro método público estático chamado merge() com quatro parâmetros: int arrToSort[], startIdx, midIdx e endIdx. Você precisa inicializar os arrays esquerdo e direito. Em seguida, você precisa unir ambos os arrays comparando os elementos de cada array e mesclando-os em um único array.
public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
int[] leftArr = new int[midIdx - startIdx + 1];
int[] rightArr = new int[endIdx - midIdx];
for (int i = 0; i < leftArr.length; i++) {
leftArr[i] = arrToSort[startIdx + i];
}
for (int i = 0; i < rightArr.length; i++) {
rightArr[i] = arrToSort[midIdx + i + 1];
}
int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
leftArrIdx += 1;
} else {
arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
rightArrIdx += 1;
}
sortedArrIdx += 1;
}
while (leftArrIdx < leftArr.length) {
arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
leftArrIdx += 1;
sortedArrIdx += 1;
}
while (rightArrIdx < rightArr.length) {
arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
rightArrIdx += 1;
sortedArrIdx += 1;
}
}
Testar Merge Sort
Vamos testar o método mergeSort() escrevendo código para ordenar um array de entrada. Crie um método main. Em seguida, declare um array de inteiros com alguns valores não ordenados. Chame o método mergeSort() e passe o array não ordenado para ele. Finalmente, imprima o array ordenado no console. O bloco de código para esta etapa terá a seguinte aparência:
public static void main(String[] args) {
int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
mergeSort(arrToSort, 0, arrToSort.length - 1);
System.out.println(Arrays.toString(arrToSort));
}
Após executar o programa, a saída deve ser: [0, 1, 2, 4, 6, 8].
Testar com Array Vazio
Crie outro teste para um array vazio. Declare um array de inteiros vazio. Chame o método mergeSort() e passe-o para o array vazio. Finalmente, imprima o array ordenado no console. O bloco de código para esta etapa terá a seguinte aparência:
int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));
A saída deve ser a mesma que a entrada.
Testar com Array de um Único Elemento
Crie mais um teste com um array de um único elemento. Declare um array de inteiros com um único elemento. Chame o método mergeSort() e passe-o para o array de um único elemento. Finalmente, imprima o array ordenado no console. O bloco de código para esta etapa terá a seguinte aparência:
int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));
A saída deve ser a mesma que a entrada.
Testar com Valores Negativos
Crie outro teste para um array que consiste em inteiros negativos. Declare um array de inteiros que inclua alguns inteiros negativos. Chame o método mergeSort() e passe o array como um argumento. Finalmente, imprima o array ordenado no console. O bloco de código para esta etapa terá a seguinte aparência:
int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));
Após executar o programa, a saída deve ser: [-9, -7, -1, 0, 2, 6, 8].
Testar com Elementos Não Numéricos
Crie outro teste ordenando um array de elementos não numéricos. Declare um array de strings. Chame o método mergeSort() e passe o array como um argumento. Finalmente, imprima o array ordenado no console. O bloco de código para esta etapa terá a seguinte aparência:
String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));
Após executar o programa, a saída deve ser: ['Bob', 'Christine', 'David', 'Emily', 'John'].
Código fonte final
Aqui está o código fonte final para o Merge Sort:
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
if (startIdx >= endIdx) {
return;
}
int midIdx = startIdx + (endIdx - startIdx) / 2;
mergeSort(arrToSort, startIdx, midIdx);
mergeSort(arrToSort, midIdx + 1, endIdx);
merge(arrToSort, startIdx, midIdx, endIdx);
}
public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
int[] leftArr = new int[midIdx - startIdx + 1];
int[] rightArr = new int[endIdx - midIdx];
for (int i = 0; i < leftArr.length; i++) {
leftArr[i] = arrToSort[startIdx + i];
}
for (int i = 0; i < rightArr.length; i++) {
rightArr[i] = arrToSort[midIdx + i + 1];
}
int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
leftArrIdx += 1;
} else {
arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
rightArrIdx += 1;
}
sortedArrIdx += 1;
}
while (leftArrIdx < leftArr.length) {
arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
leftArrIdx += 1;
sortedArrIdx += 1;
}
while (rightArrIdx < rightArr.length) {
arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
rightArrIdx += 1;
sortedArrIdx += 1;
}
}
public static void main(String[] args) {
//create an unsorted integer array
int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
//sort the integer array using Merge Sort
mergeSort(arrToSort, 0, arrToSort.length - 1);
//print the sorted array
System.out.println(Arrays.toString(arrToSort));
//create an empty integer array
int[] emptyArr = {};
//sort the empty array
mergeSort(emptyArr, 0, emptyArr.length - 1);
//print the sorted array
System.out.println(Arrays.toString(emptyArr));
//create a single-element array
int[] singleElementArr = {7};
//sort the single-element array
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
//print the sorted array
System.out.println(Arrays.toString(singleElementArr));
//create a negative integer array
int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
//sort the negative integer array
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
//print the sorted array
System.out.println(Arrays.toString(arrWithNegatives));
//create a string array
String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
//sort the string array
mergeSort(strsToSort, 0, strsToSort.length - 1);
//print the sorted array
System.out.println(Arrays.toString(strsToSort));
}
}
Executar o programa
Compile e execute o programa usando o terminal:
javac MergeSort.java && java MergeSort
Resumo
Neste laboratório, você aprendeu o que é Merge Sort, como ele funciona e como implementá-lo em Java. Você criou dois métodos public static, mergeSort() e merge(), para dividir e mesclar (merge) o array de entrada, respectivamente. Após a implementação, você o testou em várias entradas, discutiu a complexidade de tempo e espaço, e verificou sua funcionalidade. Parabéns! Você concluiu com sucesso o laboratório de Merge Sort em Java.
