Introducere în Merge Sorting Algorithms in Java
Algoritmele de sortare a Merge sunt foarte importante în informatică. Rezultatul sortării este de a aranja elementele unei liste la o anumită ordine (ascendentă sau descendentă). Sortarea Merge este unul dintre cei mai eficienți algoritmi de sortare disponibili, deoarece se bazează pe conceptul de divizare și cucerire. După cum sugerează și numele, mai întâi împărțiți problema mai mare în probleme mici decât rezolvați problemele mai mici pentru a rezolva problema mai mare. În acest articol, vom discuta algoritmii de sortare a îmbinării în Java. Conceptual, sortarea Merge este o combinație de doi algoritmi de bază numiți MERGE și MERGE_SORT care funcționează astfel:
- Împărțiți lista nesortată în n număr de subliste cu un singur articol (n este numărul total de elemente din lista nesortată).
- Fuzionați repetat subliste în subliste sortate până când nu există decât o listă sortată.
Implementarea algoritmilor de sortare Merge în Java
Algoritmul MERGE este procedura de combinare a două liste sortate într-o listă sortată.
Exemplu: Să presupunem că există două liste, adică Lista 1 (6, 3) și Lista 2 (3, 1, 9).
1. Sortează mai întâi ambele liste.
Lista 1
Lista 2
Acum, vom aplica o tehnică de îmbinare.
- Apoi, vom crea o nouă listă de dimensiuni m + n unde m este numărul de elemente din Lista 1 și n este numărul de elemente din Lista 2.
Lista 3
În cazul nostru m = 2 și n = 3, deci m + n = 5.
- Acum, avem un doi indicatori. Un prim indicator care indică prima poziție a listei 1 și un al doilea indicator îndreptat către prima poziție a listei 2.
4. Apoi vom compara valoarea ambelor indicatoare. Indicatorul cu valoare mai mică, copiați elementul în Lista 3 și mutați indicatorul la dreapta listei cu o valoare mai mică și lista rezultată (adică Lista 1 și Lista 3).
5. În mod similar, efectuați iar și iar pasul 4.
Parcurgerea ulterioară …
NOTĂ: Dacă una dintre liste (adică lista 1 sau lista 2) este parcursă complet ca în cazul de mai sus, atunci copiați întregul conținut al altor liste de la pointer la lista de rezultate (adică lista 3) după cum urmează.
Algoritm și pseudocod
Cei doi algoritmi folosiți în algoritmul de îmbinare sunt:
- MERGE (ARR, F, M, L) este un proces care presupune următoarele:
- ARR (F… .M) și ARR (M + 1… .L) sunt liste ordonate.
- Fuzionează cele două sub-liste listate într-un singur ARR (F… .L).
- SORT (ARR (), F, L) // aici F este primul și L este ultimul index al tabloului.
Dacă (L> 1)
- Găsiți punctul de mijloc pentru a împărți lista în două jumătăți:
mijlocul M = (F + L) / 2
- Sunați sortarea Merge pentru prima jumătate:
Apelați SORT (ARR, 1, M)
- Sunați sortarea Merge pentru a doua jumătate:
Apelați SORT (ARR, M + 1, L)
- Combinați jumătățile sortate în etapele 2 și 3:
Apelați MERGE (ARR, L, M, R)
Exemplu
Să luăm un exemplu de matrice ARR (10, 6, 8, 5, 7, 3, 4). Vom folosi algoritmul Merge pentru a sorta Array folosind tehnica sa Divide și Conquer. Putem vedea figura de mai jos că Array-ul este împărțit recursiv în două jumătăți până când dimensiunea devine 1. Odată ce dimensiunea devine 1, atunci apelăm procese de combinare și începem fuzionarea listelor până când lista completă este contopită.
NOTĂ: În figura de mai jos, numerele în roșu indică ordinea în care sunt prelucrați pașii pentru a forma Array Sorted.
Codul programului:
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);
)
)
ieşire:
Concluzie - Merge Sorting Algorithms in Java
Complexitatea timpului cel mai bun, cel mai rău și cel mediu este același, ceea ce îl face un algoritm mai eficient. Funcționează mai repede decât alte tehnici de sortare. Sortare combinată poate fi aplicată fișierelor de orice dimensiune. Este foarte paralizabil datorită utilizării metodei de împărțire și de cucerire. Pentru a dezvolta elemente de bază puternice în informatică, vi se recomandă să înțelegeți în detaliu diferiți algoritmi de sortare.
Articole recomandate
Acesta este un ghid pentru Merge Sorting Algorithms in Java. Aici discutăm Implementarea algoritmilor de sortare Merge în java și Algoritm și Pseudocod, cu un exemplu. Puteți parcurge și alte articole propuse -
- Sortare selecție în Java
- Declarație de caz în Java
- Accesați modificatorii în Java
- Sortare Mergeți în JavaScript
- Ce este declarația de caz în JavaScript?
- Modificatori de acces în PHP
- Algoritmi de sortare rapidă în Java
- Ghid complet de sortare în C # cu exemple
- Funcția de sortare în Python cu exemple
- Top 6 Sortarea algoritmului în JavaScript