Yhdistä lajittelualgoritmi

Tässä opetusohjelmassa opit yhdistämislajittelusta. Löydät myös toimivia esimerkkejä yhdistämisen lajittelusta C, C ++, Java ja Python.

Yhdistä lajittelu on yksi suosituimmista lajittelualgoritmeista, joka perustuu jakamis- ja valloitusalgoritmin periaatteeseen.

Tässä ongelma on jaettu useisiin alaongelmiin. Jokainen alaongelma ratkaistaan ​​erikseen. Lopuksi alaongelmat yhdistetään lopullisen ratkaisun muodostamiseksi.

Yhdistä lajitteluesimerkki

Jaa ja valloita strategia

Käyttämällä hajoita ja hallitse tekniikka, meidän jakaa ongelma tulee aliongelmat. Kun ratkaisu kullekin osaongelmalle on valmis, 'yhdistämme' alaongelmien tulokset pääongelman ratkaisemiseksi.

Oletetaan, että meidän oli lajiteltava taulukko A. Aliongelma olisi lajitella tämän matriisin alaosa indeksistä p alkaen ja päättyen hakemistoon r, jota merkitään nimellä A (p… r).

Jakaa
Jos q on puolipiste p: n ja r: n välillä, voimme jakaa alapiirin A (p… r) kahteen ryhmään A (p… q) ja A (q + 1, r).

Valloitus
Valloitusvaiheessa yritämme lajitella sekä alialat A (p… q) että A (q + 1, r). Jos emme ole vielä saavuttaneet perustapausta, jaamme molemmat nämä alirivit uudelleen ja yritämme lajitella ne.

Yhdistä
Kun valloitusvaihe saavuttaa perusvaiheen ja saamme kaksi lajiteltua aliriviä A (p… q) ja A (q + 1, r) taulukolle A (p… r), yhdistämme tulokset luomalla lajiteltu taulukko A (p p… r) kahdesta lajitellusta alirivistä A (p… q) ja A (q + 1, r).

MergeSort-algoritmi

MergeSort-toiminto jakaa matriisin toistuvasti kahteen puolikkaaseen, kunnes saavutamme vaiheen, jossa yritämme suorittaa MergeSort-sovelluksen kokoalueella 1 eli p == r.

Sen jälkeen yhdistämistoiminto tulee esiin ja yhdistää lajitellut taulukot suurempiin ryhmiin, kunnes koko taulukko on yhdistetty.

 MergeSort (A, p, r): jos p> r palaa q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) yhdistää (A, p, q, r )

Koko taulukon lajittelemiseksi meidän on soitettava MergeSort(A, 0, length(A)-1).

Kuten alla olevassa kuvassa on esitetty, yhdistämisen lajittelualgoritmi jakaa matriisin rekursiivisesti puolikkaisiin, kunnes saavutamme matriisin perustapauksen yhdellä elementillä. Tämän jälkeen yhdistämistoiminto poimii lajitellut alaryhmät ja yhdistää ne koko matriisin lajittelemiseksi asteittain.

Yhdistä lajittelu toiminnassa

Yhdistämisen Vaihe lomituslajittelu

Jokainen rekursiivinen algoritmi riippuu perustapauksesta ja kyvystä yhdistää perustapausten tulokset. Yhdistä lajittelu ei ole erilainen. Tärkein osa yhdistämisen lajittelualgoritmia on, arvasit, yhdistämisvaihe.

Yhdistämisvaihe on ratkaisu yksinkertaiseen ongelmaan, joka koskee kahden lajitellun luettelon (taulukot) yhdistämistä yhden suuren lajitellun luettelon (taulukon) muodostamiseksi.

Algoritmi ylläpitää kolmea osoittinta, yhden kullekin kahdelle ryhmälle ja toisen lopullisen lajitellun taulukon nykyisen indeksin ylläpitämiseksi.

Olemmeko saavuttaneet jonkun taulukon loppua? Ei: Vertaa molempien matriisien nykyisiä elementtejä Kopioi pienempi elementti lajiteltuun matriisiin Siirrä pienempää elementtiä sisältävän elementin osoitin Kyllä: Kopioi kaikki muut kuin tyhjät matriisit
Yhdistä vaihe

Yhdistämisalgoritmin koodin kirjoittaminen

Huomattava ero edellä kuvatun yhdistämisvaiheen ja yhdistämislajittelun välillä on se, että suoritamme yhdistämistoiminnon vain peräkkäisillä alaryhmillä.

Siksi tarvitsemme vain matriisin, ensimmäisen sijainnin, ensimmäisen osa-alueen viimeisen indeksin (voimme laskea toisen osa-alueen ensimmäisen indeksin) ja toisen osa-alueen viimeisen indeksin.

Tehtävämme on yhdistää kaksi alikaistaa A (p… q) ja A (q + 1… r) lajitellun taulukon A (p… r) luomiseksi. Joten funktion tulot ovat A, p, q ja r

Yhdistämistoiminto toimii seuraavasti:

  1. Luo kopiot alikentistä L ← A(p… q)ja M ← A (q + 1… r).
  2. Luo kolme osoitinta i, j ja k
    1. i säilyttää nykyisen L-indeksin alkaen 1: stä
    2. j ylläpitää M: n nykyisen indeksin alkaen 1: stä
    3. k ylläpitää nykyisen A-indeksin (p… q) alkaen p: stä.
  3. Kunnes saavutetaan joko L: n tai M: n loppu, valitse suurempi L: n ja M: n elementtien joukosta ja aseta ne oikeaan kohtaan A (p… q)
  4. Kun elementit loppuvat joko L: ssä tai M: ssä, poimi jäljellä olevat elementit ja aseta A (p… q)

Koodissa tämä näyttäisi tältä:

 // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) )

Yhdistä () -toiminto selitetty vaihe vaiheelta

Tässä toiminnossa tapahtuu paljon, joten ottakaamme esimerkki nähdäksesi, miten tämä toimisi.

Kuten tavallista, kuva puhuu tuhat sanaa.

Kahden peräkkäisen matriisin alialueen yhdistäminen

Taulukko A (0… 5) sisältää kaksi lajiteltua aliriviä A (0… 3) ja A (4… 5). Katsotaanpa, kuinka yhdistämistoiminto yhdistää kaksi taulukkoa.

 void merge(int arr(), int p, int q, int r) ( // Here, p = 0, q = 4, r = 6 (size of array)

Vaihe 1: Luo lajiteltavat aliryhmien kopiot

  // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1 = 3 - 0 + 1 = 4; int n2 = r - q = 5 - 3 = 2; int L(4), M(2); for (int i = 0; i < 4; i++) L(i) = arr(p + i); // L(0,1,2,3) = A(0,1,2,3) = (1,5,10,12) for (int j = 0; j < 2; j++) M(j) = arr(q + 1 + j); // M(0,1,2,3) = A(4,5) = (6,9)
Luo kopioita alakentistä yhdistämistä varten

Vaihe 2: Säilytä alaryhmien ja päätaulukon nykyinen hakemisto

  int i, j, k; i = 0; j = 0; k = p;
Säilytä alaryhmän ja päätaulukon kopioiden indeksit

Vaihe 3: kunnes saavutamme joko L: n tai M: n loppuun, valitse suurempi elementtien L ja M joukosta ja aseta ne oikeaan kohtaan kohtaan A (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Lajiteltujen alikaavioiden yksittäisten elementtien vertaaminen, kunnes saavutamme yhden osan

Vaihe 4: Kun elementit loppuvat joko L: stä tai M: stä, poimi jäljellä olevat elementit ja aseta A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopioi jäljellä olevat elementit ensimmäisestä taulukosta pääalaryhmään 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopioi toisen matriisin jäljellä olevat elementit pääalikenttään

Tätä vaihetta olisi tarvittu, jos M: n koko olisi suurempi kuin L.

Yhdistämistoiminnon lopussa osa-alue A (p… r) lajitellaan.

Python-, Java- ja C / C ++ -esimerkkejä

Python Java C C ++ 
 # MergeSort in Python def mergeSort(array): if len(array)> 1: # r is the point where the array is divided into two subarrays r = len(array)//2 L = array(:r) M = array(r:) # Sort the two halves mergeSort(L) mergeSort(M) i = j = k = 0 # Until we reach either end of either L or M, pick larger among # elements L and M and place them in the correct position at A(p… r) while i < len(L) and j < len(M): if L(i) < M(j): array(k) = L(i) i += 1 else: array(k) = M(j) j += 1 k += 1 # When we run out of elements in either L or M, # pick up the remaining elements and put in A(p… r) while i < len(L): array(k) = L(i) i += 1 k += 1 while j < len(M): array(k) = M(j) j += 1 k += 1 # Print the array def printList(array): for i in range(len(array)): print(array(i), end=" ") print() # Driver program if __name__ == '__main__': array = (6, 5, 12, 10, 9, 1) mergeSort(array) print("Sorted array is: ") printList(array) 
 // Merge sort in Java class MergeSort ( // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L() = new int(n1); int M() = new int(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = (l + r) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver program public static void main(String args()) ( int arr() = ( 6, 5, 12, 10, 9, 1 ); MergeSort ob = new MergeSort(); ob.mergeSort(arr, 0, arr.length - 1); System.out.println("Sorted array:"); printArray(arr); ) )
 // Merge sort in C #include // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) printf("%d ", arr(i)); printf(""); ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); printf("Sorted array: "); printArray(arr, size); )
 // Merge sort in C++ #include using namespace std; // Merge two subarrays L and M into arr void merge(int arr(), int p, int q, int r) ( // Create L ← A(p… q) and M ← A(q+1… r) int n1 = q - p + 1; int n2 = r - q; int L(n1), M(n2); for (int i = 0; i < n1; i++) L(i) = arr(p + i); for (int j = 0; j < n2; j++) M(j) = arr(q + 1 + j); // Maintain current index of sub-arrays and main array int i, j, k; i = 0; j = 0; k = p; // Until we reach either end of either L or M, pick larger among // elements L and M and place them in the correct position at A(p… r) while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; ) // When we run out of elements in either L or M, // pick up the remaining elements and put in A(p… r) while (i < n1) ( arr(k) = L(i); i++; k++; ) while (j < n2) ( arr(k) = M(j); j++; k++; ) ) // Divide the array into two subarrays, sort them and merge them void mergeSort(int arr(), int l, int r) ( if (l < r) ( // m is the point where the array is divided into two subarrays int m = l + (r - l) / 2; mergeSort(arr, l, m); mergeSort(arr, m + 1, r); // Merge the sorted subarrays merge(arr, l, m, r); ) ) // Print the array void printArray(int arr(), int size) ( for (int i = 0; i < size; i++) cout << arr(i) << " "; cout << endl; ) // Driver program int main() ( int arr() = (6, 5, 12, 10, 9, 1); int size = sizeof(arr) / sizeof(arr(0)); mergeSort(arr, 0, size - 1); cout << "Sorted array: "; printArray(arr, size); return 0; )

Yhdistä lajittelun monimutkaisuus

Ajan monimutkaisuus

Parhaan tapauksen monimutkaisuus: O (n * log n)

Pahimman tapauksen monimutkaisuus: O (n * log n)

Keskimääräinen tapauksen monimutkaisuus: O (n * log n)

Avaruuden monimutkaisuus

Yhdistämislajin avaruuden monimutkaisuus on O (n).

Yhdistä lajittelusovellukset

  • Kääntymismäärän ongelma
  • Ulkoinen lajittelu
  • Verkkokaupan sovellukset

Mielenkiintoisia artikkeleita...