Introduktion till sammanslagningssorteringsalgoritmer i Java
Merge sorteringsalgoritmer är mycket viktiga inom datavetenskap. Utmatningen från sorteringen är att ordna elementen i en lista i viss ordning (antingen stigande eller fallande). Sammanfogningssortering är en av de mest effektiva sorteringsalgoritmerna som finns tillgängliga eftersom den är baserad på begreppet split och erövrar. Som namnet antyder, dela först det större problemet i små problem än att lösa de mindre problemen för att lösa det större problemet. I den här artikeln kommer vi att diskutera sammanslagningssorteringsalgoritmer i Java. Konceptuellt är Merge sort en kombination av två grundläggande algoritmer som kallas MERGE och MERGE_SORT som fungerar enligt följande:
- Dela upp den osorterade listan i n-nummer av undelistor med en artikel (n är det totala antalet element i den osorterade listan).
- Slå samman sublister upprepade gånger i sorterade underlistor tills det bara finns en sorterad lista.
Implementering av algoritmer för sorteringssortering i Java
MERGE-algoritmen är proceduren för att kombinera två sorterade listor till en sorterad lista.
Exempel: Anta att det finns två listor, dvs. lista 1 (6, 3) och lista 2 (3, 1, 9).
1. Sortera först båda listorna.
Lista 1
Lista 2
Nu kommer vi att använda en sammanslagningsteknik på den.
- Sedan skapar vi en ny lista med storlek m + n där m är antalet element i lista 1 och n är antalet element i lista 2.
Lista 3
I vårt fall m = 2 och n = 3, så m + n = 5.
- Nu har vi en tvåpekare. En första pekare som pekar på den första positionen i lista 1 och den andra pekaren som pekar på den första positionen i lista 2.
4. Sedan jämför vi värdet på båda pekarna. Pekaren med mindre värde, kopiera det elementet till lista 3 och flytta pekaren till höger om listan med mindre värde och den resulterande listan (dvs. lista 1 och lista 3).
5. Utför på samma sätt steg 4 igen och igen.
Ytterligare korsa …
OBS: Om en av listorna (dvs. lista 1 eller lista 2) blir fullständigt korsad som i ovanstående fall, kopierar du hela innehållet i andra listor från pekaren till resultatlistan (dvs. lista 3) enligt följande.
Algoritm och pseudokod
De två algoritmerna som används i sammanslagningsalgoritmen är:
- MERGE (ARR, F, M, L) är en process som antar följande:
- ARR (F… .M) och ARR (M + 1… .L) är sorterade listor.
- Sammanfogar de två sorterade underlistorna till en ARR (F… .L).
- SORT (ARR (), F, L) // här är F den första och L är det sista indexet i matrisen.
Om (L> 1)
- Hitta mittpunkten för att dela upp listan i två halvor:
mitt M = (F + L) / 2
- Call Merge Sort för första halvåret:
Ring SORT (ARR, 1, M)
- Call Merge Sort för andra halvåret:
Ring SORT (ARR, M + 1, L)
- Slå ihop halvorna sorterade i steg 2 och 3:
Ring MERGE (ARR, L, M, R)
Exempel
Låt oss ta ett exempel på en array ARR (10, 6, 8, 5, 7, 3, 4). Vi kommer att använda sammanslagningsalgoritmen för att sortera matrisen med dess Divide and Conquer-teknik. Vi kan se figuren nedan att arrayen är rekursivt uppdelad i två halvor tills storleken blir 1. När storleken blir 1, så kallar vi sammanslagningsprocesser och börjar sammanfoga listor tillbaka tills hela listan slås samman.
OBS! I figuren nedan anger siffrorna i rött i vilken ordning stegen bearbetas för att bilda den sorterade matrisen.
Programkod:
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);
)
)
Produktion:
Slutsats - Slå samman sorteringsalgoritmer i Java
Slå samman bästa, sämsta och genomsnittliga tidskomplexiteten är desamma som gör det till en effektivare algoritm. Det fungerar snabbare än andra sorteringstekniker. Sorteringssortering kan tillämpas på filer av valfri storlek. Den är mycket parallelliserbar på grund av användningen av divide-and-conquer-metoden. För att utveckla starka grunder i datavetenskap rekommenderas du att förstå grundligt olika sorteringsalgoritmer.
Rekommenderade artiklar
Detta är en guide till sammanfoga sorteringsalgoritmer i Java. Här diskuterar vi Implementation of Merge Sorting Algoritms i java och Algoritm & Pseudocode med exempel. Du kan också gå igenom våra andra föreslagna artiklar–
- Urval Sortera i Java
- Ärendemärkning i Java
- Få åtkomst till modifierare i Java
- Slå samman Sortera i JavaScript
- Vad är ärendeuttalande i JavaScript?
- Få åtkomst till modifierare i PHP
- Snabbsorteringsalgoritmer i Java
- Komplett guide till sortering i C # med exempel
- Sorteringsfunktion i Python med exempel
- Topp 6 sorteringsalgoritm i JavaScript