Apvienot šķirošanas algoritmu

Šajā apmācībā jūs uzzināsiet par apvienošanas kārtojumu. Jūs atradīsit arī C, C ++, Java un Python apvienošanas kārtības piemērus.

Kārtot apvienošana ir viens no populārākajiem šķirošanas algoritmiem, kas balstīts uz dalīšanas un iekarošanas algoritma principu.

Šeit problēma ir sadalīta vairākās apakšproblēmās. Katra apakšproblēma tiek atrisināta atsevišķi. Visbeidzot, apakšproblēmas tiek apvienotas, lai iegūtu galīgo risinājumu.

Apvienot Kārtot piemēru

Sadaliet un iekarojiet stratēģiju

Izmantojot sadalīšanas un iekarošanas tehniku, problēmu mēs sadalām apakšproblēmās. Kad katras apakšproblēmas risinājums ir gatavs, mēs "apvienojam" apakšproblēmu rezultātus, lai atrisinātu galveno problēmu.

Pieņemsim, ka mums bija jāšķiro masīvs A. Apakšproblēma būtu kārtot šī masīva apakšsadaļu, sākot ar indeksu p un beidzot ar indeksu r, kas apzīmēts kā A (p … r).

Dalīt
Ja q ir pusceļš starp p un r, tad apakšlīniju A (p… r) varam sadalīt divās masīvās A (p… q) un A (q + 1, r).

Iekarošana
Iekarošanas solī mēs cenšamies sakārtot gan apakškārtas A (p… q), gan A (q + 1, r). Ja mēs vēl neesam sasnieguši pamata lietu, mēs atkal sadalām abus šos apakšstarus un mēģinām tos kārtot.

Apvienot
Kad iekarošanas solis sasniedz bāzes soli un mēs iegūstam divas sakārtotas apakšrindas A (p… q) un A (q + 1, r) masīvam A (p… r), mēs apvienojam rezultātus, izveidojot sakārtotu masīvu A ( p… r) no divām sakārtotām apakšrāmīm A (p… q) un A (q + 1, r).

MergeSort algoritms

MergeSort funkcija atkārtoti sadala masīvu divās pusēs, līdz mēs sasniedzam stadiju, kurā mēs mēģinām veikt MergeSort uz 1. lieluma apakšgrupas, ti, p == r.

Pēc tam apvienošanās funkcija sāk darboties un apvieno sakārtotos masīvus lielākos masīvos, līdz viss masīvs tiek apvienots.

 MergeSort (A, p, r): ja p> r atgriež q = (p + r) / 2 apvienotSort (A, p, q) apvienotSort (A, q + 1, r) sapludināt (A, p, q, r )

Lai kārtotu visu masīvu, mums jāzvana MergeSort(A, 0, length(A)-1).

Kā parādīts zemāk esošajā attēlā, sapludināšanas šķirošanas algoritms rekursīvi sadala masīvu uz pusēm, līdz mēs sasniedzam masīva pamata gadījumu ar 1 elementu. Pēc tam sapludināšanas funkcija uzņem sakārtotos apakšmasīvus un apvieno tos, lai pakāpeniski kārtotu visu masīvu.

Apvienot kārtošanu darbībā

Sapludināšanas solis no Merge Sort

Katrs rekursīvais algoritms ir atkarīgs no bāzes gadījuma un spējas apvienot bāzes gadījumu rezultātus. Apvienošanas kārtība neatšķiras. Svarīgākā sapludināšanas šķirošanas algoritma daļa ir, jūs uzminējāt, apvienošanas solis.

Apvienošanas solis ir vienkāršas divu sakārtotu sarakstu (masīvu) apvienošanas problēmas risinājums, lai izveidotu vienu lielu sakārtotu sarakstu (masīvu).

Algoritms uztur trīs rādītājus, vienu katram no diviem masīviem un vienu galīgā sakārtotā masīva pašreizējā indeksa uzturēšanai.

Vai esam sasnieguši kāda no masīviem beigas? Nē: Salīdzināt abu masīvu pašreizējos elementus Kopēt mazāku elementu sakārtotajā masīvā Pārvietot rādītāju elementam, kas satur mazāku elementu Jā: Kopēt visus atlikušos ne-tukšā masīva elementus
Apvienot soli

Apvienošanas algoritma koda rakstīšana

Ievērojama atšķirība starp iepriekš aprakstīto sapludināšanas soli un to, ko izmantojam apvienošanas kārtošanai, ir tāda, ka apvienošanas funkciju veicam tikai secīgos apakškārtos.

Tāpēc mums ir vajadzīgs tikai masīvs, pirmā pozīcija, pirmā apakšgrupas pēdējais indekss (mēs varam aprēķināt otrā apakšgrupas pirmo indeksu) un otrā apakšgrupas pēdējais indekss.

Mūsu uzdevums ir apvienot divas apakškārtas A (p… q) un A (q + 1… r), lai izveidotu sakārtotu masīvu A (p… r). Tātad funkcijas ievadi ir A, p, q un r

Apvienošanas funkcija darbojas šādi:

  1. Izveidojiet apakšrašu L ← A(p… q)un M ← A (q + 1… r) kopijas .
  2. Izveidojiet trīs i, j un k rādītājus
    1. i uztur pašreizējo L indeksu, sākot no 1
    2. j uztur pašreizējo M indeksu, sākot no 1
    3. k saglabā pašreizējo A indeksu (p… q), sākot no p.
  3. Līdz brīdim, kad sasniedzam vai nu L, vai M, izvēlieties lielāko no L un M elementiem un novietojiet tos pareizajā pozīcijā pie A (p… q)
  4. Kad mums beigsies elementi L vai M, paņemiet atlikušos elementus un ielieciet A (p… q)

Kodā tas izskatīsies šādi:

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

Apvienot () Funkcija paskaidrota soli pa solim

Šajā funkcijā notiek daudz, tāpēc ņemsim piemēru, lai redzētu, kā tas darbotos.

Kā parasti, attēls runā tūkstoš vārdu.

Divu secīgu masīva apakšrašu apvienošana

Masīvā A (0… 5) ir divas sakārtotas apakškārtas A (0… 3) un A (4… 5). Apskatīsim, kā sapludināšanas funkcija apvienos abus masīvus.

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

1. darbība: izveidojiet sakārtotu apakšmasīvu kopijas

  // 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)
Izveidojiet apakšrašu kopijas apvienošanai

2. solis: Saglabājiet pašreizējo apakšmasīvu un galvenā masīva indeksu

  int i, j, k; i = 0; j = 0; k = p;
Uzturēt apakšgrupas un galvenā masīva kopiju indeksus

3. solis: līdz sasniegsim L vai M galu, izvēlieties lielāku starp elementiem L un M un novietojiet tos pareizajā pozīcijā pie 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++; )
Kārtotu apakšstaru atsevišķu elementu salīdzināšana, līdz mēs sasniedzam viena galu

4. solis: Kad elementi L vai M ir beigušies, paņemiet atlikušos elementus un ielieciet A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopējiet atlikušos elementus no pirmā masīva uz galveno apakšdatu 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopēt atlikušos otrā masīva elementus galvenajā apakšdarījumā

Šis solis būtu bijis vajadzīgs, ja M izmērs būtu lielāks par L.

Apvienošanas funkcijas beigās apakškopa A (p… r) tiek sakārtota.

Python, Java un C / C ++ piemēri

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

Apvienot kārtošanas sarežģītību

Laika sarežģītība

Labākā gadījuma sarežģītība: O (n * log n)

Sliktākā gadījuma sarežģītība: O (n * log n)

Vidējā gadījuma sarežģītība: O (n * log n)

Kosmosa sarežģītība

Apvienošanas šķirošanas telpas sarežģītība ir O (n).

Apvienot kārtošanas lietojumprogrammas

  • Inversiju skaitīšanas problēma
  • Ārējā šķirošana
  • E-komercijas lietojumprogrammas

Interesanti raksti...