Sammanslagningssortering liknar algoritmen för snabbsortering som arbetar med konceptet dela och erövra. Det är en av de mest populära och effektiva sorteringsalgoritmerna. Det är det bästa exemplet för dela och erövra kategori av algoritmer.
Den delar upp den givna listan i de två halvorna, kallar sig för de två halvorna och slår sedan samman de två sorterade halvorna. Vi definierar sammanfoga() funktion som används för att slå samman två halvor.
Underlistorna delas om och om igen i halvor tills vi får det enda elementet var. Sedan kombinerar vi paret med ett elementlistor till två elementlistor, och sorterar dem i processen. De sorterade två elementparen slås samman till de fyra elementlistorna, och så vidare tills vi får den sorterade listan.
Sammanfoga sorteringskoncept
Låt oss se följande sammanslagningssorteringsdiagram.
Vi har delat upp den givna listan i två halvor. Listan kunde inte delas upp i lika delar det spelar ingen roll alls.
Sammanslagningssortering kan implementeras på två sätt - uppifrån och ner-tillvägagångssätt och nedifrån-upp-metoden. Vi använder uppifrån och ner-metoden i exemplet ovan, vilket är Merge-sort som oftast används.
Bottom-up-metoden ger desto mer optimering som vi kommer att definiera senare.
Huvuddelen av algoritmen är hur vi kombinerar de två sorterade underlistorna. Låt oss slå samman de två sorterade sammanslagningslistan.
- A: [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- sorterad : tom
Först observerar vi det första elementet i båda listorna. Vi tycker att B:s första element är mindre, så vi lägger till detta i vår sorterade lista och går vidare i B-listan.
- A: [ 2 , 4, 7, 8]
- B: [1, 3 , elva]
- Sorterat: 1
Nu tittar vi på nästa par av element 2 och 3. 2 är mindre så vi lägger till det i vår sorterade lista och går vidare till listan.
- A: [ 2 , 4, 7, 8]
- B: [1, 3 , elva]
- Sorterat: 1
Fortsätt den här processen och vi slutar med den sorterade listan med {1, 2, 3, 4, 7, 8, 11}. Det kan finnas två specialfall.
alya manasa
Vad händer om båda underlistorna har samma element - I så fall kan vi flytta endera underlistan och lägga till elementet i den sorterade listan. Tekniskt sett kan vi gå framåt i både underlistan och lägga till elementen i den sorterade listan.
Vi har inget element kvar i en underlista. När vi tar slut i en underlista lägger du bara till elementet i den andra efter varandra.
Vi bör komma ihåg att vi kan sortera elementet i valfri ordning. Vi sorterar den givna listan i stigande ordning men vi kan enkelt sortera i fallande ordning.
Genomförande
Algoritmen för sammanslagningssortering implementeras genom att använda uppifrån-och-ned-metoden. Det kan se lite svårt ut, så vi kommer att utveckla varje instegsdetaljer. Här kommer vi att implementera denna algoritm på två typer av samlingar - heltalselements lista (används vanligtvis för att introducera sortering) och ett anpassat objekt (ett mer praktiskt och realistiskt scenario).
Sortering Array
Algoritmens huvudkoncept är att dela upp (under)listan i halvor och sortera dem rekursivt. Vi fortsätter processen tills vi hamnar i listor som bara har ett element. Låt oss förstå följande funktion för division -
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)
Vårt primära fokus är att dela upp listan i underdelar innan sorteringen sker. Vi måste få heltalsvärdet så vi använder operatorn // för våra index.
Låt oss förstå proceduren ovan genom att följa stegen.
- Första steget är att skapa kopior av listor. Den första listan innehåller listorna från [vänster_index,...,mitten] och den andra från [mitten+1,?,höger_index] .
- Vi går igenom båda kopiorna av listan med hjälp av pekaren, väljer det mindre värdet av de två värdena och lägger till dem i den sorterade listan. När vi väl har lagt till elementet i listan och vi går vidare i den sorterade listan oavsett.
- Lägg till de återstående elementen i den andra kopian till den sorterade arrayen.
Låt oss implementera sammanslagningssorteringen i Python-programmet.
sql välj från flera tabeller
Python-programmet
# 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)> Sortera anpassade objekt
Vi kan också sortera de anpassade objekten genom att använda Pytonorm klass. Denna algoritm liknar nästan ovanstående men vi måste göra den mer mångsidig och klara jämförelsefunktionen.
Vi kommer att skapa en anpassad klass, Bil och lägga till några fält till den. Vi gör några ändringar i algoritmen nedan för att göra den mer mångsidig. Vi kan göra detta genom att använda lambdafunktionerna.
Låt oss förstå följande exempel.
Python-programmet
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)> Optimering
Vi kan förbättra prestandan för sammanslagningssorteringsalgoritmen. Låt oss först förstå skillnaden mellan sorteringen uppifrån och ner och nedifrån och upp. Bottom-up-metoden sorterar elementen i angränsande listor iterativt där top-down-metoden bryter ner listorna i två halvor.
Den givna listan är [10, 4, 2, 12, 1, 3], istället för att dela upp den i [10], [4], [2], [12], [1], [3] - vi delar upp den i underlistorna som redan kan sorteras: [10, 4], [2], [1, 12], [3] och nu är redo att sortera dem.
Merge sort är en ineffektiv algoritm i både tid och rum för de mindre underlistorna. Så infogningssortering är en mer effektiv algoritm än sammanslagningssortering för de mindre underlistorna.
Slutsats
Merge sort är en populär och effektiv algoritm. Det är en mer effektiv algoritm för de stora listorna. Det beror inte på eventuella olyckliga beslut som leder till dåliga körtider.
Det finns en stor nackdel med sammanslagningen. Den använder det extra minnet som används för att lagra de tillfälliga kopiorna av listor innan de slås samman. Men Merge sort används ofta i programvaran. Dess prestanda är snabb och ger ett utmärkt resultat.
Vi har diskuterat sammanslagningssorteringskonceptet i korthet och implementerar det både på enkel heltalslista och på anpassade objekt via en lambdafunktion som används för jämförelse.