Algorytm scalania sortowania

W tym samouczku nauczysz się sortowania przez scalanie. Znajdziesz tu również działające przykłady sortowania przez scalanie C, C ++, Java i Python.

Merge Sort to jeden z najpopularniejszych algorytmów sortowania, który opiera się na zasadzie algorytmu dzielenia i zwyciężania.

Tutaj problem jest podzielony na wiele podproblemów. Każdy problem podrzędny jest rozwiązywany indywidualnie. Wreszcie, podproblemy są łączone, aby stworzyć ostateczne rozwiązanie.

Przykład scalania i sortowania

Strategia dziel i podbijaj

Używając techniki Divide and Conquer , dzielimy problem na podproblemy. Gdy rozwiązanie każdego podproblemu jest gotowe, „łączymy” wyniki z podproblemów, aby rozwiązać główny problem.

Załóżmy, że musimy posortować tablicę A. Podproblem byłoby posortowanie podsekcji tej tablicy zaczynającej się od indeksu p i kończącej się na indeksie r, oznaczonej jako A (p… r).

Dzielenie
Jeśli q jest punktem w połowie drogi między p i r, to możemy podzielić podtablicę A (p… r) na dwie tablice A (p… q) i A (q + 1, r).

Pokonaj
Na etapie zdobywania staramy się posortować zarówno podtablice A (p… q), jak i A (q + 1, r). Jeśli nie osiągnęliśmy jeszcze przypadku podstawowego, ponownie dzielimy obie te podtablice i próbujemy je posortować.

Łączenie
Kiedy krok zdobywania osiągnie krok podstawowy i otrzymamy dwie posortowane podtablice A (p… q) i A (q + 1, r) dla tablicy A (p… r), łączymy wyniki, tworząc posortowaną tablicę A ( p… r) z dwóch posortowanych podtablic A (p… q) i A (q + 1, r).

Algorytm MergeSort

Funkcja MergeSort wielokrotnie dzieli tablicę na dwie połowy, aż osiągamy etap, w którym próbujemy wykonać MergeSort na podtablicy o rozmiarze 1, tj. P == r.

Następnie w grę wchodzi funkcja scalania, która łączy posortowane tablice w większe tablice, aż cała tablica zostanie scalona.

 MergeSort (A, p, r): jeśli p> r return q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) merge (A, p, q, r) )

Aby posortować całą tablicę, musimy wywołać MergeSort(A, 0, length(A)-1).

Jak pokazano na poniższym obrazku, algorytm sortowania przez scalanie rekurencyjnie dzieli tablicę na połowy, aż osiągniemy podstawowy przypadek tablicy z 1 elementem. Następnie funkcja scalania wybiera posortowane tablice podrzędne i łączy je, aby stopniowo posortować całą tablicę.

Sortowanie przez scalanie w akcji

Seryjnej Etap sortowanie przez scalanie

Każdy algorytm rekurencyjny jest zależny od przypadku podstawowego i możliwości łączenia wyników z przypadków podstawowych. Sortowanie przez scalanie nie jest inne. Najważniejszą częścią algorytmu sortowania przez scalanie jest, jak się domyślacie, krok scalania.

Etap scalania jest rozwiązaniem prostego problemu łączenia dwóch posortowanych list (tablic) w celu zbudowania jednej dużej posortowanej listy (tablicy).

Algorytm utrzymuje trzy wskaźniki, po jednym dla każdej z dwóch tablic i jeden do utrzymywania bieżącego indeksu ostatniej posortowanej tablicy.

Czy doszliśmy do końca którejkolwiek z tablic? Nie: Porównaj bieżące elementy obu tablic Skopiuj mniejszy element do posortowanej tablicy Przesuń wskaźnik elementu zawierającego mniejszy element Tak: Skopiuj wszystkie pozostałe elementy niepustej tablicy
Scal krok

Pisanie kodu algorytmu scalania

Zauważalna różnica między krokiem scalania, który opisaliśmy powyżej, a tym, którego używamy do sortowania przez scalanie, polega na tym, że wykonujemy funkcję scalania tylko na kolejnych tablicach podrzędnych.

Dlatego potrzebujemy tylko tablicy, pierwszej pozycji, ostatniego indeksu pierwszej podtablicy (możemy obliczyć pierwszy indeks drugiej podtablicy) i ostatniego indeksu drugiej podtablicy.

Naszym zadaniem jest scalenie dwóch podtablic A (p… q) i A (q + 1… r) w celu utworzenia posortowanej tablicy A (p… r). Zatem dane wejściowe funkcji to A, p, q i r

Funkcja scalania działa w następujący sposób:

  1. Utwórz kopie podtablic L ← A(p… q)i M ← A (q + 1… r).
  2. Utwórz trzy wskaźniki i, j oraz k
    1. i utrzymuje aktualny indeks L, zaczynając od 1
    2. j utrzymuje aktualny indeks M, począwszy od 1
    3. k utrzymuje aktualny indeks A (p… q), zaczynając od p.
  3. Dopóki nie dojdziemy do końca L lub M, wybierz większy spośród elementów z L i M i umieść je we właściwej pozycji w A (p… q)
  4. Kiedy skończą nam się elementy w L lub M, podnieś pozostałe elementy i wstaw A (p… q)

W kodzie wyglądałoby to następująco:

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

Funkcja Merge () wyjaśniona krok po kroku

W tej funkcji dużo się dzieje, więc weźmy przykład, aby zobaczyć, jak to zadziała.

Jak zwykle obraz mówi więcej niż tysiąc słów.

Łączenie dwóch kolejnych podtablic tablicy

Tablica A (0… 5) zawiera dwie posortowane podtablice A (0… 3) i A (4… 5). Zobaczmy, jak funkcja merge połączy dwie tablice.

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

Krok 1: Utwórz zduplikowane kopie tablic podrzędnych do posortowania

  // 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)
Utwórz kopie podtablic do scalenia

Krok 2: Utrzymaj aktualny indeks pod-tablic i głównej tablicy

  int i, j, k; i = 0; j = 0; k = p;
Zachowaj indeksy kopii tablicy podrzędnej i tablicy głównej

Krok 3: Dopóki nie dojdziemy do końca L lub M, wybierz większy spośród elementów L i M i umieść je we właściwej pozycji w 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++; )
Porównywanie poszczególnych elementów posortowanych podtablic do końca jednej

Krok 4: Kiedy skończą nam się elementy w L lub M, podnieś pozostałe elementy i wstaw A (p… r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Skopiuj pozostałe elementy z pierwszej tablicy do głównej podtablicy 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Skopiuj pozostałe elementy drugiej tablicy do głównej podtablicy

Ten krok byłby potrzebny, gdyby rozmiar M był większy niż L.

Na końcu funkcji scalania sortowana jest podtablica A (p… r).

Przykłady w Pythonie, Javie 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; )

Scal złożoność sortowania

Złożoność czasowa

Złożoność najlepszego przypadku: O (n * log n)

Złożoność najgorszego przypadku: O (n * log n)

Średnia złożoność przypadku: O (n * log n)

Złożoność przestrzeni

Złożoność przestrzeni sortowania przez scalanie wynosi O (n).

Połącz aplikacje sortowania

  • Problem z liczbą inwersji
  • Sortowanie zewnętrzne
  • Aplikacje e-commerce

Interesujące artykuły...