Egyesítés rendezési algoritmus

Ebben az oktatóanyagban megismerheti az egyesítés rendezését. A C, C ++, a Java és a Python egyesítésének működő példáit is megtalálja.

A Rendezés egyesítése az egyik legnépszerűbb rendezési algoritmus, amely a Divide and Conquer Algorithm elvén alapszik.

Itt egy probléma több részproblémára oszlik. Minden részprobléma egyenként van megoldva. Végül a részproblémákat kombinálva alkotják a végső megoldást.

Merge Sort példa

Divide and Conquer Strategy

A Divide and Conquer technikával a problémát részproblémákra osztjuk. Amikor az egyes részproblémák megoldása készen áll, a főprobléma megoldása érdekében „összekapcsoljuk” az alproblémák eredményeit.

Tegyük fel, hogy egy A tömböt kellett rendeznünk. Egy részprobléma az lenne, ha ennek a tömbnek egy alszakaszát rendezni kezdjük p indexről és r indexre végzünk, A-nak (p… r) jelöljük.

Osztás
Ha q a félútpont p és r között, akkor az A (p… r) részrajzot két A (p… q) és A (q + 1, r) tömbre oszthatjuk.

Conquer
A Conquer lépésben, igyekszünk rendezni mind a almátrixszá A (p … q) és az A (q + 1, R). Ha még nem jutottunk el az alapesetig, ismét felosztjuk mindkét alsávot, és megpróbáljuk rendezni őket.

Összevonás
Amikor a hódítási lépés eléri az alaplépést, és két rendezett A (p… q) és A (q + 1, r) részsávot kapunk az A tömbhöz (p… r), akkor az eredményeket egyesítjük egy rendezett A tömb létrehozásával ( p… r) két rendezett A (p… q) és A (q + 1, r) részsávból.

A MergeSort algoritmus

A MergeSort függvény ismételten két részre osztja a tömböt, amíg el nem érünk egy olyan szakaszt, ahol megpróbáljuk végrehajtani a MergeSort-ot egy 1-es méretű alrészen, azaz p == r.

Ezt követően az egyesítés függvény lép működésbe, és a rendezett tömböket nagyobb tömbökbe egyesíti, amíg az egész tömböt össze nem olvasztják.

 MergeSort (A, p, r): ha p> r visszatér q = (p + r) / 2 egyesítésSort (A, p, q) egyesítésSort (A, q + 1, r) egyesítés (A, p, q, r )

Egy teljes tömb rendezéséhez hívnunk kell MergeSort(A, 0, length(A)-1).

Amint az alábbi képen látható, az egyesítés rendezése algoritmus rekurzívan osztja fel a tömböt felekre, amíg el nem érjük a tömb alapesetét 1 elemmel. Ezt követően az egyesítés függvény felveszi a rendezett rész tömböket, és egyesíti őket, hogy fokozatosan rendezze az egész tömböt.

A rendezés egyesítése műveletben

Az egyesítési lépés Merge Küld

Minden rekurzív algoritmus függ egy alapesettől és az alapesetek eredményeinek kombinálásának képességétől. A Merge sort nem különbözik. Az egyesítés rendezése algoritmus legfontosabb része az, hogy kitalálta, egyesítés lépés.

Az egyesítési lépés megoldást kínál arra az egyszerű problémára, hogy két rendezett listát (tömböt) egy nagy rendezett lista (tömb) összeállításához egyesít.

Az algoritmus három mutatót tart fenn, egyet a két tömb mindegyikéhez, egyet pedig a végső rendezett tömb aktuális indexének fenntartásához.

Megérkeztünk valamelyik tömb végéhez? Nem: Összehasonlítja mindkét tömb aktuális elemeit Kisebb elem másolása rendezett tömbbe A kisebb elemet tartalmazó elem mutatójának mozgatása Igen: A nem üres tömb összes többi elemének másolása
Egyesítési lépés

Az egyesítési algoritmus kódjának megírása

Észrevehető különbség a fent leírt egyesítési lépés és az egyesítés rendezéséhez használt lépés között az, hogy az egyesítés funkciót csak egymást követő résztömbökön hajtjuk végre.

Ezért van szükségünk csak a tömbre, az első pozícióra, az első részrajz utolsó indexére (kiszámíthatjuk a második részrajz első indexét) és a második részrajz utolsó indexére.

Feladatunk két A (p… q) és A (q + 1… r) részsáv egyesítése egy rendezett A (p… r) tömb létrehozásához. Tehát a függvény bemenete A, p, q és r

Az egyesítés funkció a következőképpen működik:

  1. Készítsen másolatokat az alsávokról L ← A(p… q)és M ← A (q + 1… r).
  2. Hozzon létre három i, j és k mutatót
    1. i fenntartja az L aktuális indexét, kezdve 1-től
    2. j fenntartja az M aktuális indexét, kezdve 1-től
    3. k fenntartja az A (p… q) aktuális indexét, p-től kezdve.
  3. Amíg el nem érjük az L vagy az M végét, válasszuk ki a nagyobbat az L és M elemek közül, és helyezzük őket a megfelelő helyzetbe A-nál (p… q)
  4. Ha L vagy M elemből kifogynak az elemek, vegye fel a többi elemet, és tegye A-ba (p… q)

Kódban ez így néz ki:

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

Merge () Funkció lépésről lépésre elmagyarázva

Sok minden történik ebben a funkcióban, ezért vegyünk egy példát, hogy megnézzük, hogyan működne ez.

Szokás szerint egy kép ezer szót szól.

Két egymást követő tömb alsáv egyesítése

Az A tömb (0… 5) két rendezett A (0… 3) és A (4… 5) részsávot tartalmaz. Lássuk, hogyan egyesíti az egyesítés függvény a két tömböt.

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

1. lépés: Készítsen másodlagos másolatokat a rendezésre szánt résztömbökről

  // 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)
Készítsen másolatokat az alsávokról az egyesítéshez

2. lépés: Az altömbök és a fő tömb aktuális indexének fenntartása

  int i, j, k; i = 0; j = 0; k = p;
Tartsa fenn az altömb és a fő tömb másolatainak indexeit

3. lépés: Amíg el nem érjük az L vagy az M végét, válasszon nagyobbat az L és M elemek közül, és helyezze őket a megfelelő helyzetbe A-nál (p… r)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
A rendezett részsávok egyes elemeinek összehasonlítása, amíg el nem érjük az egyik végét

4. lépés: Ha az L vagy az M elemből kifogynak az elemek, vegye fel a fennmaradó elemeket, és tegye A-ba (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Másolja az első tömbből a fennmaradó elemeket a fő alsávba 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Másolja a második tömb fennmaradó elemeit a fő részterületre

Erre a lépésre lett volna szükség, ha az M mérete nagyobb, mint L.

Az egyesítési függvény végén az A (p… r) részrajz rendeződik.

Példák Python, Java és C / C ++

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

Összevonás rendezési komplexitás

Az idő komplexitása

Legjobb eset komplexitás: O (n * log n)

Legrosszabb eset komplexitás: O (n * log n)

Átlagos bonyolultság: O (n * log n)

Tér komplexitás

Az összevonási rend térbeli összetettsége O (n).

Egyesítse az alkalmazások rendezését

  • Inverziószám-probléma
  • Külső rendezés
  • E-kereskedelmi alkalmazások

érdekes cikkek...