Сортирането чрез сливане е подобно на алгоритъма за бързо сортиране, тъй като работи върху концепцията за разделяй и владей. Това е един от най-популярните и ефективни алгоритъми за сортиране. Това е най-добрият пример за разделяй и владей категория алгоритми.
Той разделя дадения списък на две половини, извиква се за двете половини и след това обединява двете сортирани половини. Ние определяме сливане () функция, използвана за сливане на две половини.
Подсписъците се разделят отново и отново на половини, докато получим само един елемент всеки. След това комбинираме двойката от списъци с един елемент в два списъка с елементи, като ги сортираме в процеса. Сортираните две двойки елементи се обединяват в списъка с четири елемента и така нататък, докато получим сортирания списък.
Концепция за сортиране чрез сливане
Нека видим следната диаграма за сортиране чрез сливане.
Разделихме дадения списък на две половини. Списъкът не може да бъде разделен на равни части, това няма никакво значение.
Сортирането чрез сливане може да се реализира по два начина - подход отгоре надолу и подход отдолу нагоре. Използваме подхода отгоре надолу в горния пример, който е най-често използваното сортиране чрез сливане.
Подходът отдолу нагоре осигурява повече оптимизация, която ще дефинираме по-късно.
Основната част от алгоритъма е как комбинираме двата сортирани подсписъка. Нека обединим двата сортирани списъка за сливане.
- 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}. Може да има два специални случая.
размер шрифт латекс
Ами ако и двата подсписъка имат едни и същи елементи - В такъв случай можем да преместим единия подсписък и да добавим елемента към сортирания списък. Технически можем да продължим напред в двата подсписъка и да добавим елементите към сортирания списък.
Нямаме останал елемент в един подсписък. Когато изчерпим подсписъка, просто добавяме елемента от втория един след друг.
Трябва да помним, че можем да сортираме елемента в произволен ред. Ние сортираме дадения списък във възходящ ред, но можем лесно да сортираме в низходящ ред.
Внедряване
Алгоритъмът за сортиране чрез сливане се реализира чрез използване на подхода отгоре надолу. Може да изглежда малко трудно, така че ще разработим подробности за всяка стъпка. Тук ще приложим този алгоритъм върху два типа колекции - списък на целочислен елемент (обикновено използван за въвеждане на сортиране) и потребителски обект (по-практичен и реалистичен сценарий).
np точка
Масив за сортиране
Основната концепция на алгоритъма е да раздели (под)списъка на половини и да ги сортира рекурсивно. Продължаваме процеса, докато завършим списъци, които имат само един елемент. Нека разберем следната функция за деление -
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 >= 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'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('Make: {}, Model: {}, Year: {}', 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('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 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'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('Make: {}, Model: {}, Year: {}', 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('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 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'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] и сега са готови да ги сортирате.
Сортирането чрез сливане е неефективен алгоритъм както във времето, така и в пространството за по-малките подсписъци. Така че сортирането чрез вмъкване е по-ефективен алгоритъм от сортирането чрез сливане за по-малките подсписъци.
Заключение
Сортирането чрез сливане е популярен и ефективен алгоритъм. Това е по-ефективен алгоритъм за големи списъци. Не зависи от някакви неудачни решения, които водят до лошо време на работа.
Има един основен недостатък в сортирането чрез сливане. Той използва допълнителната памет, която се използва за съхраняване на временни копия на списъци, преди да ги обедини. Сортирането чрез сливане обаче се използва широко в софтуера. Изпълнението му е бързо и дава отличен резултат.
Обсъдихме накратко концепцията за сортиране чрез сливане и я внедрихме както върху списък с прости цели числа, така и върху персонализирани обекти чрез ламбда функция, използвана за сравнение.