Ühenda sortimisalgoritmid Java-s - Merge Sordi rakendamine

• Sissejuhatus Java sortimisalgoritmide ühendamisse

Sissejuhatus Java sortimisalgoritmide ühendamisse

Ühendamise sorteerimise algoritmid on arvutiteaduses väga olulised. Sorteerimise väljund on loendi elementide järjestamine kindlasse järjekorda (kas kasvavalt või kahanevalt). Ühenda sortimine on üks tõhusamaid sorteerimisalgoritme, kuna see põhineb jagamise ja vallutamise kontseptsioonil. Nagu nimigi ütleb, jagage suurem probleem esmalt väiksemateks probleemideks kui väiksemate probleemide lahendamiseks. Selles artiklis käsitleme Java-s sorteerimise algoritmide ühendamist. Kontseptuaalselt on sorteerimise ühendamine kahe põhilise algoritmi kombinatsioon nimega MERGE ja MERGE_SORT, mis töötab järgmiselt:

1. Jagage sortimata loend n arvuks üksikute alamloendite arvuks (n on sortimata loendi elementide koguarv).
2. Ühendage alamloendid korduvalt sorteeritud alamloenditeks, kuni on ainult üks sorteeritud loend.

Ühendamisalgoritmide rakendamine Java-s

MERGE algoritm on protseduur kahe sorteeritud loendi ühendamiseks üheks sorteeritud loendiks.

Näide: Oletame, et on kaks loendit, st loend 1 (6, 3) ja loend 2 (3, 1, 9).

1. Esmalt sorteerige mõlemad loendid.

1. loetelu

2. loetelu

Nüüd rakendame selle ühendamise tehnikat.

2. Seejärel loome uue loendi suurusega m + n, kus m on 1. loendi elementide arv ja n on 2. loendi elementide arv.

3. loetelu

Meie puhul on m = 2 ja n = 3, seega m + n = 5.

3. Nüüd on meil kaks osutit. Esimene kursor osutab loendi 1 esimesele positsioonile ja teine ​​kursor loendi 2 esimesele positsioonile.

4. Seejärel võrdleme mõlema osuti väärtust. Väiksema väärtusega osuti, kopeerige see element loendisse 3 ja liigutage kursorit väiksema väärtuse ja sellest tuleneva loendi (st loend 1 ja loend 3) paremale.

5. Samamoodi toimige uuesti 4. ja 4. sammu.

Edasine liikumine …

MÄRKUS. Kui üks loenditest (st 1. või 2. loend) läbitakse täielikult, nagu ülaltoodud juhul, siis kopeerige muude loendite kogu sisu kursorilt tulemuste loendisse (st 3. loendisse) järgmiselt.

Algoritm ja pseudokood

Kaks ühendamise algoritmis kasutatavat algoritmi on järgmised:

• ÜHENDAMINE (ARR, F, M, L) on protsess, mis eeldab järgmist:

1. ARR (F… .M) ja ARR (M + 1… .L) on sorteeritud loendid.
2. Liidab kaks järjestatud alamloendit üheks ARR (F… .L).

• SORT (ARR (), F, L) // siin F on esimene ja L on massiivi viimane indeks.

Kui (L> 1)

1. Leidke keskpunkt, et jagada loend kaheks pooleks:

keskmine M = (F + L) / 2

2. Esimese poolaasta kõnede ühendamise sort:

Helista SORT (ARR, 1, M)

3. Call Merge Sort teisel poolel:

Helista SORT (ARR, M + 1, L)

4. Ühendage 2. ja 3. astmes järjestatud pooled:

Helistage MERGE (ARR, L, M, R)

Näide

Võtame näiteks massiivi ARR (10, 6, 8, 5, 7, 3, 4). Massi sortimiseks, kasutades jaotamise ja vallutamise tehnikat, kasutame liitmisalgoritmi. Alloleval joonisel näeme, et massiiv jaguneb rekursiivselt kaheks pooleks, kuni suuruseks saab 1. Kui suurus saab 1, kutsume liitmisprotsessid kokku ja alustame loendite liitmist tagasi, kuni kogu loend on ühendatud.

MÄRKUS . Alloleval joonisel tähistavad punased numbrid järjekorda, milles samme töödeldakse sorteeritud massiivi moodustamiseks.

Programmi kood:

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äljund:

Järeldus - liitmis sortimise algoritmid Java-s

Liitmise sorteerimise parim, halvim ja keskmise juhtumi ajaline keerukus on sama, mis muudab selle algoritmi tõhusamaks. See töötab kiiremini kui muud sorteerimistehnikad. Ühendamise sorteerimist saab rakendada mis tahes suurusega failidele. See on jagamise ja vallutamise meetodi kasutamise tõttu väga paralleelne. Tugevate arvutiteaduse aluste väljatöötamiseks soovitatakse teil põhjalikult mõista erinevaid sortimisalgoritme.

Soovitatavad artiklid

See on juhend Java sortimisalgoritmide ühendamiseks. Siin käsitleme näitena ühendamise sortimisalgoritmide rakendamist javas ning algoritme ja pseudokoode. Võite vaadata ka meie teisi soovitatud artikleid -

1. Valik Sorteeri Java-s
2. Juhtumi avaldus Java-s
3. Juurdepääs Java muutjatele
4. Ühenda Sorteeri JavaScriptis
5. Mis on kohtuasja avaldus JavaScriptis?
6. Juurdepääs modifikaatoritele PHP-s
7. Kiire sortimise algoritmid Java-s
8. Täielik juhend C # -s sortimise kohta koos näidetega
9. Näite abil sortimisfunktsioon Pythonis
10. Kuus parimat sortimisalgoritmi JavaScriptis