マージ ソートは、分割統治の概念に基づいたクイック ソート アルゴリズムに似ています。これは、最も一般的で効率的な並べ替えアルゴリズムの 1 つです。これは、分割統治カテゴリのアルゴリズムの最良の例です。
指定されたリストを 2 つの半分に分割し、その 2 つの半分に対して自分自身を呼び出してから、ソートされた 2 つの半分をマージします。定義します マージ（） 2 つの半分を結合するために使用される関数。
サブリストは、それぞれ 1 つの要素だけが得られるまで、何度も半分に分割されます。次に、1 つの要素リストのペアを 2 つの要素リストに結合し、その過程でそれらを並べ替えます。ソートされた 2 つの要素のペアが 4 つの要素リストにマージされ、ソートされたリストが得られるまでこれが繰り返されます。
マージソートの概念
次のマージソート図を見てみましょう。
指定されたリストを 2 つの半分に分割しました。リストを均等に分割できませんでしたが、まったく問題ありません。
マージソートは、トップダウンアプローチとボトムアップアプローチの 2 つの方法を使用して実装できます。上の例ではトップダウンのアプローチを使用していますが、これは最もよく使用されるマージソートです。
ボトムアップのアプローチでは、後で定義するさらなる最適化が実現します。
アルゴリズムの主要な部分は、2 つのソートされたサブリストをどのように組み合わせるかです。ソートされた 2 つのマージ リストをマージしましょう。
- 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} のソートされたリストが完成します。 2 つの特殊なケースが考えられます。
通信販売トラバーサル バイナリ ツリー
両方のサブリストに同じ要素がある場合はどうなるでしょうか - このような場合、どちらかのサブリストを移動し、その要素をソートされたリストに追加できます。技術的には、両方のサブリスト内で前に進み、ソートされたリストに要素を追加できます。
1 つのサブリストには要素が残っていません。サブリスト内の を使い果たした場合は、単純に 2 番目の要素を次々に追加します。
要素は任意の順序で並べ替えることができることを覚えておいてください。指定されたリストを昇順で並べ替えますが、降順で並べ替えることも簡単にできます。
実装
マージソートアルゴリズムはトップダウンアプローチを使用して実装されます。少し難しそうに見えるかもしれないので、各ステップの詳細を詳しく説明します。ここでは、整数要素のリスト (通常、並べ替えを導入するために使用されます) とカスタム オブジェクト (より実用的で現実的なシナリオ) の 2 種類のコレクションにこのアルゴリズムを実装します。
配列の並べ替え
アルゴリズムの主な概念は、(サブ)リストを半分に分割し、それらを再帰的にソートすることです。要素が 1 つだけ含まれるリストが完成するまで、このプロセスを続けます。次の割り算関数を理解しましょう -
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)
私たちの主な焦点は、並べ替えが行われる前にリストをサブパートに分割することです。整数値を取得する必要があるため、インデックスに // 演算子を使用します。
上記の手順を次の手順で理解しましょう。
- 最初のステップは、リストのコピーを作成することです。最初のリストには、次のリストが含まれます。 [左インデックス,...,中] そして2番目から [middle+1,?,right_index] 。
- ポインタを使用してリストの両方のコピーをスキャンし、2 つの値のうち小さい方の値を選択して、並べ替えられたリストに追加します。要素をリストに追加すると、ソートされたリスト内で関係なく先に進みます。
- もう一方のコピーの残りの要素をソートされた配列に追加します。
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)> カスタムオブジェクトの並べ替え
を使用してカスタム オブジェクトを並べ替えることもできます。 パイソン クラス。このアルゴリズムは上記とほぼ同様ですが、より汎用性を高め、比較関数を渡す必要があります。
カスタム クラス 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)> 最適化
マージソートアルゴリズムのパフォーマンスを向上させることができます。まず、トップダウンとボトムアップのマージソートの違いを理解しましょう。ボトムアップのアプローチでは、隣接するリストの要素が繰り返し並べ替えられます。一方、トップダウンのアプローチでは、リストが 2 つの半分に分割されます。
与えられたリストは [10, 4, 2, 12, 1, 3] ですが、[10]、[4]、[2]、[12]、[1]、[3] に分割するのではなく、分割します。すでにソート済みのサブリスト [10, 4]、[2]、[1, 12]、[3] に追加され、これらをソートする準備が整いました。
マージソートは、小さなサブリストに対しては時間的にも空間的にも非効率なアルゴリズムです。したがって、挿入ソートは、より小さいサブリストの場合はマージソートよりも効率的なアルゴリズムです。
結論
マージソートは一般的で効率的なアルゴリズムです。これは、大きなリストに対してより効率的なアルゴリズムです。ランタイムの悪化につながるような不運な決定には依存しません。
マージソートには大きなデメリットが 1 つあります。リストを結合する前に、リストの一時コピーを保存するために使用される追加メモリが使用されます。ただし、マージソートはソフトウェアで広く使用されています。パフォーマンスは高速で、優れた結果が得られます。
マージソートの概念について簡単に説明し、単純な整数リストと比較に使用されるラムダ関数を介したカスタムオブジェクトの両方に実装しました。
ノードjsのコマンド