Сортирање спајањем је слично алгоритму брзог сортирања јер ради на концепту завади па владај. То је један од најпопуларнијих и најефикаснијих алгоритама за сортирање. То је најбољи пример за завади па владај категорију алгоритама.
Она дели дату листу на две половине, позива себе на две половине и затим спаја две сортиране половине. Дефинишемо споји() функција која се користи за спајање две половине.
Подлисте се изнова деле на половине док не добијемо по један једини елемент. Затим комбинујемо пар листа једног елемента у две листе елемената, сортирајући их у процесу. Сортирана два пара елемента се спајају у четири листе елемената, и тако све док не добијемо сортирану листу.
Концепт сортирања спајањем
Хајде да видимо следећи дијаграм сортирања спајањем.
Дату листу смо поделили на две половине. Списак се не би могао поделити на једнаке делове, то уопште није битно.
Сортирање спајањем се може применити на два начина – приступ одозго надоле и приступ одоздо према горе. Користимо приступ одозго надоле у горњем примеру, а то је сортирање спајањем које се најчешће користи.
Приступ одоздо према горе пружа више оптимизације коју ћемо касније дефинисати.
Главни део алгоритма је начин на који комбинујемо две сортиране подлисте. Хајде да спојимо две сортиране листе спајања.
- А : [ 2 , 4, 7, 8]
- Б : [ 1 , 3, 11]
- сортирано: празно
Прво, посматрамо први елемент обе листе. Откривамо да је први елемент Б мањи, па додамо ово у нашу сортирану листу и идемо напред на Б листи.
- А : [ 2 , 4, 7, 8]
- Б : [1, 3 , Једанаест]
- Сортирано: 1
Сада гледамо следећи пар елемената 2 и 3. 2 је мањи па га додајемо у нашу сортирану листу и идемо напред на листу.
- А : [ 2 , 4, 7, 8]
- Б : [1, 3 , Једанаест]
- Сортирано: 1
Наставите са овим процесом и на крају ћемо добити сортирану листу од {1, 2, 3, 4, 7, 8, 11}. Могу постојати два посебна случаја.
објекат на јсон у Јави
Шта ако обе подлисте имају исте елементе - У том случају, можемо померити било коју подлисту и додати елемент у сортирану листу. Технички, можемо да идемо напред у обе подлисте и да додамо елементе у сортирану листу.
На једној подлисти немамо ниједан елемент. Када понестане у подлисти, једноставно додајте елемент другог један за другим.
Треба да запамтимо да елемент можемо сортирати било којим редоследом. Дату листу сортирамо растућим редоследом, али лако можемо сортирати и опадајућом.
Имплементација
Алгоритам сортирања спајањем се имплементира коришћењем приступа одозго надоле. Може изгледати мало тешко, па ћемо детаљније разрадити сваки корак. Овде ћемо имплементирати овај алгоритам на два типа колекција – листу целобројних елемената (обично се користи за увођење сортирања) и прилагођени објекат (практичнији и реалистичнији сценарио).
Сортирање низа
Главни концепт алгоритма је поделити (под)листу на половине и сортирати их рекурзивно. Настављамо процес док не завршимо листе које имају само један елемент. Хајде да разумемо следећу функцију за дељење -
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,?,десни_индекс] .
- Обе копије листе прелазимо помоћу показивача, бирамо мању вредност од две вредности и додајемо их у сортирану листу. Једном када додамо елемент на листу и идемо напред у сортираној листи без обзира на то.
- Додајте преостале елементе у другој копији у сортирани низ.
Хајде да имплементирамо сортирање спајањем у Питхон програму.
Питхон програм
# 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)> Сортирање прилагођених објеката
Такође можемо сортирати прилагођене објекте користећи Питхон класа. Овај алгоритам је скоро сличан претходном, али морамо га учинити разноврснијим и проћи функцију поређења.
Направићемо прилагођену класу, Ауто и додати јој неколико поља. Унели смо неколико промена у доњи алгоритам да бисмо га учинили разноврснијим. То можемо урадити коришћењем ламбда функција.
јава стринг индекоф
Хајде да разумемо следећи пример.
Питхон програм
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] и сада су спремне да их сортирају.
Сортирање спајањем је неефикасан алгоритам и у времену иу простору за мање подлисте. Дакле, сортирање уметањем је ефикаснији алгоритам од сортирања спајањем за мање подлисте.
Закључак
Сортирање спајањем је популаран и ефикасан алгоритам. То је ефикаснији алгоритам за велике листе. Не зависи од било каквих несрећних одлука које доводе до лошег времена рада.
Постоји један велики недостатак у сортирању спајањем. Користи додатну меморију која се користи за чување привремених копија листа пре њиховог спајања. Међутим, сортирање спајањем се широко користи у софтверу. Његов учинак је брз и даје одличне резултате.
Укратко смо разговарали о концепту сортирања спајањем и имплементирали га и на једноставну листу целих бројева и на прилагођене објекте преко ламбда функције која се користи за поређење.