TechCodeview

Сортування злиттям схоже на алгоритм швидкого сортування, оскільки працює на основі концепції розділяй і володарюй. Це один із найпопулярніших і ефективних алгоритмів сортування. Це найкращий приклад для категорії алгоритмів «розділяй і володарюй».

Він ділить заданий список на дві половини, викликає себе для двох половин, а потім об’єднує дві відсортовані половини. Ми визначаємо злиття () функція, яка використовується для злиття двох половин.

Підсписки знову і знову діляться навпіл, поки ми не отримаємо єдиний елемент кожен. Потім ми об’єднуємо пару списків одного елемента в два списки елементів, сортуючи їх у процесі. Відсортовані дві пари елементів об’єднуються в чотири списки елементів і так далі, поки ми не отримаємо відсортований список.

Концепція сортування злиттям

Давайте подивимося на наступну діаграму сортування злиттям.

Ми розділили наведений список на дві половини. Список не можна ділити на рівні частини, це абсолютно не важливо.

Сортування злиттям можна реалізувати двома способами - підходом зверху вниз і підходом знизу вгору. У наведеному вище прикладі ми використовуємо підхід «зверху вниз», тобто сортування злиттям найчастіше використовується.

Підхід «знизу вгору» забезпечує більшу оптимізацію, яку ми визначимо пізніше.

Основна частина алгоритму полягає в тому, як ми об’єднуємо два відсортовані підсписки. Давайте об’єднаємо два відсортованих списку злиття.

• A : [ 2 , 4, 7, 8]
• B : [ 1 , 3, 11]
• відсортовано: пусто

Спочатку спостерігаємо за першим елементом обох списків. Ми виявили, що перший елемент B менший, тому ми додаємо його в наш відсортований список і рухаємося вперед у списку B.

• A : [ 2 , 4, 7, 8]
• B : [1, 3 , одинадцять]
• Відсортовано: 1

Тепер ми дивимося на наступну пару елементів 2 і 3. 2 менший, тому ми додаємо його в наш відсортований список і рухаємося вперед до списку.

• A : [ 2 , 4, 7, 8]
• B : [1, 3 , одинадцять]
• Відсортовано: 1

Продовжуйте цей процес, і ми отримаємо відсортований список {1, 2, 3, 4, 7, 8, 11}. Особливих випадків може бути два.

оператор if java

Що робити, якщо обидва підсписки мають однакові елементи. У такому випадку ми можемо перемістити один підсписок і додати елемент до відсортованого списку. Технічно ми можемо рухатися вперед в обох підсписках і додавати елементи до відсортованого списку.

У нас не залишилося жодного елемента в одному підсписку. Коли у нас закінчується підсписок, просто додайте елемент другого за іншим.

Слід пам'ятати, що ми можемо сортувати елемент у будь-якому порядку. Ми сортуємо наданий список у порядку зростання, але ми можемо легко сортувати в порядку спадання.

Реалізація

Алгоритм сортування злиттям реалізовано за допомогою підходу зверху вниз. Це може здатися трохи складним, тому ми детально розглянемо кожен етап. Тут ми реалізуємо цей алгоритм на двох типах колекцій — списку цілочисельних елементів (зазвичай використовується для введення сортування) і спеціальному об’єкті (більш практичний і реалістичний сценарій).

Масив сортування

Основна концепція алгоритму полягає в тому, щоб розділити (під)список на половини та сортувати їх рекурсивно. Ми продовжуємо процес, поки не отримаємо списки, які містять лише один елемент. Давайте розберемо наступну функцію для ділення -

 def merge_sort(array, left_index, right_index): if left_index >= right_index: return middle = (left_index + right_index)//2 merge_sort(array, left_index, middle) merge_sort(array, middle + 1, right_index) merge(array, left_index, right_index, middle) 

Наша головна мета — розділити список на підчастини до того, як відбудеться сортування. Нам потрібно отримати ціле значення, тому ми використовуємо оператор // для наших індексів.

Давайте зрозуміємо описану вище процедуру, виконавши наступні кроки.

• Першим кроком є ​​створення копій списків. Перший список містить списки з [лівий_індекс,...,середина] а другий від [середній+1,?,правий_індекс] .
• Ми обходимо обидві копії списку за допомогою покажчика, вибираємо менше значення з двох значень і додаємо їх до відсортованого списку. Як тільки ми додаємо елемент до списку, ми рухаємося вперед у відсортованому списку незалежно від цього.
• Додайте решту елементів в іншій копії до відсортованого масиву.

Реалізуємо сортування злиттям у програмі Python.

що таке особливий символ

Програма Python

 # Here, we are declaring the function to divide the lists in to the two sub lists # Here, we are passing the list1, left index, right index as the parameters def merge_sort(list1, left_index, right_index): if left_index &gt;= right_index: # here, we are checking the if condition return middle = (left_index + right_index)//2 # Here, we are finding the middle of the given two numbers merge_sort(list1, left_index, middle) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, middle + 1, right_index) # Here, we are calling the merge sort function till the end of the list i.e., right index merge(list1, left_index, right_index, middle) # Here, we are calling the merge function to merge the divided list using the merge # sort function above # Here, we are defining a function for merge the list after dividing def merge(list1, left_index, right_index, middle): # Here, we are creating subparts of a lists left_sublist = list1[left_index:middle + 1] right_sublist = list1[middle+1:right_index+1] # Here, we are initializing the values for variables that we use to keep # track of where we are in each list1 left_sublist_index = 0 right_sublist_index = 0 sorted_index = left_index # Here, we are traversing the both copies until we get run out one element while left_sublist_index <len(left_sublist) 1 and right_sublist_index < len(right_sublist): # here, we are declaring a while loop if our left_sublist has the smaller element, put it in sorted part then move forward (by increasing pointer) left_sublist[left_sublist_index] checking condition, is true will enter block list1[sorted_index]="left_sublist[left_sublist_index]" left_sublist_index="left_sublist_index" + otherwise add into right sublist else: moving sorted_index="sorted_index" go through remaining elements them len(left_sublist): len(right_sublist):# list1="[44," 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] print('the given list before performing merge sort is: ', list1) this input unsorted array by user merge_sort(list1, 0, len(list1) -1) after is:', printing amd functions pre> <p> <strong>Output:</strong> </p> <pre> The given list before performing the merge sort is: [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] The given list after performing the merge sort is: [1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74] </pre> <h2>Sorting Custom Objects</h2> <p>We can also sort the custom objects by using the <a href="/python-tutorial-python-programming-language">Python</a> class. This algorithm is almost similar to the above but we need to make it more versatile and pass the comparison function.</p> <p>We will create a custom class, Car and add a few fields to it. We make few changes in the below algorithm to make it more versatile. We can do this by using the lambda functions.</p> <p>Let&apos;s understand the following example.</p> <h3>Python Program</h3> <pre> class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format(&apos;Make: {}, Model: {}, Year: {}&apos;, self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print('cars sorted by year:') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let&apos;s understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)></pre></len(left_sublist)>

Сортування настроюваних об’єктів

Ми також можемо сортувати власні об’єкти за допомогою Python клас. Цей алгоритм майже схожий на наведений вище, але нам потрібно зробити його більш універсальним і передати функцію порівняння.

Ми створимо спеціальний клас Car і додамо до нього кілька полів. Ми вносимо деякі зміни в наведений нижче алгоритм, щоб зробити його більш універсальним. Ми можемо зробити це за допомогою лямбда-функцій.

Давайте розберемося в наступному прикладі.

Програма Python

 class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format(&apos;Make: {}, Model: {}, Year: {}&apos;, self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print(\'cars sorted by year:\') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:\') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let&apos;s understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)>

Оптимізація

Ми можемо покращити продуктивність алгоритму сортування злиттям. Спочатку давайте зрозуміємо різницю між сортуванням злиттям зверху вниз і знизу вгору. Підхід «знизу вгору» сортує елементи суміжних списків ітеративно, а підхід «зверху вниз» розбиває списки на дві половини.

Даний список має вигляд [10, 4, 2, 12, 1, 3], замість того, щоб розбивати його на [10], [4], [2], [12], [1], [3], ми ділимо у підсписки, які, можливо, вже відсортовано: [10, 4], [2], [1, 12], [3] і тепер готові до їх сортування.

Сортування злиттям є неефективним алгоритмом як у часі, так і в просторі для менших підсписків. Отже, сортування вставкою є більш ефективним алгоритмом, ніж сортування злиттям для менших підсписків.

Висновок

Сортування злиттям є популярним і ефективним алгоритмом. Це більш ефективний алгоритм для великих списків. Це не залежить від будь-яких невдалих рішень, які призводять до поганої роботи.

У сортуванні злиттям є один великий недолік. Він використовує додаткову пам’ять, яка використовується для зберігання тимчасових копій списків перед їх об’єднанням. Однак сортування злиттям широко використовується в програмному забезпеченні. Його дія швидка і дає чудовий результат.

Ми коротко обговорили концепцію сортування злиттям і реалізували її як на простому списку цілих чисел, так і на настроюваних об’єктах за допомогою лямбда-функції, яка використовується для порівняння.