Johdanto yhdistelmälajittelualgoritmeihin Java
Yhdistämislajittelualgoritmit ovat erittäin tärkeitä tietotekniikassa. Lajittelun lähtökohtana on järjestää luettelon elementit tiettyyn järjestykseen (joko nousevaan tai laskevaan). Yhdistämislajittelu on yksi tehokkaimmista käytettävissä olevista lajittelualgoritmeista, koska se perustuu jakamisen ja valloituksen käsitteeseen. Kuten nimestä voi päätellä, jaa iso ongelma ensin pieniin ongelmiin kuin ratkaise pienempiin ongelmiin suuremman ongelman ratkaisemiseksi. Tässä artikkelissa käsittelemme Yhdistämislajittelualgoritmeja Java-sovelluksessa. Konseptuaalisesti yhdistämislajittelu on kahden perusalgoritmin, nimeltään MERGE ja MERGE_SORT, yhdistelmä, joka toimii seuraavasti:
- Jaa lajittelematon luettelo n määrään yksikohtaisia alaluetteloita (n on lajittelemattoman luettelon elementtien kokonaismäärä).
- Yhdistä alaluettelot toistuvasti lajiteltuihin alaluetteloihin, kunnes lajiteltua luetteloa on vain yksi.
Yhdistämislajittelualgoritmien toteutus Java-järjestelmässä
MERGE-algoritmi on menettely, jolla kaksi lajiteltua luetteloa yhdistetään yhdeksi lajiteltuksi luetteloksi.
Esimerkki: Oletetaan, että on kaksi luetteloa, ts. Lista 1 (6, 3) ja Lista 2 (3, 1, 9).
1. Lajittele ensin molemmat luettelot.
Luettelo 1
Luettelo 2
Nyt käytämme siihen sulauttamistekniikkaa.
- Sitten luomme uuden luettelon koon m + n, missä m on luettelossa 1 olevien elementtien lukumäärä ja n on luettelossa 2 olevien elementtien lukumäärä.
Luettelo 3
Meidän tapauksessamme m = 2 ja n = 3, joten m + n = 5.
- Nyt meillä on kaksi osoitinta. Ensimmäinen osoitin luettelon 1 ensimmäiseen sijaintiin ja toinen osoitin luettelon 2 ensimmäiseen kohtaan.
4. Sitten vertaamme molempien osoittimien arvoa. Pienemmällä arvolla oleva osoitin, kopioi tämä elementti luetteloon 3 ja siirrä osoitin oikealla puolelle luetteloa, jolla on pienempi arvo ja tulosluettelo (eli luettelo 1 ja luettelo 3).
5. Suorita samalla tavalla vaihe 4 uudelleen ja uudelleen.
Edelleen liikkuminen …
HUOMAUTUS: Jos yksi luetteloista (eli luettelo 1 tai luettelo 2) kulkee kokonaan, kuten edellisessä tapauksessa, kopioi muiden luetteloiden koko sisältö osoittimesta tulosluetteloon (eli luettelo 3) seuraavasti.
Algoritmi ja pseudokoodi
Yhdistämisalgoritmissa käytetyt kaksi algoritmia ovat:
- Yhdistäminen (ARR, F, M, L) on prosessi, joka edellyttää seuraavaa:
- ARR (F… .M) ja ARR (M + 1… .L) ovat lajiteltuja luetteloita.
- Yhdistää kaksi lajiteltua alaluetteloa yhdeksi ARR (F… .L).
- SORT (ARR (), F, L) // tässä F on taulukon ensimmäinen ja L on taulukon viimeinen hakemisto.
Jos (L> 1)
- Löydä keskipiste jakamalla luettelo kahteen puolikkaaseen:
keskimmäinen M = (F + L) / 2
- Call Merge Sort ensimmäisen vuosipuoliskon aikana:
Soita SORT (ARR, 1, M)
- Call Merge Sort toiselle puoliskolle:
Soita SORT (ARR, M + 1, L)
- Yhdistä vaiheissa 2 ja 3 lajitellut puolikkaat:
Soita MERGE (ARR, L, M, R)
esimerkki
Otetaanpa esimerkki taulukosta ARR (10, 6, 8, 5, 7, 3, 4). Käytämme yhdistämisalgoritmia lajittelemaan taulukon sen Divide and Conquer -tekniikan avulla. Alla olevasta kuvasta nähdään, että taulukko on jaettu rekursiivisesti kahteen puolikkaaseen, kunnes kokoksi tulee 1. Kun kokoksi tulee 1, kutsumme yhdistämisprosesseja ja aloitamme yhdistämisluettelot takaisin, kunnes koko luettelo on sulautettu.
HUOMAUTUS: Oheisessa kuvassa punaisella näkyvät numerot osoittavat vaiheiden käsittelyjärjestyksen lajitellun taulukon muodostamiseksi.
Ohjelman koodi:
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);
)
)
lähtö:
Johtopäätös - Yhdistä lajittelualgoritmit Java-sovellukseen
Yhdistämislajikkeiden parhaat, pahimmat ja keskimääräiset tapaukset ovat samat, mikä tekee siitä tehokkaamman algoritmin. Se toimii nopeammin kuin muut lajittelutekniikat. Yhdistämislajittelua voidaan soveltaa minkä tahansa kokoisiin tiedostoihin. Se on erittäin rinnakkaistettava, koska käytetään "jaa ja vallitse" -menetelmää. Vahvien tietotekniikan perusteiden kehittämiseksi kehotetaan ymmärtämään perusteellisesti erilaiset lajittelualgoritmit.
Suositellut artikkelit
Tämä on opas yhdistämislajittelualgoritmeihin Java-sovelluksessa. Tässä keskustellaan yhdistämislajittelualgoritmien toteuttamisesta Java- ja Algorithm & Pseudocode-sovelluksissa esimerkillä. Voit myös käydä läpi muiden ehdottamiemme artikkeleidemme -
- Valinta Lajittele Java
- Tapauslause Java
- Käytä Java-muokkaajia
- Yhdistä Lajittele JavaScript
- Mikä on oikeuskäytäntö JavaScriptissä?
- Pääsy muokkaimet PHP
- Pikalajittelualgoritmit Java-sovelluksessa
- Täydellinen opas lajitteluun C # -merkinnällä esimerkkeinä
- Järjestämistoiminto Pythonissa esimerkkien avulla
- Kuusi suosituinta lajittelualgoritmia JavaScriptissä