Spoji algoritam sortiranja

U ovom vodiču naučit ćete o sortiranju spajanja. Također ćete pronaći radne primjere spajanja sorti C, C ++, Java i Python.

Spajanje sortiranja jedan je od najpopularnijih algoritama za sortiranje koji se temelji na principu Divide and Conquer Algorithm.

Ovdje se problem dijeli na više potproblema. Svaki se pod-problem rješava pojedinačno. Konačno, pod-problemi se kombiniraju u konačno rješenje.

Primjer sortiranja stapanja

Podijeli i osvoji strategiju

Korištenje Podijeli pa vladaj tehniku, podijelimo problem u subproblems. Kada je rješenje za svaki potproblem spremno, 'kombiniramo' rezultate iz potproblema kako bismo riješili glavni problem.

Pretpostavimo da smo morali razvrstati niz A. Podproblem bi bio razvrstavanje pododsjeka ovog niza koji započinje indeksom p i završava indeksom r, označenim kao A (p … r).

Podijeli
Ako je q točka na pola puta između p i r, tada možemo podijeliti podniz A (p … r) na dva polja A (p … q) i A (q + 1, r).

Osvajanje
U koraku osvajanja pokušavamo razvrstati i podsklopove A (p… q) i A (q + 1, r). Ako još nismo došli do osnovnog slučaja, opet dijelimo oba ova niza i pokušavamo ih sortirati.

Kombiniraj
Kada korak osvajanja dosegne osnovni korak i dobijemo dva razvrstana podreza A (p… q) i A (q + 1, r) za niz A (p… r), kombiniramo rezultate stvaranjem razvrstanog niza A ( p … r) iz dva razvrstana podsklopa A (p … q) i A (q + 1, r).

MergeSort algoritam

Funkcija MergeSort opetovano dijeli niz na dvije polovice dok ne dođemo do faze u kojoj pokušavamo izvesti MergeSort na podnizu veličine 1 tj. P == r.

Nakon toga dolazi u obzir funkcija spajanja i kombinira razvrstane nizove u veće nizove dok se cijeli niz ne spoji.

 MergeSort (A, p, r): ako je p> r vrati q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) spajanje (A, p, q, r )

Da bismo sortirali čitav niz, moramo nazvati MergeSort(A, 0, length(A)-1).

Kao što je prikazano na donjoj slici, algoritam sortiranja spajanja rekurzivno dijeli niz na polovice dok ne dođemo do osnovnog slučaja niza s 1 elementom. Nakon toga, funkcija spajanja preuzima sortirane pod-nizove i spaja ih kako bi postupno razvrstala cijeli niz.

Spoji sortiranje na djelu

Spajanje Korak od pisma Sort

Svaki rekurzivni algoritam ovisi o osnovnom slučaju i mogućnosti kombiniranja rezultata iz osnovnih slučajeva. Sortiranje spajanja se ne razlikuje. Najvažniji dio algoritma za spajanje je, pogađate, korak spajanja.

Korak spajanja rješenje je jednostavnog problema spajanja dvaju sortiranih popisa (polja) za izgradnju jednog velikog sortiranog popisa (polja).

Algoritam održava tri pokazivača, po jedan za svaki od dva polja i jedan za održavanje trenutnog indeksa konačnog razvrstanog niza.

Jesmo li došli do kraja bilo kojeg niza? Ne: Usporedba trenutnih elemenata oba niza Kopiranje manjeg elementa u razvrstani niz Pomicanje pokazivača elementa koji sadrži manji element Da: Kopiranje svih preostalih elemenata nepraznog niza
Korak spajanja

Pisanje koda za algoritam spajanja

Primjetna razlika između gore opisanog koraka spajanja i onog koji koristimo za sortiranje spajanja je u tome što funkciju spajanja izvodimo samo na uzastopnim podnizima.

Zbog toga su nam potrebni samo niz, prvo mjesto, posljednji indeks prvog podreda (možemo izračunati prvi indeks drugog podreda) i posljednji indeks drugog podreda.

Naš je zadatak spojiti dva podsklopa A (p … q) i A (q + 1 … r) kako bismo stvorili razvrstani niz A (p … r). Dakle, ulazi u funkciju su A, p, q i r

Funkcija spajanja radi na sljedeći način:

  1. Stvorite kopije podsklopova L ← A(p… q)i M ← A (q + 1… r).
  2. Stvorite tri pokazivača i, j i k
    1. održavam trenutni indeks L, počevši od 1
    2. j održava trenutni indeks M, počevši od 1
    3. k održava trenutni indeks A (p… q), počevši od p.
  3. Dok ne stignemo na kraj L ili M, odaberite veći među elementima iz L i M i postavite ih u točan položaj u A (p… q)
  4. Kad nam ponestane elemenata u L ili M, pokupite preostale elemente i stavite A (p … q)

U kodu bi ovo izgledalo ovako:

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

Korak po korak objašnjena funkcija objedinjavanja ()

Puno se toga događa u ovoj funkciji, pa uzmimo primjer da vidimo kako će to funkcionirati.

Kao i obično, slika govori tisuću riječi.

Spajanje dva uzastopna niza niza

Niz A (0… 5) sadrži dva razvrstana podsreza A (0… 3) i A (4… 5). Pogledajmo kako će funkcija spajanja spojiti dva niza.

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

Korak 1: Stvorite dvostruke kopije podsrezova koji će se sortirati

  // 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)
Stvorite kopije podsklopova za spajanje

Korak 2: Održavanje trenutnog indeksa podnizova i glavnog niza

  int i, j, k; i = 0; j = 0; k = p;
Održavajte indekse kopija podniza i glavnog niza

Korak 3: Dok ne stignemo na kraj L ili M, odaberite veći među elementima L i M i postavite ih u ispravan položaj u 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++; )
Uspoređujući pojedinačne elemente razvrstanih podsklopova dok ne dođemo do kraja jednog

Korak 4: Kad nam ponestane elemenata bilo u L ili M, pokupite preostale elemente i stavite A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Kopirajte preostale elemente iz prvog niza u glavni podniz 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Kopirajte preostale elemente drugog niza u glavni podniz

Ovaj bi korak bio potreban da je veličina M veća od L.

Na kraju funkcije spajanja sortira se podniz A (p … r).

Primjeri Pythona, Java i 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; )

Složenost sortiranja stapanja

Složenost vremena

Složenost najboljeg slučaja: O (n * log n)

Najgora složenost slučaja: O (n * log n)

Prosječna složenost predmeta: O (n * log n)

Složenost prostora

Složenost prostora spajanja je O (n).

Spoji sortiranje aplikacija

  • Problem broja inverzija
  • Vanjsko sortiranje
  • Aplikacije za e-trgovinu

Zanimljivi članci...