merge sort c with examples
C ++ Техника за сортиране на обединяване.
Алгоритъмът за сортиране на обединяване използва „ разделяй и владей ”Стратегия, при която разделяме проблема на подпроблеми и ги решаваме индивидуално.
След това тези подпроблеми се комбинират или обединяват заедно, за да образуват единно решение.
=> Прочетете Популярната серия за обучение на C ++ тук.
Какво ще научите:
кой е най-добрият безплатен имейл акаунт
- Общ преглед
- Общ алгоритъм
- Псевдо код за сортиране на обединяване
- Илюстрация
- Итеративно сортиране на обединяване
- Анализ на сложността на алгоритъма за сортиране на обединяване
- Заключение
- Препоръчително четене
Общ преглед
Сортирането на обединяване се извършва чрез следните стъпки:
# 1) Списъкът, който трябва да се сортира, се разделя на два масива с еднаква дължина чрез разделяне на списъка върху средния елемент. Ако броят на елементите в списъка е 0 или 1, тогава списъкът се счита за сортиран.
# две) Всеки подлист се сортира поотделно, като се използва рекурсивно сортиране на обединяване.
# 3) След това сортираните подлисти се комбинират или обединяват, за да образуват пълен сортиран списък.
Общ алгоритъм
Общият псевдокод за техниката на сортиране на сливане е даден по-долу.
Декларирайте масив Arr с дължина N
Ако N = 1, Arr вече е сортиран
Ако N> 1,
Ляво = 0, дясно = N-1
Намерете средата = (вляво + вдясно) / 2
Обадете се merge_sort (Arr, ляво, средно) => сортирайте първата половина рекурсивно
Извикайте merge_sort (Arr, средно + 1, вдясно) => сортирайте втората половина рекурсивно
Извикайте сливане (Arr, ляво, средно, дясно), за да обедините сортираните масиви в горните стъпки.
Изход
Както е показано в горния псевдо код, в алгоритъма за сортиране на обединяване разделяме масива на половина и сортираме всяка половина, като използваме сливане рекурсивно. След като под-масивите се сортират поотделно, двата под-масива се обединяват заедно, за да образуват пълен сортиран масив.
Псевдо код за сортиране на обединяване
Следва псевдо кодът за техника на сортиране на сливане. Първо, имаме процедура за сливане на процедурата, за да разделим масива на половини рекурсивно. Тогава имаме процедура за сливане, която ще обедини сортираните по-малки масиви, за да получи пълен сортиран масив.
procedure mergesort( array,N ) array – list of elements to be sorted N – number of elements in the list begin if ( N == 1 ) return array var array1 as array = a(0) ... a(N/2) var array2 as array = a(N/2+1) ... a(N) array1 = mergesort(array1) array2 = mergesort(array2) return merge( array1, array2 ) end procedure procedure merge(array1, array2 ) array1 – first array array2 – second array begin var c as array while ( a and b have elements ) if ( array1(0) > array2(0) ) add array2 (0) to the end of c remove array2 (0) from array2 else add array1 (0) to the end of c remove array1 (0) from array1 end if end while while ( a has elements ) add a(0) to the end of c remove a(0) from a end while while ( b has elements ) add b(0) to the end of c remove b(0) from b end while return c end procedure
Нека сега илюстрираме техниката за сортиране на сливане с пример.
Илюстрация
Горната илюстрация може да бъде показана в таблична форма по-долу:
Подайте | Несортиран списък | разделям | Сортиран списък |
---|---|---|---|
един | {12, 23,2,43,51,35,19,4} | {12,23,2,43} {51,35,19,4} | {} |
две | {12,23,2,43} {51,35,19,4} | {12.23} {2.43} {51.35} {19.4} | {} |
3 | {12.23} {2.43} {51.35} {19.4} | {12.23} {2.43} {35.51} {4.19} | {12.23} {2.43} {35.51} {4.19} |
4 | {12.23} {2.43} {35.51} {4.19} | {2,12,23,43} {4,19,35,51} | {2,12,23,43} {4,19,35,51} |
5 | {2,12,23,43} {4,19,35,51} | {2,4,12,19,23,35,43,51} | {2,4,12,19,23,35,43,51} |
6 | {} | {} | {2,4,12,19,23,35,43,51} |
Както е показано в горното представяне, първо масивът е разделен на два под-масива с дължина 4. Всеки под-масив е допълнително разделен на още два под-масива с дължина 2. След това всеки под-масив е допълнително разделен на под-масив от по един елемент. Целият този процес е процесът „Разделяне“.
След като разделим масива на под-масиви от по един елемент, сега трябва да обединим тези масиви в сортиран ред.
Както е показано на илюстрацията по-горе, ние разглеждаме всеки подмасив от един елемент и първо комбинираме елементите, за да образуваме подмасиви от два елемента в сортиран ред. След това сортираните подмасиви с дължина две се сортират и комбинират, за да образуват два подмасива с дължина четири. След това комбинираме тези два под-масива, за да образуваме пълен сортиран масив.
Итеративно сортиране на обединяване
Алгоритъмът или техниката на сортиране на сливания, които видяхме по-горе, използва рекурсия. Известен е още като „ рекурсивно сортиране на сливане ”.
Знаем, че рекурсивните функции използват стека от извиквания на функции, за да съхраняват междинното състояние на извикващата функция. Той също така съхранява друга счетоводна информация за параметри и т.н. и поставя режийни разходи по отношение на съхраняване на запис за активиране на извикване на функцията, както и възобновяване на изпълнението.
От всички тези режийни разходи може да се отървем, ако използваме итеративни функции вместо рекурсивни. Горният алгоритъм за сортиране на сливания също може лесно да бъде преобразуван в итеративни стъпки, като се използват цикли и вземане на решения.
Подобно на рекурсивното сортиране на сливане, итеративното сортиране на сливане също има сложност O (nlogn), следователно по отношение на производителността, те се представят наравно помежду си. Ние просто сме в състояние да намалим режийните разходи.
В този урок се концентрирахме върху рекурсивно сортиране на сливане и след това ще приложим рекурсивно сортиране на сливане, използвайки езици C ++ и Java.
По-долу е дадено изпълнение на техника за сортиране чрез сливане, използващо C ++.
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< Изход:
Въведете броя на елементите за сортиране: 10
Въведете 10 елемента за сортиране: 101 10 2 43 12 54 34 64 89 76
Сортиран масив
2 10 12 34 43 54 64 76 89 101
В тази програма дефинирахме две функции, merge_sort и отивам . Във функцията merge_sort разделяме масива на два равни масива и извикваме функцията за сливане на всеки от тези под масиви. В функцията за сливане правим действителното сортиране на тези под масиви и след това ги обединяваме в един пълен сортиран масив.
След това внедряваме техниката Merge Sort на езика Java.
class MergeSort { void merge(int arr(), int beg, int mid, int end) { int left = mid - beg + 1; int right = end - mid; int Left_arr() = new int (left); int Right_arr() = new int (right); for (int i=0; i Изход:
Входен масив
101 10 2 43 12 54 34 64 89 76
Масивът е сортиран чрез сортиране чрез сливане
2 10 12 34 43 54 64 76 89 101
И при внедряването на Java използваме същата логика, както при внедряването на C ++.
Сливането на обединяване е ефективен начин за сортиране на списъци и най-вече се използва за сортиране на свързани списъци. Тъй като използва подход „разделяй и владей“, техниката за сортиране на сливане се представя еднакво ефективно както за по-малки, така и за по-големи масиви.
Анализ на сложността на алгоритъма за сортиране на обединяване
Знаем, че за да извършим сортиране чрез сортиране на сливане, първо разделяме масива на две равни половини. Това се представя от „log n“, което е логаритмична функция и броят на предприетите стъпки е log (n + 1) най-много.
След това, за да намерим средния елемент на масива, се изисква една стъпка, т.е.O (1).
След това, за да обединим подмасивите в масив от n елемента, ще вземем O (n) количество време за изпълнение.
По този начин общото време за извършване на сортиране на сливане ще бъде n (log n + 1), което ни дава времевата сложност на O (n * logn).
Най-лошата времева сложност O (n * log n) Най-добрата сложност във времето O (n * log n) Средна времева сложност O (n * log n) Космическа сложност На)
Сложността във времето за сортиране на обединяване е еднаква и в трите случая (най-лошото, най-доброто и средното), тъй като винаги разделя масива на под-масиви и след това обединява под-масивите, като взема линейно време.
Сливането на обединяването винаги отнема равно пространство като несортирани масиви. Следователно, когато списъкът, който ще се сортира, е масив, сортирането на сливане не трябва да се използва за много големи масиви. Сортирането на сливане обаче може да се използва по-ефективно за сортиране на свързани списъци.
Заключение
Merge sort използва стратегията „разделяй и владей“, която разделя масива или списъка на множество подмасиви и ги сортира поотделно и след това се обединява в пълен сортиран масив.
Сливането на обединяване се извършва по-бързо от другите методи за сортиране, а също така работи ефективно и за по-малки и по-големи масиви.
Ще проучим повече за Бързото сортиране в нашия предстоящ урок!
=> Внимавайте тук за начинаещи ръководства за обучение на C ++.
Препоръчително четене
- Метод за сортиране на MongoDB () с примери
- Команда за сортиране на Unix със синтаксис, опции и примери
- Сортиране на черупката в C ++ с примери
- Сортиране на купчини в C ++ с примери
- Сортиране на избора в C ++ с примери
- Сортиране на балончета в C ++ с примери
- Сортиране по вмъкване в C ++ с примери
- Бързо сортиране в C ++ с примери