병합 정렬은 분할 및 정복 개념을 기반으로 하는 빠른 정렬 알고리즘과 유사합니다. 가장 널리 사용되고 효율적인 정렬 알고리즘 중 하나입니다. 이는 알고리즘의 분할 및 정복 범주에 대한 가장 좋은 예입니다.

주어진 목록을 두 부분으로 나누고 두 부분에 대해 자신을 호출한 다음 정렬된 두 부분을 병합합니다. 우리는 병합() 두 개의 반쪽을 병합하는 데 사용되는 기능입니다.

하위 목록은 각각 단 하나의 요소를 얻을 때까지 계속해서 절반으로 나뉩니다. 그런 다음 한 요소 목록 쌍을 두 요소 목록으로 결합하고 프로세스에서 정렬합니다. 정렬된 두 요소 쌍은 네 요소 목록으로 병합되며, 정렬된 목록을 얻을 때까지 계속됩니다.

병합 정렬 개념

다음 병합 정렬 다이어그램을 살펴보겠습니다.

우리는 주어진 목록을 두 부분으로 나누었습니다. 목록은 동일한 부분으로 나눌 수 없으므로 전혀 중요하지 않습니다.

병합 정렬은 하향식 접근 방식과 상향식 접근 방식의 두 가지 방법을 사용하여 구현할 수 있습니다. 위의 예에서는 가장 자주 사용되는 병합 정렬인 하향식 접근 방식을 사용합니다.

상향식 접근 방식은 나중에 정의할 더 많은 최적화를 제공합니다.

알고리즘의 주요 부분은 두 개의 정렬된 하위 목록을 결합하는 방법입니다. 두 개의 정렬된 병합 목록을 병합해 보겠습니다.

• ㅏ : [ 2 , 4, 7, 8]
• ㄴ : [ 1 , 3, 11]
• 정렬됨: 비어 있음

먼저 두 목록의 첫 번째 요소를 관찰합니다. B의 첫 번째 요소가 더 작다는 것을 알았으므로 이를 정렬된 목록에 추가하고 B 목록에서 앞으로 이동합니다.

• ㅏ : [ 2 , 4, 7, 8]
• B : [1, 삼 , 열하나]
• 정렬됨 : 1

이제 요소 2와 3의 다음 쌍을 살펴봅니다. 2는 더 작으므로 정렬된 목록에 추가하고 목록으로 이동합니다.

• ㅏ : [ 2 , 4, 7, 8]
• B : [1, 삼 , 열하나]
• 정렬됨 : 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,?,오른쪽_색인] .
• 포인터를 사용하여 목록의 두 복사본을 모두 탐색하고 두 값 중 더 작은 값을 선택하여 정렬된 목록에 추가합니다. 목록에 요소를 추가하면 상관없이 정렬된 목록에서 앞으로 이동합니다.
• 다른 복사본의 나머지 요소를 정렬된 배열에 추가합니다.

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 &gt;= 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&apos;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(&apos;Make: {}, Model: {}, Year: {}&apos;, 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(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 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&apos;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라는 사용자 정의 클래스를 만들고 여기에 몇 가지 필드를 추가하겠습니다. 우리는 아래 알고리즘을 좀 더 다양하게 만들기 위해 몇 가지 변경 사항을 적용했습니다. 람다 함수를 사용하여 이를 수행할 수 있습니다.

다음 예를 이해해 봅시다.

파이썬 프로그램

 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(&apos;Make: {}, Model: {}, Year: {}&apos;, 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(&apos;Renault&apos;, &apos;33 Duster&apos;, 2001) car2 = Car(&apos;Maruti&apos;, &apos;Maruti Suzuki Dzire&apos;, 2015) car3 = Car(&apos;Tata motor&apos;, &apos;Jaguar&apos;, 2004) car4 = Car(&apos;Cadillac&apos;, &apos;Seville Sedan&apos;, 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&apos;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])에 추가했으며 이제 정렬할 준비가 되었습니다.

병합 정렬은 더 작은 하위 목록에 대해 시간과 공간 모두에서 비효율적인 알고리즘입니다. 따라서 삽입 정렬은 더 작은 하위 목록에 대한 병합 정렬보다 더 효율적인 알고리즘입니다.

결론

병합 정렬은 대중적이고 효율적인 알고리즘입니다. 큰 목록에는 더 효율적인 알고리즘입니다. 이는 잘못된 런타임을 초래하는 불행한 결정에 의존하지 않습니다.

병합 정렬에는 한 가지 큰 단점이 있습니다. 목록을 병합하기 전에 목록의 임시 복사본을 저장하는 데 사용되는 추가 메모리를 사용합니다. 그러나 병합 정렬은 소프트웨어에서 널리 사용됩니다. 성능이 빠르고 우수한 결과를 만들어냅니다.

우리는 병합 정렬 개념에 대해 간략하게 논의했으며 비교에 사용되는 람다 함수를 통해 간단한 정수 목록과 사용자 정의 개체 모두에서 이를 구현했습니다.