CS50 2019 (11)merge sort

===

www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)

1.컴퓨팅사고

2.C언어

3.배열

4.알고리즘

5.메모리

6.자료구조

 

=====================

8)병합 정렬

 

▽동영상, 텍스트, pdf 전부 봐도 이렇게 할거면 처음에 8개를 4개 4개로 나눴을 때 병합하면 되는거 아니야? 두 배열중에 가장 작은 값을 앞에다두는거면. 에 대한게 해결이 안됨. 저게 안되는 원리와 그 성능 잴 때 n이 정확히 뭔지 알아야 이해가 될 듯

 

===

영상 강의 설명

 

재귀를 활용한 정렬 알고리즘! 병합 정렬, merge sort

버블이나 선택보다도 뛰어난 알고리즘

이렇게 생겼다

입력으로 어떤 정보의 배열이 주어졌을 때 이렇게 동작

 

받은 입력에 항목이 하나라면 그냥 반환

: 이미 정렬된거잖아 순서가 틀린 게 없으니, 시작점, 가장 단순한 경우라서 하드코딩 할 수밖에 없다, 이런 상황에는 이렇게 하라고 명시적으로 적어야한다

 

다른 경우

  우선 왼쪽 절반을 정렬하고

  오른쪽 절반을 정렬한 뒤

  짜깁기를 하듯이 하나의 배열로 합친다

 

merge sort는 3단계이다

  왼쪽 정렬

  오른쪽 정렬

  이 두 배열의 병합

 

높이 h-1 피라미드와 시작점을 출력하면 끝인 것 처럼 마법이다

 

===

입력으로 주어진 것 : 7 4 5 2 6 3 8 1

 

왼쪽 절반 : 7 4 5 2 

을 정렬하려면 병합정렬이니까 왼쪽 정렬, 오른쪽 정렬, 정렬 병합.

 

그럼 또 왼쪽 절반인 7 4를 정렬,

크기가 2인 배열은? 아직 교환하지 않음. 왼쪽 정렬, 오른쪽 정렬, 정렬 병합 임.

 

아무것도 하지 않고 있는데 정렬중이래 하여튼 계속 해보면

 

왼쪽 절반은 7이다 크기가 1인 정렬은? 이미 된것. 반환해서 이 과정을 영원히 반복하지 않게 함.

다음은? 오른쪽 정렬 4니까 이미 된것. 반환

이제 흥미로운, 세번째 과정 정렬 병합, 크기 1의 배열 2개를 합침

메모리를 하나 추가해서 합치는데 병합과정은 4 가 앞이고 7이 뒤임

병합이란 두 배열 중에서 가장 작은 값을 꺼내 다른 배열(처음엔 빈 배열인가봄 메모리 추가(아랫줄)해서 하나 더 만든 그거)의 가장 작은 값 다음에 두는 과정을 말함

 

여기서 다시 떠올려보면 두번 째 과정은?방금 왼쪽 절반을 정렬했으니 오른쪽 절반을 정렬해야함

 

그럼 오른쪽은? 5 2 이고, 왼 끝 오 끝 병합 2가 먼저 오고 5가 다음에 옴

방금 오른쪽 절반을 정렬 했으니, 이제 병합!

 

4 7 // 2 5 두개의 배열을 어떻게 바른 순서로 병합?

병합이 두 배열 중에 가장 작은 값을 꺼내 다른 배열의 가장 작은 값 다음에 두는 과정이니까

2, 4, 5, 7이 됨

이렇게 원래 배열의 왼쪽 절반을 정렬함

 

이제 왼쪽 정렬이 끝남. 두번째 과정은? 오른쪽 절반을 정렬

그 다음은? 메모리를 조금 더 사용해서 두 배열을 합침

한 쪽 배열에서 연달아 2개 먼저 나온거 맞음

1 2 3 4 5 6 7 8이 됨

 

사실 제가 한 것은 크기 8의 배열을 쪼개서 어느 순간 크기 1의 배열 8개를 만든것임

그 다음에는 크기가 2인 배열 4개로 만들고

그 다음에는 4인 배열 2개

결과적으로 크기 8인 하나의 배열로 합침

그림에서 패턴을 보면아래에서 위로 올라가는데가장 아래 배열이 하나 있고절반으로 나누고 그걸 다시 나누고 그걸 다시 나눴다

 

===

첫 주부터 매번 무언가를 계속해서 절반으로 나눌 때 이 과정을 설명하는 수식이나 함수가 뭐가 있었죠? 로그  --첨듣는데요?

 

CS50에서 혹은 어떤 알고리즘을 얘기할 때 무언가를 절반으로 계속 나눈다면 로그함수로 표현할 수 있다

 

크기 8인 배열을 쪼개서 크기 1인 배열 8개로 만드는데 필요한 과정은 밑이 2인 log n 입니다, 대략 log n 이라 하죠

저 그림의 높이가 log n 이지만 수학에 대해 너무 깊이 다룰 필요는 없습니다

 

쪼개는 과정이 한 번 있을 때마다 합치는 과정이 있었습니다. 세번 째 과정으로 가장 중요합니다

병합을 할 때마다 4개와 4개, 또는 2+2+2+2 또는 1+1+...+1 하며 총 8개의 항목을 합쳤습니다.

즉 n개의 모든 항목을 확인합니다

 

이 그림처럼 8개, 혹은 n개가 있다고 하면

높이는 log n --나눌 수 있는 횟수가 log n 번이기 때문

 

그렇다면 병합 정렬의 실행 시간은?? n 곱하기 log(n)

n개의 숫자를 다시 합쳐야 하는데 log(n)번 반복됨, 이게 과정을 반복하는 횟수 log 2 8 = 3

▽첫째줄 에서 둘째줄로 갈 때 한번, 둘 셋 두번, 셋 넷 세번 해서 세번인것

 

어떻게 이렇게 계산이 되는지는 그저 받아들여야 하는 또 다른 부분이지만

중요한 것은 이 알고리즘은 근본적으로 더 빠르다는 겁니다

병합정렬은 중간인 n log n에 놓인다(▽아래로 갈수록 성능이 좋은 것)

log n은 n보다 조금 작은 값이므로 n log n은 n보다 크고 n^2보다 작다

 

최선의 경우 병합 정렬은? = 오메가는?

버블 정렬 처럼 더이상 교환이 일어나지 않을 때 멈추는 최적화 기법은 없다

항상 왼 오 정렬 뿐 따라서 마찬가지임

저기의 bubble sort는 두번째 버전의 버블정렬이었고(교환이 일어나지 않을 때 멈추는)

좋은 경우 n번 만에 가능했다

 

병합 정렬의 장점과 단점인것. 최선의 경우에 시간을 낭비하고, 최악의 경우에 훨씬 빠르다

->컴퓨터 과학에서 자주 일어나는 일. 공짜는 없다. 상한선을 개선해야 한다면 하한선을 희생해야 할 수도 있다

 

===

이 수업에서 배울 마지막 그리스문자로

어떤 알고리즘의 상한선과 하한선이 같을 때 Theta 표기법을 사용하면 됩니다

선택정렬과 병합정렬에 적용할 수 있다

 

선택정렬은 맹목적으로 가장 작은 값을 계속해서 찾기 때문에 느렸다

병합정렬도 맹목적으로 같은 알고리즘을 반복, 정렬이 돼 있는 입력값이어도 상관없다

 

===

이러고 나머지 시간에 세개의 같은 입력에 대한 각 알고리즘의 실행을 시각화 자료로 보여주고 끝,

알고리즘을 만들 때 우리의 목표는 정확성 뿐만 아니고 well design as well

선택

병학

버블 순서

 

와 진짜 빠르다 특히 병합, n log n과 n^2차이

--원리가 뭘까? 메모리를 어서 배워야?

 

===

텍스트 설명

 

병합 정렬

지난 단원에서 다양한 정렬 방법에 대해서 배웠습니다.

하지만 우리가 아직 공부하지 않은 대표적인 정렬 방법이 하나 더 있습니다.

전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 공통점이 있는 방법인 병합 정렬(합병 정렬)이 있습니다.

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.

그리고 이 과정은 재귀적으로 구현되기 때문에 나중에 재귀를 학습하면 더 이해하기 쉽습니다.

마찬가지로 다음 숫자들을 오름차순으로 정렬해 보겠습니다.

 

7 4 5 2 6 3 8 1

 

먼저 숫자들을 반으로 나눕니다.

 

7 4 5 2 | 6 3 8 1

 

그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눠봅니다.

 

7 4 | 5 2 | 6 3 8 1

 

마지막으로 한 번 더 나눠봅니다.

 

7 | 4 | 5 2 | 6 3 8 1

 

이제 숫자가 두 개 밖에 남지 않았으므로 더 이상 나누지 않고, 두 숫자를 다시 병합합니다.

단, 이 때 작은 숫자가 먼저 오도록 합니다. 4와 7의 순서를 바꿔서 병합하는 것이죠.

 

4 7 | 5 2 | 6 3 8 1

 

마찬가지로 5 2 부분도 반으로 나눈 후에 작은 숫자가 먼저 오도록 다시 병합할 수 있습니다.

 

4 7 | 2 5 | 6 3 8 1

 

그럼 이제 4 7과 2 5 두 개의 부분들을 병합하겠습니다.

각 부분들의 숫자들을 앞에서 부터 순서대로 읽어들여 비교하여 더 작은 숫자를 병합되는 부분에 가져옵니다.

즉, 4와 2를 먼저 비교해서 2를 가져옵니다. 그 후에 4와 5를 비교해서 4를 가져옵니다.

그리고 7과 5를 비교해서 5를 가져오고, 남은 7을 가져옵니다.

 

2 4 5 7 | 6 3 8 1

 

이제 남은 오른쪽 4개의 숫자들도 위와 동일한 과정을 거칩니다. 

 

2 4 5 7 | 1 3 6 8

 

마지막으로 각각 정렬된 왼쪽 4개와 오른쪽 4개의 두 부분을 병합합니다.

2와 1을 비교하고, 1을 가져옵니다. 2와 3을 비교하고, 2를 가져옵니다. 4와 3을 비교하고, 3을 가져옵니다.

4와 6을 비교하고… 이 과정을 병합이 끝날때까지 진행하면 아래와 같이 정렬이 완료됩니다.

 

1 2 3 4 5 6 7 8

 

전체 과정을 요약해서 도식화해보면 아래와 같습니다.

 

7 | 4 | 5 | 2 | 6 | 3 | 8 | 1 → 가장 작은 부분 (숫자 1개)으로 나눠진 결과입니다.

4   7 | 2   5 | 3   6 | 1   8 → 숫자 1개씩을 정렬하여 병합한 결과입니다.

2   4   5   7 | 1   3   6   8 → 숫자 2개씩을 정렬하여 병합한 결과입니다.

1   2   3   4   5   6   7   8 → 마지막으로 숫자 4개씩을 정렬하여 병합한 결과입니다. 

 

이러한 방법을 ‘병합 정렬’ 이라고 합니다.

 

병합 정렬 실행 시간의 상한은 O(n log n) 입니다.

숫자들을 반으로 나누는 데는 O(log n)의 시간이 들고, 각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문입니다.

실행 시간의 하한도 역시 Ω(n log n) 입니다. 숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문입니다.

 

===

pdf 설명