Sortowanie przez scalanie jest podobne do algorytmu szybkiego sortowania i opiera się na koncepcji dziel i zwyciężaj. Jest to jeden z najpopularniejszych i najskuteczniejszych algorytmów sortowania. Jest to najlepszy przykład kategorii algorytmów „dziel i zwyciężaj”.
Dzieli podaną listę na dwie połowy, wywołuje siebie dla dwóch połówek, a następnie łączy dwie posortowane połówki. Definiujemy łączyć() funkcja służąca do łączenia dwóch połówek.
Listy podrzędne są dzielone raz po raz na połowy, aż do uzyskania w każdej z nich tylko jednego elementu. Następnie łączymy parę list jednego elementu w dwie listy elementów, sortując je przy tym. Posortowane pary dwóch elementów są łączone w listy czterech elementów i tak dalej, aż otrzymamy posortowaną listę.
Koncepcja sortowania scalającego
Przyjrzyjmy się poniższemu diagramowi sortowania przez scalanie.
Podaną listę podzieliliśmy na dwie połowy. Listy nie da się podzielić na równe części, to w ogóle nie ma znaczenia.
Sortowanie przez scalanie można wdrożyć na dwa sposoby - podejście od góry do dołu i podejście od dołu do góry. W powyższym przykładzie stosujemy podejście z góry na dół, które jest najczęściej używanym sortowaniem przez scalanie.
Podejście oddolne zapewnia większą optymalizację, którą zdefiniujemy później.
Główną częścią algorytmu jest sposób łączenia dwóch posortowanych podlist. Połączmy dwie posortowane listy scalone.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- posortowane: puste
Najpierw obserwujemy pierwszy element obu list. Stwierdziliśmy, że pierwszy element B jest mniejszy, więc dodajemy go do naszej posortowanej listy i poruszamy się dalej na liście B.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , jedenaście]
- Posortowane: 1
Teraz patrzymy na następną parę elementów 2 i 3. 2 jest mniejsze, więc dodajemy je do naszej posortowanej listy i przechodzimy dalej do listy.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , jedenaście]
- Posortowane: 1
Kontynuuj ten proces, a otrzymamy posortowaną listę {1, 2, 3, 4, 7, 8, 11}. Mogą być dwa szczególne przypadki.
c sformatowany ciąg
A co jeśli obie podlisty mają te same elementy? W takim przypadku możemy przenieść jedną z podlist i dodać element do posortowanej listy. Technicznie rzecz biorąc, możemy przejść dalej w obu podlistach i dodać elementy do posortowanej listy.
Na jednej podliście nie pozostał nam żaden element. Kiedy zabraknie nam podlisty, po prostu dodajemy element drugiej listy po drugiej.
Pamiętajmy, że element możemy posortować w dowolnej kolejności. Podaną listę sortujemy w kolejności rosnącej, ale bez problemu możemy także sortować w kolejności malejącej.
Realizacja
Algorytm sortowania przez scalanie jest realizowany przy użyciu podejścia z góry na dół. Może to wyglądać na nieco trudne, dlatego opracujemy szczegóły każdego kroku. Tutaj zaimplementujemy ten algorytm dla dwóch typów kolekcji - listy elementów całkowitych (zwykle używanej do wprowadzenia sortowania) i obiektu niestandardowego (scenariusz bardziej praktyczny i realistyczny).
Sortowanie tablicy
Główną koncepcją algorytmu jest podzielenie (pod)listy na połowy i posortowanie ich rekurencyjnie. Kontynuujemy ten proces, aż otrzymamy listy zawierające tylko jeden element. Rozumiemy następującą funkcję dzielenia -
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)
Naszym głównym celem jest podzielenie listy na części przed sortowaniem. Musimy uzyskać wartość całkowitą, dlatego używamy operatora // dla naszych indeksów.
Rozumiemy powyższą procedurę, wykonując następujące kroki.
- Pierwszym krokiem jest utworzenie kopii list. Pierwsza lista zawiera listy z [lewy_indeks,...,środkowy] i drugi z [środkowy+1,?,prawy_indeks] .
- Przemierzamy obie kopie listy za pomocą wskaźnika, wybieramy mniejszą wartość z dwóch wartości i dodajemy je do posortowanej listy. Gdy już dodamy element do listy i bez względu na wszystko będziemy poruszać się dalej po posortowanej liście.
- Dodaj pozostałe elementy z drugiej kopii do posortowanej tablicy.
Zaimplementujmy sortowanie przez scalanie w programie Python.
Program w Pythonie
# 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)> Sortowanie obiektów niestandardowych
Możemy również sortować niestandardowe obiekty za pomocą Pyton klasa. Algorytm ten jest prawie podobny do powyższego, ale musimy uczynić go bardziej uniwersalnym i przekazać funkcję porównania.
Stworzymy niestandardową klasę Car i dodamy do niej kilka pól. Wprowadzamy kilka zmian w poniższym algorytmie, aby uczynić go bardziej uniwersalnym. Możemy to zrobić za pomocą funkcji lambda.
Rozumiemy następujący przykład.
Program w Pythonie
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)> Optymalizacja
Możemy poprawić wydajność algorytmu sortowania przez scalanie. Najpierw zrozummy różnicę między sortowaniem przez scalanie od góry do dołu i od dołu do góry. Podejście od dołu do góry sortuje elementy sąsiednich list iteracyjnie, podczas gdy podejście od góry do dołu dzieli listy na dwie połowy.
Podana lista to [10, 4, 2, 12, 1, 3], zamiast dzielić ją na [10], [4], [2], [12], [1], [3] - dzielimy do podlist, które mogły już zostać posortowane: [10, 4], [2], [1, 12], [3] i teraz są gotowe do ich posortowania.
Sortowanie przez scalanie jest algorytmem nieefektywnym zarówno pod względem czasu, jak i przestrzeni w przypadku mniejszych list podrzędnych. Zatem sortowanie przez wstawianie jest skuteczniejszym algorytmem niż sortowanie przez scalanie w przypadku mniejszych list podrzędnych.
Wniosek
Sortowanie przez scalanie jest popularnym i wydajnym algorytmem. Jest to bardziej wydajny algorytm dla dużych list. Nie zależy to od żadnych niefortunnych decyzji, które prowadzą do złych czasów działania.
Sortowanie przez scalanie ma jedną poważną wadę. Wykorzystuje dodatkową pamięć używaną do przechowywania tymczasowych kopii list przed ich połączeniem. Jednakże sortowanie przez scalanie jest szeroko stosowane w oprogramowaniu. Jego działanie jest szybkie i daje doskonałe rezultaty.
pobierz filmy z YouTube'a za pomocą VLC
Omówiliśmy w skrócie koncepcję sortowania przez scalanie i zaimplementowaliśmy ją zarówno na prostej liście liczb całkowitych, jak i na niestandardowych obiektach za pomocą funkcji lambda używanej do porównania.