Споји алгоритам сортирања

У овом упутству ћете научити о сортирању спајања. Такође ћете наћи радне примере спајања сорти Ц, Ц ++, Јава и Питхон.

Мерге Сорт је један од најпопуларнијих алгоритама за сортирање који се заснива на принципу Дивиде анд Цонкуер Алгоритхм.

Овде је проблем подељен на више подпроблема. Сваки под-проблем се решава појединачно. Коначно, под-проблеми се комбинују да би се створило коначно решење.

Пример сортирања обједињавања

Стратегија поделе и освајања

Коришћење Подели и освоји технику, делимо проблем у субпроблемс. Када је решење за сваки потпроблем спремно, ми „комбинујемо“ резултате из потпроблема да бисмо решили главни проблем.

Претпоставимо да смо морали сортирати низ А. Подпроблем би био сортирање пододсјека овог низа који започиње на индексу п и завршава на индексу р, означеном као А (п … р).

Подијели
Ако је к тачка на пола пута између п и р, тада можемо подијелити подниз А (п … р) на два низа А (п … к) и А (к + 1, р).

Освајање
У кораку освајања покушавамо да сортирамо и поднизове А (п… к) и А (к + 1, р). Ако још увек нисмо дошли до основног случаја, поново делимо оба ова низа и покушавамо да их сортирамо.

Комбиновање
Када корак освајања достигне основни корак и добијемо два сортирана подниза А (п… к) и А (к + 1, р) за низ А (п… р), комбинујемо резултате стварањем сортираног низа А ( п … р) из два сортирана подниза А (п … к) и А (к + 1, р).

МергеСорт алгоритам

Функција МергеСорт више пута дели низ на две половине док не дођемо до фазе у којој покушавамо да изведемо МергеСорт на поднизу величине 1, тј. П == р.

Након тога, функција спајања ступа у игру и комбинује сортиране низове у веће низове док се цео низ не споји.

 МергеСорт (А, п, р): ако је п> р врати к = (п + р) / 2 мергеСорт (А, п, к) мергеСорт (А, к + 1, р) спајање (А, п, к, р )

Да бисмо сортирали читав низ, морамо да позовемо MergeSort(A, 0, length(A)-1).

Као што је приказано на доњој слици, алгоритам сортирања спајања рекурзивно дели низ на половине док не дођемо до основног случаја низа са 1 елементом. Након тога, функција спајања преузима сортиране под-низове и спаја их да би постепено сортирала читав низ.

Споји сортирање на делу

Стапања Корак сортирање спајањем

Сваки рекурзивни алгоритам зависи од основног случаја и могућности комбиновања резултата из основних случајева. Сортирање спајања се не разликује. Најважнији део алгоритма за сортирање спајања је, претпостављате, корак спајања.

Корак спајања је решење једноставног проблема спајања две сортиране листе (низа) за изградњу једне велике сортиране листе (низа).

Алгоритам одржава три показивача, по један за сваки од два низа и један за одржавање тренутног индекса коначног сортираног низа.

Да ли смо стигли до краја било ког низа? Не: Упоредите тренутне елементе оба низа Копирање мањег елемента у сортирани низ Премештање показивача на елемент који садржи мањи елемент Да: Копирање свих преосталих елемената који нису празни
Корак обједињавања

Писање кода за алгоритам спајања

Приметна разлика између корака спајања који смо горе описали и оног који користимо за сортирање спајања је у томе што функцију спајања изводимо само на узастопним поднизима.

Због тога су нам потребни само низ, прва позиција, последњи индекс првог подреда (можемо израчунати први индекс другог подреда) и последњи индекс другог подреда.

Наш задатак је спојити два подниза А (п … к) и А (к + 1 … р) да бисмо креирали сортирани низ А (п … р). Дакле, улази у функцију су А, п, к и р

Функција спајања ради на следећи начин:

  1. Направите копије подсклопова L ← A(p… q)и М ← А (к + 1… р).
  2. Направите три показивача и, ј и к
    1. одржавам тренутни индекс Л, почев од 1
    2. ј одржава тренутни индекс М, почев од 1
    3. к одржава тренутни индекс А (п… к), почевши од п.
  3. Док не стигнемо на крај Л или М, одаберите већи међу елементима из Л и М и поставите их у прави положај у А (п … к)
  4. Кад нам понестане елемената у Л или М, покупите преостале елементе и ставите А (п… к)

У коду би ово изгледало овако:

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

Функција обједињавања () објашњена корак по корак

Пуно се тога дешава у овој функцији, па узмимо пример да видимо како ће ово функционисати.

Као и обично, слика говори хиљаду речи.

Спајање два узастопна подниза низа

Низ А (0… 5) садржи два сортирана подниза А (0… 3) и А (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: Док не стигнемо на крај Л или М, одаберите већи међу елементима Л и М и поставите их у прави положај у А (п … р)

  while (i < n1 && j < n2) ( if (L(i) <= M(j)) ( arr(k) = L(i); i++; ) else ( arr(k) = M(j); j++; ) k++; )
Упоређивање појединачних елемената сортираних подсредова док не дођемо до краја једног

Корак 4: Када нам понестане елемената било у Л или М, покупите преостале елементе и ставите А (п … р)

  // 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++; ) )
Прекопирајте преостале елементе другог низа у главни подниз

Овај корак би био потребан да је величина М већа од Л.

На крају функције спајања подред А (п … р) је сортиран.

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц ++ 
 # 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; )

Сложеност сортирања стапања

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

Сложеност најбољег случаја: О (н * лог н)

Најгора сложеност случаја: О (н * лог н)

Просечна сложеност случаја: О (н * лог н)

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

Сложеност простора спајања је О (н).

Споји сортиране апликације

  • Проблем броја инверзије
  • Спољно сортирање
  • Апликације за е-трговину

Занимљиви Чланци...

Рецоммендед