Обединяване на алгоритъм за сортиране

В този урок ще научите за обединяването. Също така ще намерите работещи примери за сливане на сорти C, C ++, Java и Python.

Merge Sort е един от най-популярните алгоритми за сортиране, който се основава на принципа Divide and Conquer Algorithm.

Тук проблемът е разделен на множество подпроблеми. Всеки подзадача се решава индивидуално. И накрая, подзадачите се комбинират, за да образуват окончателното решение.

Пример за сортиране на обединяване

Стратегия за разделяне и завладяване

Използвайки техниката Divide and Conquer , разделяме проблема на подпроблеми. Когато решението за всяка подпроблема е готово, ние „комбинираме“ резултатите от подпроблемите, за да решим основния проблем.

Да предположим, че трябва да сортираме масив А. Подпроблема би била да сортираме подраздел на този масив, започващ от индекс p и завършващ до индекс r, обозначен като A (p … r).

Разделяне
Ако q е точката на средата между p и r, тогава можем да разделим подмасива A (p … r) на два масива A (p … q) и A (q + 1, r).

Conquer
В стъпката conquer се опитваме да сортираме както подмасивите A (p… q), така и A (q + 1, r). Ако все още не сме достигнали до основния случай, отново разделяме и двете подредове и се опитваме да ги сортираме.

Комбиниране
Когато стъпката conquer достигне основната стъпка и получим две сортирани подмасиви A (p … q) и A (q + 1, r) за масив A (p … r), комбинираме резултатите, като създадем сортиран масив A p … r) от две сортирани подредове A (p … q) и A (q + 1, r).

Алгоритъмът MergeSort

Функцията MergeSort многократно разделя масива на две половини, докато стигнем до етап, в който се опитваме да изпълним MergeSort на подмасив с размер 1, т.е. p == r.

След това функцията за сливане влиза в действие и комбинира сортираните масиви в по-големи масиви, докато целият масив не бъде обединен.

 MergeSort (A, p, r): ако p> r връща q = (p + r) / 2 mergeSort (A, p, q) mergeSort (A, q + 1, r) сливане (A, p, q, r )

За да сортираме цял масив, трябва да се обадим MergeSort(A, 0, length(A)-1).

Както е показано на изображението по-долу, алгоритъмът за сортиране на сливане рекурсивно разделя масива на половинки, докато стигнем до основния случай на масив с 1 елемент. След това функцията за сливане взема сортираните подмасиви и ги обединява, за да сортира постепенно целия масив.

Обединяване на сортиране в действие

В обединяване етап на сортиране чрез сливане

Всеки рекурсивен алгоритъм зависи от базовия случай и възможността да се комбинират резултатите от базовите случаи. Сливането на обединяването не е по-различно. Най-важната част от алгоритъма за сортиране на обединяване е, както се досещате, стъпка за сливане.

Стъпката за сливане е решението на простия проблем за обединяването на два сортирани списъка (масиви), за да се изгради един голям сортиран списък (масив).

Алгоритъмът поддържа три указателя, по един за всеки от двата масива и един за поддържане на текущия индекс на крайния сортиран масив.

Стигнали ли сме до края на някой от масивите? Не: Сравнение на текущите елементи от двата масива Копиране на по-малък елемент в сортиран масив Преместване на показалеца на елемент, съдържащ по-малък елемент Да: Копиране на всички останали елементи на непразен масив
Стъпка за обединяване

Написване на кода за обединяване на алгоритъма

Забележима разлика между стъпката за обединяване, която описахме по-горе, и тази, която използваме за сортиране на сливане, е, че ние изпълняваме функцията за сливане само в последователни подмасиви.

Ето защо се нуждаем само от масива, първата позиция, последния индекс на първия подмасив (можем да изчислим първия индекс на втория подмасив) и последния индекс на втория подмасив.

Нашата задача е да обединим две поднизи A (p … q) и A (q + 1 … r), за да създадем сортиран масив A (p … r). Така че входовете за функцията са A, p, q и r

Функцията за сливане работи по следния начин:

  1. Създайте копия на подредовете L ← A(p… q)и M ← A (q + 1… r).
  2. Създайте три указателя i, j и k
    1. поддържа текущия индекс на L, започвайки от 1
    2. j поддържа текущия индекс на М, започвайки от 1
    3. k поддържа текущия индекс на A (p … q), започвайки от p.
  3. Докато стигнем края на L или M, изберете по-големия измежду елементите от L и M и ги поставете в правилната позиция на A (p … q)
  4. Когато свършим с елементи в L или M, вземете останалите елементи и сложете A (p … q)

В кода това би изглеждало така:

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

Функция за обединяване (), обяснена стъпка по стъпка

Много се случва с тази функция, така че нека вземем пример, за да видим как ще работи това.

Както обикновено, снимката говори хиляда думи.

Обединяване на два последователни подмасива на масив

Масивът A (0… 5) съдържа два сортирани подмасива A (0… 3) и A (4… 5). Нека видим как функцията за сливане ще обедини двата масива.

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

Стъпка 1: Създайте дублирани копия на подмасиви, които ще бъдат сортирани

  // 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)
Създайте копия на подредове за обединяване

Стъпка 2: Поддържайте текущия индекс на под-масиви и основен масив

  int i, j, k; i = 0; j = 0; k = p;
Поддържайте индекси на копия на под масив и основен масив

Стъпка 3: Докато стигнем края на L или M, изберете по-голям между елементите L и M и ги поставете в правилната позиция в 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++; )
Сравняване на отделни елементи от сортирани подредове, докато стигнем края на единия

Стъпка 4: Когато свършим с елементи в L или M, вземете останалите елементи и сложете A (p … r)

  // We exited the earlier loop because j < n2 doesn't hold while (i < n1) ( arr(k) = L(i); i++; k++; )
Копирайте останалите елементи от първия масив в основния подмасив 
  // We exited the earlier loop because i < n1 doesn't hold while (j < n2) ( arr(k) = M(j); j++; k++; ) )
Копирайте останалите елементи от втория масив в основния подмасив

Тази стъпка би била необходима, ако размерът на M беше по-голям от L.

В края на функцията за сливане подреждането A (p … r) се сортира.

Примери за Python, Java и 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; )

Сложност на сортиране на обединяване

Сложност във времето

Най-добрата сложност: O (n * log n)

Най-лошата сложност: O (n * log n)

Средна сложност на случая: O (n * log n)

Сложност на пространството

Сложността на пространството при сортиране на сливане е O (n).

Обединяване на приложения за сортиране

  • Проблем с броя на инверсиите
  • Външно сортиране
  • Приложения за електронна търговия

Интересни статии...

Препоръчано