[Powered by Google Translate] [병합 정렬] [롭 보덴 - 하버드 대학교 (Harvard University)] [이 CS50입니다. - CS50.TV] 병합 정렬에 대해 이야기합시다. 지금까지 당신은 버블 정렬, 삽입 정렬, 그리고 선택 정렬 봤어요. 내가 더가 무슨 뜻인지에 파도 손을 좀하더라도, 병합 정렬은 일반적으로이 3 종류의보다 더 잘 수행합니다. 

그러나 병합 정렬에 대해 얘기하기 전에,의 2 정렬 목록을 병합에 대해 얘기 해봐요. 우리는이 같은 2 정렬 목록을 복용하는 과정을 부를 그 중 하나의 정렬 된 목록을 얻고 - 목록을 병합. 우리가 어떻게이 작업을 수행 할 수 있습니까? 음, 하나의 생각은 다른 목록의 끝에 한 목록을 쑤셔하는 것입니다 다음 결과 목록을 정렬합니다. 

이 작동하지만, 그것은 불필요한 작업이 많이 있습니다. 우리는 정렬보다 더 빨리 할 수​​ 있습니다. 하나라도 잘못 생각은 단지 각 목록에서 번갈아 컵을하는 것입니다납니다. 그 처음에는 그 작품처럼 보일 수도 있지만하면, 16 23 여길 것을 통지 - 우리가 4, 8, 15, 23, 16로 결국 그래요. 이 때문 병합 목록에 연속으로 나타납니다 두 요소 같은 초기 목록입니다. 15, 16는 모두 왼쪽에있는 목록에 있습니다. 그 트릭은 두 목록이 이미 정렬되어 있다는 사실을 활용하는 것입니다. 즉, 우리는 두 목록의 첫 번째 요소를 살펴보면 - 여기, 4, 8 - 그들 중 한명은 또한 병합 목록의 첫 번째 요소 여야합니다. 음, 이유는? 이 목록은 모두 이미 정렬되어, 우리가이 목록을 결합 할 때 등 4 또는 8 중 가장 작은 요소 수 있어야합니다. 이 경우, 가장 작은이 4 그래서 우리는 4를 가져 가서 우리의 병합 목록의 첫 번째 요소 수 있습니다. 이제 우리는 첫 번째 목록의 나머지 세 요소를 병합 계속 두 번째 목록의 4 원소. 

다시 한번, 우리는 두 목록의 첫 번째 요소를보세요. 2 작은 우리의 병합 목록의 두 번째 요소 여야합니다. 이번에는, 8, 15 일까지 가장 작은은 8이며, 그래서 우리는 삽입이 우리 정렬 목록의 두 번째 요소로. 우리 둘 다 목록의 첫 번째 요소를 비교 계속 그리고 2 작은을 제거. 15 23, 15을 비교하면 작고 있도록이 우리의 세 번째 요소입니다. 지금 16 비교 23, 16 작습니다. 그래서 그런 번째 요소입니다. 

이 요소는 행에있는 동일한 목록에서 온 것을 확인할 수 있습니다. 이 이유 병합 목록 2 목록에서 다른 요소 수 없습니다. 50 23, 23을 비교하면 작은, 그래서 우리는 그런 선택합니다. 50 42 사이에 42 작습니다. 50 108 사이에 50 작습니다. 그리고 마지막으로, 우리는 그냥 108을 가지고, 그래서 목록의 마지막에 이동해야합니다. 우리가 좋은, 정렬 목록을 확인합니다. 우리가 2 목록의 첫 2 요소를 비교 때마다 우리는 병합 목록의 다음 요소를 확인할 수있었습니다. 이것은 경우 최종 목록 n은 여기에 8이다 N 번호가 포함되어 있다는 것을 의미 그러면 우리는 그 장소에있는 숫자를 모두 얻을 대부분의 N 비교에 필요합니다. 이러한 알고리즘은 선형 시간에 실행이라고합니다 하지만 여기에 대해 걱정하지 마십시오. 

합병에 대한 우리의 알고리즘을 사용하여, 우리는 빠른 병합 정렬 알고리즘을 만들 수 있습니다. 자, 우리의 목록을 다시 보자. 병합 정렬의 과정에서 2 개의 대형 단계가 있습니다. 첫째, 지속적으로 절반으로 컵의 목록을 분할 우리는 그들, 그냥 1 컵과 목록의 무리가 될 때까지. 목록 홀수가 포함되어있는 경우 걱정하지 마세요 당신은 그들 사이 완벽하게 깨끗한 몫을 할 수 없습니다. 그냥 임의로 추가 컵 인치를 포함하는 목록을 선택 자,이 목록을 분할 보자. 이제 우리는이 목록을 수 있습니다. 이제 우리는 4 목록이 있습니다. 

그리고 지금 우리는 각 목록에서 컵 8리스트를 갖추고 있습니다. 그래서 단계 1 거에요. 2 단계의 경우, 우리는 반복적으로 우리가 전에 배운 병합 알고리즘을 사용하여 목록의 쌍을 병합합니다. 108 15 병합, 우리는 목록 15, 108이 생깁니다. 50 4 병합, 우리는 4, 50이 생깁니다. 8 42 병합, 우리는 8 42 결국. 23와 16을 병합, 우리는, 16과 23이 되죠. 지금 우리의 모든 목록의 크기는 2의합니다. 4 목록의 각이 정렬됩니다 것을 확인할 수 있습니다. 

그래서 우리는 다시리스트의 쌍을 병합 시작할 수 있습니다. 15 108 4 50 병합 - 첫째 다음 108 다음 50 다음 15 4를. 8, 42 및 16, 23, 병합 우리가 처음 다음엔 다음 8, 16, 23, 42보세요. 이제 우리는 크기가 4 단 2 목록을 가지고 각각의가 정렬됩니다. 이제 우리는 이러한 두 목록을 병합합니다. 먼저 우리는 4을. 그런 다음 우리는 8보세요. 그럼 우리가 15 다음 다음 다음 다음 16, 23, 42, 50, 108을. 그리고 우리는 끝났어. 우리는 지금 정렬 목록을 수 있습니다. 그래서 정확히 어떻게 빠른가요? 기술 측면에서, 병합 정렬은 O (N 로그 N)입니다 버블 정렬, 삽입 정렬, 그리고 선택 종류의 모든 O 반면 (N ²). 당신은 곧 알게 되겠지만 사실, 당신은 정렬을 마련 할 수 없습니다 그건 일반적으로 경우에 O (N 로그 N)보다 더 수행합니다. 당신은 아직 본적이 없다면 다시 큰 O 표기법에 대해 걱정하지 마십시오. 

우리가 정말 큰 목록을 정렬하고자 할 경우 만 의미 알고 버블 정렬, 삽입 정렬, 그리고 선택 정렬 가능성이 소요될 수 있습니다 크게 이상 정렬 병합보다. 이 병합 정렬 빠르게 모든 목록에되는 것은 아닙니다 또는 특정 크기에 따라 단일 목록. 예를 들어, 삽입 정렬은 5 요소보다 작은 모든 목록에 대한 가장 빠른 정렬 될 수 있습니다. 실제로, 병합 정렬은 50 요소로 작게 목록에 일반적으로 빨라집니다. 

그러나이 추가 속도는 가격없이 오지 않습니다. 다른 종류와 달리, 어느 장소에 목록을 목록을 가지고 수정 우리가 정렬 목록을 얻을 때까지 병합 정렬은 추가적인 공간이 필요 함께이 목록을 병합합니다. 우리는 즉시 병합 목록을 저장하기 위해 통합되고있는 목록을 사용할 수 없습니다 그래도 우리가 병합 될 필요 요소를 재정의 할 수 때문입니다. 이 공간은 가격의 약간이지만, 일반적으로 불합리하지 않습니다. 그래서 병합 정렬을위한 거예요. 

내 이름은 롭 보덴 있으며,이 CS50입니다. [CS50.TV] - 및 선택 정렬합니다. [웃음] 아, 내가 제시 한 방법을 전환하기 때문에 역시 그를 맡아 요. 왼쪽의 목록입니다. 그건 오타했다. [misspoke] 내가이 일을 망쳐 놨다는 - [웃음] 내가 뭘 몰라 -