Menu

Merge Sort In Java - Programa para implementar MergeSort

  • Principal
  • Outro
  • Merge Sort In Java - Programa para implementar MergeSort

merge sort java program implement mergesort

Experimente Nosso Instrumento Para Eliminar Problemas

Este tutorial explica o que é Merge Sort em Java, Algoritmo MergeSort, Pseudo Código, Implementação de Merge Sort, Exemplos de MergeSort Iterativo e Recursivo:

A técnica de classificação de mesclagem usa uma estratégia de “dividir e conquistar”. Nesta técnica, o conjunto de dados a ser classificado é dividido em unidades menores para classificá-lo.

=> Leia a série de treinamento Easy Java.

Mesclar classificação em Java

O que você aprenderá:

Mesclar classificação em Java

Por exemplo, se uma matriz deve ser classificada usando mergesort, a matriz é dividida em torno de seu elemento do meio em duas submatrizes. Essas duas submatrizes são divididas em unidades menores até que tenhamos apenas 1 elemento por unidade.

Uma vez feita a divisão, esta técnica mescla essas unidades individuais, comparando cada elemento e classificando-os ao mesclar. Dessa forma, no momento em que todo o array é mesclado novamente, obtemos um array ordenado.

Neste tutorial, discutiremos todos os detalhes dessa técnica de classificação em geral, incluindo seu algoritmo e pseudocódigos, bem como a implementação da técnica em Java.

Algoritmo MergeSort em Java

A seguir está o algoritmo da técnica.

# 1) Declara um array meuArray de comprimento N

#dois) Verifique se N = 1, meuArray já está classificado

# 3) Se N for maior que 1,

  • definir esquerda = 0, direita = N-1
  • computar meio = (esquerda + direita) / 2
  • Chame a sub-rotina merge_sort (myArray, left, middle) => isso classifica a primeira metade da matriz
  • Chame a sub-rotina merge_sort (myArray, middle + 1, right) => isso classificará a segunda metade da matriz
  • Chame mesclagem de sub-rotina (meuArray, esquerda, meio, direita) para mesclar arrays classificados nas etapas acima.

# 4) Saída

Conforme visto nas etapas do algoritmo, o array é dividido em dois no meio. Em seguida, classificamos recursivamente a metade esquerda do array e depois a metade direita. Depois de classificarmos individualmente as duas metades, elas serão mescladas para obter uma matriz classificada.

Mesclar Pseudo Código de Classificação

Vamos ver o pseudocódigo para a técnica Mergesort. Conforme já discutido, uma vez que esta é uma técnica de 'dividir e conquistar', apresentaremos as rotinas para dividir o conjunto de dados e, em seguida, mesclar os conjuntos de dados classificados.

procedure mergesort( var intarray as array ) if ( n == 1 ) return intarray var lArray as array = intarray(0) ... intarray (n/2) var rArray as array = intarray (n/2+1) ... intarray (n) lArray = mergesort(lArray ) rArray = mergesort(rArray ) return merge(lArray, rArray ) end procedure procedure merge( var l_array as array, var r_array as array ) var result as array while (l_array and r_array have elements ) if (l_array (0) > r_array (0) ) add r_array (0) to the end of result remove r_array (0) from r_array else add l_array (0) to the end of result remove l_array (0) from l_array end if end while while (l_array has elements ) add l_array (0) to the end of result remove l_array (0) from l_array end while while (r_array has elements ) add r_array (0) to the end of result remove r_array (0) from r_array end while return result end procedure

No pseudocódigo acima, temos duas rotinas, ou seja, Mergesort e merge. A rotina Mergesort divide o array de entrada em um array individual que é fácil de classificar. Em seguida, ele chama a rotina de mesclagem.

A rotina de mesclagem mescla as submatrizes individuais e retorna uma matriz ordenada resultante. Tendo visto o algoritmo e o pseudocódigo para a classificação Merge, vamos agora ilustrar essa técnica usando um exemplo.

Ilustração MergeSort

Considere a seguinte matriz que deve ser classificada usando esta técnica.

Mesclar ilustração de classificação

Agora, de acordo com o algoritmo de classificação Merge, vamos dividir este array em seu elemento intermediário em dois subarrays. Em seguida, continuaremos dividindo os subarrays em arrays menores até obtermos um único elemento em cada array.

Uma vez que cada submatriz possui apenas um elemento, mesclamos os elementos. Durante a fusão, comparamos os elementos e garantimos que eles estão em ordem na matriz combinada. Portanto, trabalhamos para obter um array mesclado que seja classificado.

O processo é mostrado abaixo:

Mesclar processo de classificação

Conforme mostrado na ilustração acima, vemos que a matriz é dividida repetidamente e, em seguida, mesclada para obter uma matriz classificada. Com esse conceito em mente, vamos passar para a implementação do Mergesort na linguagem de programação Java.

Implementação de mesclagem de classificação em Java

Podemos implementar a técnica em Java usando duas abordagens.

Classificação de fusão iterativa

Esta é uma abordagem de baixo para cima. As submatrizes de um elemento são classificadas e mescladas para formar matrizes de dois elementos. Essas matrizes são então mescladas para formar matrizes de quatro elementos e assim por diante. Desta forma, a matriz classificada é construída indo para cima.

O exemplo Java abaixo mostra a técnica iterativa Merge Sort.

import java.util.Arrays; class Main { // merge arrays : intArray(start...mid) and intArray(mid+1...end) public static void merge(int() intArray, int() temp, int start, int mid, int end) { int k = start, i = start, j = mid + 1; // traverse through elements of left and right arrays while (i <= mid && j <= end) { if (intArray(i) < intArray(j)) { temp(k++) = intArray(i++); } else { temp(k++) = intArray(j++); } } // Copy remaining elements while (i <= mid) { temp(k++) = intArray(i++); } // copy temp array back to the original array to reflect sorted order for (i = start; i <= end; i++) { intArray(i) = temp(i); } } // sorting intArray(low...high) using iterative approach public static void mergeSort(int() intArray) { int low = 0; int high = intArray.length - 1; // sort array intArray() using temporary array temp int() temp = Arrays.copyOf(intArray, intArray.length); // divide the array into blocks of size m // m = (1, 2, 4, 8, 16...) for (int m = 1; m <= high - low; m = 2*m) { for (int i = low; i < high; i += 2*m) { int start = i; int mid = i + m - 1; int end = Integer.min(i + 2 * m - 1, high); //call merge routine to merge the arrays merge(intArray, temp, start, mid, end); } } } public static void main(String() args) { //define array to be sorted int() intArray = { 10,23,-11,54,2,9,-10,45 }; //print the original array System.out.println('Original Array : ' + Arrays.toString(intArray)); //call mergeSort routine mergeSort(intArray); //print the sorted array System.out.println('Sorted Array : ' + Arrays.toString(intArray)); } }

Resultado:

Matriz original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriz classificada: (-11, -10, 2, 9, 10, 23, 45, 54)

Classificação de fusão iterativa - Saída

Classificação de fusão recursiva

Esta é uma abordagem de cima para baixo. Nesta abordagem, o array a ser classificado é dividido em arrays menores até que cada array contenha apenas um elemento. Então, a classificação torna-se fácil de implementar.

O código Java a seguir implementa a abordagem recursiva da técnica de classificação Merge.

import java.util.Arrays; public class Main { public static void merge_Sort(int() numArray) { //return if array is empty if(numArray == null) { return; } if(numArray.length > 1) { int mid = numArray.length / 2; //find mid of the array // left half of the array int() left = new int(mid); for(int i = 0; i

Resultado:

Matriz original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriz classificada: (- 11, -10, 2, 9, 10, 23, 45, 54)

MergeSort recursivo - Saída

Na próxima seção, vamos mudar de arrays e usar a técnica para classificar a lista vinculada e as estruturas de dados da lista de array.

Classificar lista vinculada usando mesclagem de classificação em Java

A técnica Mergesort é a mais preferida para classificar listas vinculadas. Outras técnicas de classificação funcionam mal quando se trata da lista vinculada por causa de seu acesso principalmente sequencial.

O programa a seguir classifica uma lista vinculada usando esta técnica.

import java.util.*; // A singly linked list node class Node { int data; Node next; Node(int data, Node next) { this.data = data; this.next = next; } }; class Main { //two sorted linked list are merged together to form one sorted linked list public static Node Sorted_MergeSort(Node node1, Node node2) { //return other list if one is null if (node1 == null) return node2; else if (node2 == null) return node1; Node result; // Pick either node1 or node2, and recur if (node1.data <= node2.data) { result = node1; result.next = Sorted_MergeSort(node1.next, node2); } else { result = node2; result.next = Sorted_MergeSort(node1, node2.next); } return result; } //splits the given linked list into two halves public static Node() FrontBackSplit(Node source) { // empty list if (source == null || source.next == null) { return new Node(){ source, null } ; } Node slow_ptr = source; Node fast_ptr = source.next; // Advance 'fast' two nodes, and advance 'slow' one node while (fast_ptr != null) { fast_ptr = fast_ptr.next; if (fast_ptr != null) { slow_ptr = slow_ptr.next; fast_ptr = fast_ptr.next; } } // split the list at slow_ptr just before mid Node() l_list = new Node(){ source, slow_ptr.next }; slow_ptr.next = null; return l_list; } // use Merge sort technique to sort the linked list public static Node Merge_Sort(Node head) { // list is empty or has single node if (head == null || head.next == null) { return head; } // Split head into 'left' and 'right' sublists Node() l_list = FrontBackSplit(head); Node left = l_list(0); Node right = l_list(1); // Recursively sort the sublists left = Merge_Sort(left); right = Merge_Sort(right); // merge the sorted sublists return Sorted_MergeSort(left, right); } // function to print nodes of given linked list public static void printNode(Node head) { Node node_ptr = head; while (node_ptr != null) { System.out.print(node_ptr.data + ' -> '); node_ptr = node_ptr.next; } System.out.println('null'); } public static void main(String() args) { // input linked list int() l_list = { 4,1,6,2,7,3,8 }; Node head = null; for (int key: l_list) { head = new Node(key, head); } //print the original list System.out.println('Original Linked List: '); printNode(head); // sort the list head = Merge_Sort(head); // print the sorted list System.out.println(' Sorted Linked List:'); printNode(head); } }

Resultado:

Lista original vinculada:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nulo
Lista Vinculada Classificada:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nulo

perguntas da entrevista do qa tester de nível básico

Saída - Classificar lista vinculada

Classificar ArrayList usando Merge Sort em Java

Como Arrays e listas vinculadas, também podemos usar essa técnica para classificar uma ArrayList. Usaremos rotinas semelhantes para dividir a ArrayList recursivamente e, em seguida, mesclar as sublistas.

O código Java abaixo implementa a técnica de classificação Merge para ArrayList.

import java.util.ArrayList; class Main { //splits arrayList into sub lists. public static void merge_Sort(ArrayList numList){ int mid; ArrayList left = new ArrayList<>(); ArrayList right = new ArrayList<>(); if (numList.size() > 1) { mid = numList.size() / 2; // left sublist for (int i = 0; i numList, ArrayList left, ArrayList right){ //temporary arraylist to build the merged list ArrayList temp = new ArrayList<>(); //initial indices for lists int numbersIndex = 0; int leftIndex = 0; int rightIndex = 0; //traverse left and righ lists for merging while (leftIndex = left.size()) { temp = right; tempIndex = rightIndex; } else { temp = left; tempIndex = leftIndex; } for (int i = tempIndex; i numList = new ArrayList<>(); int temp; //populate the ArrayList with random numbers for (int i = 1; i <= 9; i++) numList.add( (int)(Math.random() * 50 + 1) ); //print original ArrayList of random numbers System.out.println('Original ArrayList:'); for(int val: numList) System.out.print(val + ' '); //call merge_Sort routine merge_Sort(numList); //print the sorted ArrayList System.out.println(' Sorted ArrayList:'); for(int ele: numList) System.out.print(ele + ' '); System.out.println(); } }

Resultado:

ArrayList original:
17 40 36 7 6 23 35 2 38
Sorted ArrayList:
2 6 7 17 23 35 36 38 40

Saída - Classificar ArrayList

perguntas frequentes

P # 1) A classificação de mesclagem pode ser feita sem recursão?

Responda: sim. Podemos realizar uma classificação Merge não recursiva chamada 'classificação Merge iterativa'. Esta é uma abordagem ascendente que começa mesclando submatrizes com um único elemento em uma submatriz de dois elementos.

Em seguida, essas submatrizes de 2 elementos são mescladas em submatrizes de 4 elementos e assim por diante, usando construções iterativas. Este processo continua até que tenhamos um array ordenado.

Q # 2) A classificação de mesclagem pode ser feita no local?

Responda: A classificação de mesclagem geralmente não está no local. Mas podemos fazer isso no local usando alguma implementação inteligente. Por exemplo, armazenando o valor de dois elementos em uma posição. Isso pode ser extraído posteriormente usando módulo e divisão.

Q # 3) O que é uma classificação de mesclagem de 3 vias?

Responda: A técnica que vimos acima é uma classificação de mesclagem de 2 vias em que dividimos o array a ser classificado em duas partes. Em seguida, classificamos e mesclamos o array.

Em uma classificação de mesclagem de 3 vias, em vez de dividir o array em 2 partes, nós o dividimos em 3 partes, então classificamos e finalmente fundimos.

Q # 4) Qual é a complexidade de tempo do Mergesort?

Responda: A complexidade de tempo geral da classificação de mesclagem em todos os casos é O (nlogn).

Q # 5) Onde a classificação Merge é usada?

Responda: É usado principalmente para classificar a lista vinculada em tempo O (nlogn). Também é usado em cenários distribuídos em que novos dados chegam no sistema antes ou depois da classificação. Isso também é usado em vários cenários de banco de dados.

Conclusão

A classificação por mesclagem é uma classificação estável e é realizada primeiro dividindo o conjunto de dados repetidamente em subconjuntos e, em seguida, classificando e mesclando esses subconjuntos para formar um conjunto de dados classificado. O conjunto de dados é dividido até que cada conjunto de dados seja trivial e fácil de classificar.

Vimos as abordagens recursiva e iterativa da técnica de classificação. Também discutimos a classificação da estrutura de dados Linked List e ArrayList usando Mergesort.

Continuaremos com a discussão de mais técnicas de classificação em nossos próximos tutoriais. Fique atento!

=> Visite aqui a série exclusiva de tutoriais de treinamento em Java.

Leitura recomendada

^