Sujungti rūšiavimo algoritmą

Šioje pamokoje sužinosite apie suliejimo rūšiavimą. Taip pat rasite veikiančių C, C ++, Java ir Python sujungimo rūšiavimo pavyzdžių.

„Merge Sort“ yra vienas iš populiariausių rūšiavimo algoritmų, pagrįstas „Skaldyti ir užkariauti“ algoritmo principu.

Čia problema yra suskirstyta į kelias subproblemas. Kiekviena subproblema sprendžiama atskirai. Galiausiai subproblemos sujungiamos ir sudaromas galutinis sprendimas.

Sujungti rūšiavimo pavyzdį

Skaldyk ir užkariauk strategiją

Naudodamiesi „ Divide and Conquer“ technika, problemą skirstome į papročius. Kai kiekvieno subproblemos sprendimas bus paruoštas, mes „sujungsime“ subproblemų rezultatus, kad išspręstume pagrindinę problemą.

Tarkime, kad mes turėjome surūšiuoti masyvą A. Tarpinis dalykas būtų surūšiuoti šios masyvo poskyrį, prasidedantį indeksu p ir baigiant indeksu r, žymimą kaip A (p … r).

Padalinti
Jei q yra pusiaukelė tarp p ir r, tada papunktį A (p… r) galime padalyti į dvi masyvas A (p… q) ir A (q + 1, r).

Užkariauti
Užkariavimo etape bandome surūšiuoti ir poaibius A (p… q), ir A (q + 1, r). Jei dar nepasiekėme pagrindinio atvejo, dar kartą padalijame abu šiuos posūkius ir bandome juos rūšiuoti.

Sujungti
Kai užkariavimo žingsnis pasiekia pagrindinį žingsnį ir gauname du išrūšiuotus poaibius A (p… q) ir A (q + 1, r) masyvui A (p… r), rezultatus sujungiame sukurdami rūšiuojamą masyvą A ( p… r) iš dviejų išrūšiuotų pogrindžių A (p… q) ir A (q + 1, r).

„MergeSort“ algoritmas

„MergeSort“ funkcija pakartotinai dalija masyvą į dvi puses, kol pasieksime etapą, kai bandysime atlikti „MergeSort“ 1 dydžio padalinyje, ty p == r.

Po to pradeda veikti suliejimo funkcija ir sujungia surūšiuotus masyvus į didesnius masyvus, kol visas masyvas bus sujungtas.

 MergeSort (A, p, r): jei p> r grąžina q = (p + r) / 2 sulietiSort (A, p, q) sulietiSort (A, q + 1, r) sujungti )

Norėdami surūšiuoti visą masyvą, turime paskambinti MergeSort(A, 0, length(A)-1).

Kaip parodyta paveikslėlyje žemiau, suliejimo rūšiavimo algoritmas rekursyviai padalija masyvą į puses, kol pasieksime pagrindinį masyvo atvejį su 1 elementu. Po to sujungimo funkcija surenka išrūšiuotus dalinius masyvus ir sujungia juos, kad palaipsniui rūšiuotų visą masyvą.

Sujungti rūšiavimą

Suliejimo Žingsnis Merge Rūšiuoti

Kiekvienas rekursinis algoritmas priklauso nuo bazinio atvejo ir sugebėjimo sujungti bazinių atvejų rezultatus. Sujungti rūšis nesiskiria. Svarbiausia sujungimo rūšiavimo algoritmo dalis yra, jūs atspėjote, sujungimo žingsnis.

Sujungimo žingsnis yra paprastos problemos - dviejų surūšiuotų sąrašų (masyvų) sujungimo - vieno didelio surūšiuoto sąrašo (masyvo) sudarymo problemos sprendimas.

Algoritmas palaiko tris rodykles, po vieną kiekvienam iš dviejų masyvų, o kitą - dabartiniam galutinio išrūšiuoto masyvo indeksui palaikyti.

Ar mes pasiekėme bet kurio masyvo pabaigą? Ne: Palyginkite esamus abiejų masyvų elementus. Kopijuokite mažesnį elementą į rūšiuojamą masyvą Perkelkite elemento, kuriame yra mažesnis elementas, žymeklį Taip: nukopijuokite visus likusius ne tuščio masyvo elementus
Sujungti žingsnį

Sujungimo algoritmo kodo rašymas

Pastebimas skirtumas tarp aukščiau aprašyto sujungimo etapo ir to, kurį naudojame suliejimo rūšiavimui, yra tai, kad sujungimo funkciją atliekame tik iš eilės esančiuose masyvuose.

Štai kodėl mums reikia tik masyvo, pirmosios padėties, paskutinio pirmojo poskyrio indekso (galime apskaičiuoti antrojo poskyrio pirmąjį indeksą) ir paskutiniojo antrojo poskyrio rodiklio.

Mūsų užduotis yra sujungti du pogrindžius A (p… q) ir A (q + 1… r), kad būtų sukurtas rūšiuojamas masyvas A (p… r). Taigi funkcijos įvestys yra A, p, q ir r

Sujungimo funkcija veikia taip:

  1. Sukurkite papilčių L ← A(p… q)ir M ← A (q + 1… r) kopijas .
  2. Sukurkite tris rodykles i, j ir k
    1. i palaiko dabartinį L indeksą, pradedant nuo 1
    2. j palaiko dabartinį M indeksą nuo 1
    3. k palaiko dabartinį A indeksą (p… q), pradedant p.
  3. Kol nepasieksime L arba M pabaigos, pasirinkite didesnį iš L ir M elementų ir padėkite juos į teisingą padėtį A (p… q)
  4. Kai baigsis elementai L arba M, pasiimkite likusius elementus ir įdėkite A (p… q)

Kode tai atrodytų taip:

 // 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++; ) )

Sujungti () Funkcija paaiškinta žingsnis po žingsnio

Daug kas vyksta šioje funkcijoje, todėl paimkime pavyzdį, kad pamatytume, kaip tai veiktų.

Kaip įprasta, paveikslėlyje kalbama tūkstantį žodžių.

Sujungiami du vienas po kito einantys masyvo pogrindžiai

Masyve A (0… 5) yra du išrūšiuoti poaibiai A (0… 3) ir A (4… 5). Pažiūrėkime, kaip sujungimo funkcija sujungs du masyvus.

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

1 veiksmas: sukurkite pasikartojančių subrijų kopijas, kurios bus rūšiuojamos

  // 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)
Sukurkite subdėklų kopijas sujungimui

2 žingsnis: palaikykite dabartinį antrinių ir pagrindinių masyvų indeksą

  int i, j, k; i = 0; j = 0; k = p;
Palaikykite antrinio ir pagrindinio masyvo kopijų rodiklius

3 žingsnis: kol pasieksime L arba M pabaigą, tarp elementų L ir M pasirinkite didesnį ir padėkite juos į teisingą padėtį ties 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++; )
Lyginant atskirus surūšiuotų dalelių elementus, kol pasieksime jų pabaigą

4 žingsnis: Kai baigsis elementai L arba M, pasiimkite likusius elementus ir įdėkite A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Nukopijuokite likusius elementus iš pirmojo masyvo į pagrindinį skyrių 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Nukopijuokite likusius antrojo masyvo elementus į pagrindinį skyrių

Šis žingsnis būtų reikalingas, jei M dydis būtų didesnis nei L.

Sujungimo funkcijos pabaigoje sutvarkomas poskyris A (p … r).

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

„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; )

Sujungti rūšiavimo sudėtingumą

Laiko kompleksiškumas

Geriausio atvejo sudėtingumas: O (n * log n)

Blogiausio atvejo sudėtingumas: O (n * log n)

Vidutinis atvejo sudėtingumas: O (n * log n)

Erdvės sudėtingumas

Sujungimo rūšiavimo erdvės sudėtingumas yra O (n).

Sujungti rūšiuoti programas

  • Inversijų skaičiavimo problema
  • Išorinis rūšiavimas
  • Elektroninės prekybos programos

Įdomios straipsniai...