Inleiding tot het sorteren van algoritmen in Java
Sorteeralgoritmen voor merge zijn erg belangrijk in de informatica. De output van het sorteren is om de elementen van een lijst in een bepaalde volgorde (oplopend of aflopend) te rangschikken. Sorteren samenvoegen is een van de meest efficiënte sorteeralgoritmen die beschikbaar is, omdat het gebaseerd is op het concept van verdeel en overwint. Zoals de naam al doet vermoeden, verdeel je eerst het grotere probleem in kleine problemen dan het oplossen van de kleinere problemen om het grotere probleem op te lossen. In dit artikel zullen we Merge Sorting Algorithms in Java bespreken. Conceptueel is het samenvoegen een combinatie van twee basisalgoritmen genaamd MERGE en MERGE_SORT die als volgt werkt:
- Verdeel de ongesorteerde lijst in n aantal sublijsten met één item (n is het totale aantal elementen in de ongesorteerde lijst).
- Voeg sublijsten herhaaldelijk samen in gesorteerde sublijsten totdat er slechts één gesorteerde lijst is.
Implementatie van Merge Sorting Algorithms in Java
Het MERGE-algoritme is de procedure waarbij twee gesorteerde lijsten worden gecombineerd tot één gesorteerde lijst.
Voorbeeld: stel dat er twee lijsten zijn, dwz lijst 1 (6, 3) en lijst 2 (3, 1, 9).
1. Sorteer eerst beide lijsten.
Lijst 1
Lijst 2
Nu zullen we er een samenvoegingstechniek op toepassen.
- Vervolgens maken we een nieuwe lijst met grootte m + n, waarbij m het aantal elementen in lijst 1 is en n het aantal elementen in lijst 2 is.
Lijst 3
In ons geval m = 2 en n = 3, dus m + n = 5.
- Nu hebben we een tweewijzer. Een eerste aanwijzer die naar de eerste positie van lijst 1 wijst en een tweede aanwijzer die naar de eerste positie van lijst 2 wijst.
4. Vervolgens vergelijken we de waarde van beide pointers. De aanwijzer met lagere waarde, kopieer dat element naar lijst 3 en verplaats de aanwijzer naar rechts van de lijst met kleinere waarde en de resulterende lijst (dwz lijst 1 en lijst 3).
5. Voer op dezelfde manier stap 4 steeds opnieuw uit.
Verder reizen …
OPMERKING: Als een van de lijsten (bijv. Lijst 1 of lijst 2) volledig wordt doorlopen zoals in het bovenstaande geval, kopieert u de volledige inhoud van andere lijsten als volgt naar de resultatenlijst (bijv. Lijst 3).
Algoritme & Pseudocode
De twee algoritmen die worden gebruikt in Algeheel samenvoegen zijn:
- De MERGE (ARR, F, M, L) is een proces dat het volgende veronderstelt:
- ARR (F… .M) en ARR (M + 1… .L) zijn gesorteerde lijsten.
- Voegt de twee gesorteerde sublijsten samen in één ARR (F… .L).
- SORT (ARR (), F, L) // hier is F de eerste en L is de laatste index van de array.
Als (L> 1)
- Zoek het middelste punt om de lijst in twee helften te verdelen:
middelste M = (F + L) / 2
- Oproep samenvoegen sorteren voor de eerste helft:
SORT bellen (ARR, 1, M)
- Oproep samenvoegen sorteren voor de tweede helft:
SORT bellen (ARR, M + 1, L)
- Voeg de helften samen gesorteerd in stap 2 en 3:
Bel MERGE (ARR, L, M, R)
Voorbeeld
Laten we een voorbeeld nemen van een array ARR (10, 6, 8, 5, 7, 3, 4). We zullen het merge-algoritme gebruiken om de array te sorteren met behulp van de Divide and Conquer-techniek. We kunnen de onderstaande afbeelding zien dat de array recursief in twee helften is verdeeld totdat de grootte 1 wordt. Zodra de grootte 1 wordt, roepen we samenvoegprocessen aan en beginnen we lijsten samen te voegen tot de volledige lijst is samengevoegd.
OPMERKING: In de onderstaande afbeelding geven de rode cijfers de volgorde aan waarin de stappen worden verwerkt om de gesorteerde array te vormen.
Programmacode:
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);
)
)
Output:
Conclusie - Sorteeralgoritmen samenvoegen in Java
Samenvoegen sorteer beste, slechtste en gemiddelde case tijd complexiteiten zijn hetzelfde, waardoor het een efficiënter algoritme is. Het werkt sneller dan andere sorteertechnieken. Het samenvoegen kan worden toegepast op bestanden van elke grootte. Het is in hoge mate parallelliseerbaar door het gebruik van de verdeel-en-verover-methode. Om sterke basisprincipes in de informatica te ontwikkelen, wordt u geadviseerd om verschillende sorteeralgoritmen grondig te begrijpen.
Aanbevolen artikelen
Dit is een handleiding voor het sorteren van algoritmen op Java. Hier bespreken we de implementatie van Merge Sorting Algorithms in Java en Algorithm & Pseudocode met voorbeeld. U kunt ook onze andere voorgestelde artikelen doornemen–
- Selectie sorteren op Java
- Case Statement in Java
- Toegang tot modificaties in Java
- Samenvoegen Sorteren in JavaScript
- Wat is Case Statement in JavaScript?
- Toegang tot modificaties in PHP
- Snel sorteren algoritmen in Java
- Volledige gids voor sorteren in C # met voorbeelden
- Sorteerfunctie in Python met voorbeelden
- Top 6 sorteeralgoritme in JavaScript