Úvod do zlúčenia algoritmov triedenia v Jave
Algoritmy zlúčenia triedenia sú v informatike veľmi dôležité. Výstupom triedenia je usporiadanie prvkov zoznamu do určitého poradia (buď vzostupne alebo zostupne). Zlúčiť triedenie je jedným z najúčinnejších dostupných algoritmov triedenia, pretože je založené na koncepte delenia a dobývania. Ako už názov napovedá, najprv rozdelte väčší problém na malé problémy, ako vyriešite menšie problémy, aby ste vyriešili väčší problém. V tomto článku budeme diskutovať o zlúčení algoritmov triedenia v Jave. Koncepčne je Merge sort kombináciou dvoch základných algoritmov s názvom MERGE a MERGE_SORT, ktoré fungujú takto:
- Rozdeľte netriedený zoznam do n počtu podzoznamov jednotlivých položiek (n je celkový počet prvkov v netriedenom zozname).
- Opakovane spájajte zoznamy do triedených zoznamov, až kým nebude k dispozícii iba jeden zoznam.
Implementácia algoritmov zlučovania triedenia v Jave
Algoritmus MERGE je postup kombinovania dvoch triedených zoznamov do jedného triedeného zoznamu.
Príklad: Predpokladajme, že existujú dva zoznamy, tj zoznam 1 (6, 3) a zoznam 2 (3, 1, 9).
1. Najprv zoraďte oba zoznamy.
Zoznam 1
Zoznam 2
Teraz na to použijeme metódu zlúčenia.
- Potom vytvoríme nový zoznam veľkostí m + n, kde m je počet prvkov v zozname 1 a n je počet prvkov v zozname 2.
Zoznam 3
V našom prípade m = 2 an = 3, takže m + n = 5.
- Teraz máme dva ukazovatele. Prvý ukazovateľ smerujúci na prvú pozíciu zoznamu 1 a druhý ukazovateľ ukazujúci na prvú pozíciu zoznamu 2.
4. Potom porovnáme hodnotu oboch ukazovateľov. Ukazovateľ s menšou hodnotou, skopírujte tento prvok do Zoznamu 3 a posuňte ukazovateľ vpravo od zoznamu s menšou hodnotou a výsledným zoznamom (tj Zoznam 1 a Zoznam 3).
5. Podobne opakujte krok 4 znova a znova.
Ďalšie prejdenie … ..
POZNÁMKA: Ak jeden zo zoznamov (tj zoznam 1 alebo zoznam 2) úplne prechádza ako v predchádzajúcom prípade, potom skopírujte celý obsah ostatných zoznamov z ukazovateľa do zoznamu výsledkov (tj zoznam 3) nasledujúcim spôsobom.
Algoritmus a pseudokód
Dva algoritmy používané pri zlúčení algoritmov sú:
- MERGE (ARR, F, M, L) je proces, ktorý predpokladá nasledujúce:
- ARR (F… .M) a ARR (M + 1… .L) sú radené zoznamy.
- Zlúči dva zoradené podzoznamy do jedného ARR (F… .L).
- SORT (ARR (), F, L) // tu F je prvý a L je posledný index poľa.
Ak (L> 1)
- Nájdite stredný bod na rozdelenie zoznamu na dve polovice:
stredná M = (F + L) / 2
- Zoraďovanie hovorov za prvú polovicu:
Volajte SORT (ARR, 1, M)
- Zoraďovanie hovorov na druhú polovicu:
Volajte SORT (ARR, M + 1, L)
- Zlúčte polovice zoradené v krokoch 2 a 3:
Volajte MERGE (ARR, L, M, R)
príklad
Urobme príklad poľa ARR (10, 6, 8, 5, 7, 3, 4). Algoritmus zlúčenia použijeme na zoradenie poľa pomocou techniky rozdelenia a dobývania. Vidíme nižšie uvedený obrázok, že pole je rekurzívne rozdelené na dve polovice, kým sa veľkosť nestane 1. Akonáhle sa veľkosť zmení na 1, zavoláme zlučovacie procesy a začneme zlučovacie zoznamy späť, až kým sa nezmení celý zoznam.
POZNÁMKA: Na obrázku nižšie sú čísla zobrazené červenou farbou v poradí, v akom sú kroky spracované na vytvorenie zoradeného poľa.
Programový kód:
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);
)
)
Výkon:
Záver - Zlúčiť algoritmy triedenia v Jave
Zlučovanie najlepších, najhorších a priemerných časových komplikácií zlúčenia je rovnaké, čo z neho robí efektívnejší algoritmus. Funguje to rýchlejšie ako iné techniky triedenia. Zlúčiť zoradenie je možné použiť na súbory ľubovoľnej veľkosti. Je vysoko paralelizovateľný vďaka použitiu metódy rozdelenia a dobytí. S cieľom rozvinúť silné základy počítačovej vedy sa odporúča dôkladne porozumieť rôznym triediacim algoritmom.
Odporúčané články
Toto je sprievodca zlúčením algoritmov triedenia v Jave. Tu uvádzame príklad implementácie algoritmov zlučovania triedenia v jave a príkladov algoritmov a pseudokódov. Môžete si tiež prečítať naše ďalšie navrhované články -
- Výber Zoradiť v Java
- Prípadové vyhlásenie v Jave
- Prístup k modifikátorom v jazyku Java
- Zlúčiť Zoradiť v JavaScripte
- Čo je to Prípad v jazyku JavaScript?
- Modifikátory prístupu v PHP
- Algoritmy rýchleho triedenia v Jave
- Kompletný sprievodca triedením v C # s príkladmi
- Funkcia triedenia v Pythone s príkladmi
- Top 6 triediaci algoritmus v JavaScripte