Introduzione a Merge Sorting Algorithms in Java
Unisci gli algoritmi di ordinamento sono molto importanti in Informatica. L'output dell'ordinamento consiste nel disporre gli elementi di un elenco in un determinato ordine (crescente o decrescente). Unisci ordinamento è uno degli algoritmi di ordinamento più efficienti disponibili in quanto si basa sul concetto di divisione e conquista. Come suggerisce il nome, prima dividi il problema più grande in piccoli problemi piuttosto che risolvere i problemi più piccoli al fine di risolvere il problema più grande. In questo articolo, discuteremo degli algoritmi di ordinamento di tipo merge in Java. Concettualmente, Merge sort è una combinazione di due algoritmi di base chiamati MERGE e MERGE_SORT che funziona come segue:
- Dividi l'elenco non ordinato in n numero di elenchi secondari a elemento singolo (n è il numero totale di elementi nell'elenco non ordinato).
- Unisci ripetutamente gli elenchi secondari in elenchi ordinati finché non esiste un solo elenco ordinato.
Implementazione di Merge Sorting Algorithms in Java
L'algoritmo MERGE è la procedura di combinazione di due elenchi ordinati in un elenco ordinato.
Esempio: supponiamo che ci siano due elenchi, ovvero Elenco 1 (6, 3) e Elenco 2 (3, 1, 9).
1. Prima ordina entrambi gli elenchi.
Elenco 1
Elenco 2
Ora applicheremo una tecnica di fusione su di essa.
- Quindi, creeremo un nuovo elenco di dimensioni m + n in cui m è il numero di elementi in Elenco 1 e n è il numero di elementi in Elenco 2.
Elenco 3
Nel nostro caso m = 2 e n = 3, quindi m + n = 5.
- Ora, abbiamo un doppio puntatore. Un primo puntatore che punta sulla prima posizione dell'elenco 1 e Secondo puntatore che punta sulla prima posizione dell'elenco 2.
4. Quindi confronteremo il valore di entrambi i puntatori. Il puntatore con un valore inferiore, copia quell'elemento in Elenco 3 e sposta il puntatore a destra dell'elenco con un valore più piccolo e l'elenco risultante (cioè Elenco 1 e Elenco 3).
5. Allo stesso modo, eseguire nuovamente il passaggio 4.
Ulteriore attraversamento …
NOTA: se uno degli elenchi (ovvero l'elenco 1 o l'elenco 2) viene attraversato completamente come nel caso precedente, copiare l'intero contenuto degli altri elenchi dal puntatore all'elenco dei risultati (ovvero l'elenco 3) come segue.
Algoritmo e pseudocodice
I due algoritmi utilizzati in Merge Algorithm sono:
- MERGE (ARR, F, M, L) è un processo che presuppone quanto segue:
- ARR (F… .M) e ARR (M + 1… .L) sono elenchi ordinati.
- Unisce i due elenchi secondari ordinati in un ARR (F… .L).
- SORT (ARR (), F, L) // qui F è il primo e L è l'ultimo indice dell'array.
If (L> 1)
- Trova il punto centrale per dividere l'elenco in due metà:
medio M = (F + L) / 2
- Chiama Merge Sort per il primo semestre:
Chiama SORT (ARR, 1, M)
- Chiama Merge Sort per la seconda metà:
Chiama SORT (ARR, M + 1, L)
- Unisci le metà ordinate nei passaggi 2 e 3:
Chiama MERGE (ARR, L, M, R)
Esempio
Facciamo un esempio di un array ARR (10, 6, 8, 5, 7, 3, 4). Useremo l'algoritmo Merge per ordinare l'array usando la sua tecnica Divide and Conquer. Possiamo vedere la figura sotto che l'array è ricorsivamente diviso in due metà fino a quando la dimensione diventa 1. Una volta che la dimensione diventa 1, chiamiamo i processi di unione e ricominciamo a unire gli elenchi fino a quando l'elenco completo non viene unito.
NOTA: nella figura seguente, i numeri in rosso indicano l'ordine in cui i passaggi vengono elaborati per formare la matrice ordinata.
Codice programma:
import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)import java.util.Scanner;
public class mergeSort (
// merges two sublists of arr().
// first list is arr(l..m) // second list is arr(m+1..r) void mergeAlgo(int arr(), int l, int m, int r)
(
// find the sizes of two lists to be merged
int n1 = m - l + 1;
int n2 = r - m;
// create temp array
int L() = new int (n1);
int R() = new int (n2);
// copy data to temp arrays
for (int i=0; i L(i) = arr(l + i);
for (int j=0; j R(j) = arr(m + 1+ j);
/* merge the temp arrays */
// initial indexes of first and second list
int i = 0, j = 0;
// initial index of merged sub list
int k = l;
while (i < n1 && j < n2)
(
if (L(i) <= R(j))
(
arr(k) = L(i);
i++;
)
else
(
arr(k) = R(j);
j++;
)
k++;
)
// copy remaining elements of L() if any
while (i < n1)
(
arr(k) = L(i);
i++;
k++;
)
// copy remaining elements of R() if any
while (j < n2)
(
arr(k) = R(j);
j++;
k++;
)
)
// main function that sorts arr(l..r) using mergeAlgo()
void sort(int arr(), int l, int r)
(
if (l < r)
(
// find the middle index
int m = (l+r)/2;
// sort first and second halves
sort(arr, l, m);
sort(arr, m+1, r);
// merge the above two sorted halves
mergeAlgo(arr, l, m, r);
)
)
/* A function to print list of size n */
static void printArray(int arr())
(
int n = arr.length;
for (int i=0; i System.out.print(arr(i) + " ");
System.out.println();
)
public static void main(String args())
(
Scanner myObj = new Scanner(System.in);
System.out.println("Enter the size of list:");
int N = myObj.nextInt();
System.out.println("Enter the elements in list separated by space:");
int arr() = new int(N);
for(int i=0; i arr(i) = myObj.nextInt();
)
mergeSort mg = new mergeSort();
mg.sort(arr, 0, arr.length-1);
System.out.println("\nSorted list:");
printArray(arr);
)
)
Produzione:
Conclusione - Unisci gli algoritmi di ordinamento in Java
Unisci le complessità migliori, peggiori e nel caso medio sono le stesse che lo rendono un algoritmo più efficiente. Funziona più velocemente di altre tecniche di ordinamento. Unisci ordinamento può essere applicato a file di qualsiasi dimensione. È altamente parallelizzabile grazie all'uso del metodo divide-and-conquer. Al fine di sviluppare solide basi di informatica, si consiglia di comprendere a fondo i diversi algoritmi di ordinamento.
Articoli consigliati
Questa è una guida per unire gli algoritmi di ordinamento in Java. Qui discutiamo l'implementazione di Merge Sorting Algorithms in java e Algorithm & Pseudocode con esempio. Puoi anche consultare i nostri altri articoli suggeriti–
- Selezione ordinamento in Java
- Dichiarazione del caso in Java
- Modificatori di accesso in Java
- Unisci ordinamento in JavaScript
- Che cos'è l'istruzione case in JavaScript?
- Modificatori di accesso in PHP
- Algoritmi di ordinamento rapido in Java
- Guida completa all'ordinamento in C # con esempi
- Funzione di ordinamento in Python con esempi
- I 6 migliori algoritmi di ordinamento in JavaScript
