Divide and Conquer
입력을 나누어 더 작은 문제를 풀고
작은 문제들의 답을 조합하여 전체 문제의 답을 만든다.
아주 작은 문제는 어쨌든 풀린다.
어떻게 나누지??
Recursive Merge Sort
n log(n)
모든 것을 다 sort할 수 있는 알고리즘(Comparison Model) 중에 n log(n)는 없다.
같은 값이 있으면 먼저나온 것이 더 작다라고 하면 비교가능
가능한 n!가지 중 어느 것인지 알아낸다 = sorting
a(i) < a(j) ?
YES or NO
질문을 하나 할때마다 절반을 거를 수 있다.
절반을 거르는 질문을 하는 것이 최악의 경우에 가장 좋다.
=> log N번 질문해야 한다. = n log(n)
Why Quick Sort?
annotation상에서는 merge sort가 가장 좋다.
하지만 정확한 비교가 힘들다. 서울-부산 거리재는데 mm단위로 얘기할 필요 없다.
practice로 따지면 merge sort보다 빠른 것들이 생긴다 ex) 퀵 소트
새 배열을 할당하는게 비용이 많이 든다. (sort할때 보통 n이 크다)
머지소트를 배열 하나만으로 하려고 노력했으나 잘 안됨. 최소 2개 필요
while문의 서커스 -> 메모리를 추가할당하지 않기 위해서
p = a[0] // pivot 기준
a[0]로 꼭 안 잡아도 된다.
모든 값이 다 다르다는 가정!
추가 배열을 쓴다면 굉장히 쉬운 방법이다. 배열 하나로 해결하려고 할 뿐!
i는 p보다 큰 게 나올 때까지 계속 간다. y = 최초로 만난 p보다 큰 것
j도 p보다 작은 게 나올 때까지 계속 간다. x = 최초로 만난 p보다 작은 것
i<j일때 a[i]와 a[j]를 바꾼다. 즉, y와 x를 바꾼다.
=> p보다 작은 갯수, p보다 큰 갯수가 하나씩 늘었음
서커스가 끝나면 어딘가를 기준으로 p보다 작고 큰 곳이 나뉜다.
j가 넘어오면 끝난다. (항상 이 상태로 끝난다.)
따라서 p를 j부분으로 보낸다.
물론 pivot을 뭘로 잡느냐에 따라서 왼쪽, 오른쪽의 사이즈가 달라진다.
merge sort에서는 절반으로 잘랐지만(n log n), 퀵소트는 pivot에 따라 한쪽이 기울어질 수 있다.
pivot을 뭘로 잡을 것인가??