Ühenda sortimisalgoritm

Selles õpetuses saate teada ühendamise sortimise kohta. Samuti leiate toimivaid näiteid ühendamissorteerimise C, C ++, Java ja Pythoni kohta.

Sorteerimise liitmine on üks populaarsemaid sorteerimisalgoritme, mis põhineb jagamise ja vallutamise algoritmi põhimõttel.

Siin on probleem jagatud mitmeks alamprobleemiks. Iga alamprobleem lahendatakse individuaalselt. Lõpuks ühendatakse alamprobleemid lõpliku lahenduse saamiseks.

Ühenda Sordi näide

Jaga ja võida strateegiat

Jagamise ja vallutamise tehnikat kasutades jagame probleemi alamprobleemideks. Kui iga alamprobleemi lahendus on valmis, ühendame põhiprobleemi lahendamiseks alamprobleemide tulemused.

Oletame, et pidime sorteerima massiivi A. Alamprobleemiks on selle massiivi alamjaotuse sortimine algusega indeks p ja lõpeb indeksiga r, mida tähistatakse kui A (p… r).

Jaga
Kui q on p ja r vaheline poolpunkt, siis saame alamkaardi A (p… r) jagada kaheks massiiviks A (p… q) ja A (q + 1, r).

Conquer
In vallutada sammuna püüame järjestada nii alamkiipidele A (p … q) ja A (q + 1, r). Kui baasjuhtumini pole veel jõutud, jagame mõlemad alamkihid uuesti ja proovime neid sortida.

Kombineeri
Kui alistamisetapp jõuab baassammuni ja saame massiivi A (p… r) jaoks kaks järjestatud alamkaarti A (p… q) ja A (q + 1, r), ühendame tulemused, luues sorteeritud massiivi A ( p… r) kahest sorteeritud alamsaarest A (p… q) ja A (q + 1, r).

MergeSorti algoritm

Funktsioon MergeSort jagab massiivi korduvalt kaheks pooleks, kuni jõuame staadiumisse, kus proovime MergeSorti läbi viia suurusega 1 alamdiagrammil, st p == r.

Pärast seda tuleb mängu ühendamisfunktsioon ja kombineeritakse sorteeritud massiivid suuremateks massiivideks, kuni kogu massiiv on ühendatud.

 MergeSort (A, p, r): kui p> r tagastab q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) ühendab (A, p, q, r )

Terve massiivi sorteerimiseks peame helistama MergeSort(A, 0, length(A)-1).

Nagu on näidatud alloleval pildil, jagab ühendamise sortimise algoritm massiiv rekursiivselt pooleks, kuni jõuame 1 elemendiga massiivi alusjuhtumini. Pärast seda võtab ühendamisfunktsioon kokku järjestatud alammassiivid ja liidab need kogu massiivi järkjärguliseks sorteerimiseks.

Ühenda sortimine toimingus

Ühendamise Step Mestimissortimine

Iga rekursiivne algoritm sõltub baasjuhtumist ja võimest ühendada baasjuhtumite tulemused. Ühenda sortimine ei erine. Ühendamise sortimise algoritmi kõige olulisem osa on, nagu arvasite, ühendamise samm.

Ühendamisetapp on lahendus lihtsale probleemile, mis seisneb kahe sorteeritud loendi (massiivi) ühendamises ühe suure sorteeritud loendi (massiivi) koostamiseks.

Algoritm säilitab kolme osutit, ühe kummagi massiivi jaoks ja ühe lõpliku sorteeritud massiivi praeguse indeksi säilitamiseks.

Kas oleme jõudnud mõne massiivi lõppu? Ei: Võrdle mõlema massiivi praeguseid elemente Kopeeri väiksem element sorteeritud massiivi Liiguta väiksemat elementi sisaldava elemendi kursor Jah: Kopeeri kõik ülejäänud tühja massiivi elemendid
Ühenda samm

Ühendamise algoritmi koodi kirjutamine

Märgatav erinevus ülalkirjeldatud ühendamisetapi ja selle vahel, mida me ühendamissorteerimiseks kasutame, on see, et ühendamisfunktsiooni täidame ainult järjestikustel alammassiividel.

Seetõttu vajame ainult massiivi, esimest positsiooni, esimese alamkihi viimast indeksit (saame arvutada teise alamkihi esimese indeksi) ja teise alamkihi viimast indeksit.

Meie ülesandeks on ühendada kaks alamkaarti A (p… q) ja A (q + 1… r), et luua sorteeritud massiiv A (p… r). Seega on funktsiooni sisendid A, p, q ja r

Ühendamisfunktsioon töötab järgmiselt:

  1. Looge alamkaartide koopiad L ← A(p… q)ja M ← A (q + 1… r).
  2. Looge kolm osutit i, j ja k
    1. i säilitab praeguse L-indeksi alates 1-st
    2. j säilitab praeguse M indeksi alates 1-st
    3. k säilitab praeguse A (p… q) indeksi, alustades p-st.
  3. Kuni jõuame kas L või M lõpuni, valige L ja M elementide hulgast suurem ja asetage need õigesse asendisse A (p… q)
  4. Kui elemendid kas L- või M-st otsa saavad, korja ülejäänud elemendid üles ja pane A (p… q)

Koodis näeks see välja järgmine:

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

Ühendamine () Funktsioon selgitatakse samm-sammult

Selles funktsioonis toimub palju, nii et võtame näite, kuidas see toimib.

Nagu tavaliselt, räägib pilt tuhat sõna.

Massiivi kahe järjestikuse alamsaare ühendamine

Massiiv A (0… 5) sisaldab kahte järjestatud alamriba A (0… 3) ja A (4… 5). Vaatame, kuidas ühendamisfunktsioon ühendab kaks massiivi.

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

1. samm: looge sorteeritavate alammassiivide koopiad

  // 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)
Looge ühendamiseks alamkaartide koopiad

2. samm: säilitage alammassiivide ja põhimassiivi praegune register

  int i, j, k; i = 0; j = 0; k = p;
Säilitage alammassiivi ja põhimassiivi koopiate indeksid

3. samm: kuni jõuame kas L või M lõpuni, valige elementide L ja M seast suurem ja asetage need õigesse asendisse 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++; )
Sorteeritud alamkihtide üksikute elementide võrdlemine, kuni jõuame ühe lõpuni

4. samm: kui elemendid L või M-st otsa saavad, korja ülejäänud elemendid üles ja pane A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopeerige ülejäänud elemendid esimesest massiivist põhialasse 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopeerige teise massiivi ülejäänud elemendid põhialasse

See samm oleks olnud vajalik, kui M suurus oleks suurem kui L

Ühendamisfunktsiooni lõpus sorteeritakse alamkaart A (p… r).

Pythoni, Java ja C / C ++ näited

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

Sorteeri keerukus

Aja keerukus

Parima juhtumi keerukus: O (n * log n)

Halvima juhtumi keerukus: O (n * log n)

Keskmine juhtumi keerukus: O (n * log n)

Ruumi keerukus

Ühendamissordi ruumiline keerukus on O (n).

Ühenda rakenduste sortimine

  • Inversioonide loendamise probleem
  • Väline sortimine
  • E-kaubanduse rakendused

Huvitavad Artiklid...