Quick Sort

1. Quick Sort란?

Quick Sort(퀵 정렬)은 배열을 정렬하는 방법 중 하나이다. 평균적으로 가장 빠른 정렬이기 때문에 퀵 정렬이라는 이름이 붙었다. 그러나 항상 퀵 정렬이 가장 빠른 것은 아니다.(정렬된 리스트에서는 오히려 오래 걸린다.)

2. 예시

위와 같은 배열을 오름차순으로 정렬하고자 한다. 이때, pivot 값을 하나 골라야 하는데, pivot을 6으로 선택하여 정렬해볼 것이다.
오름차순으로 정렬할 것이므로, 6보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 둔다.
이렇게 pivot을 기준으로 나눠진 왼쪽, 오른쪽에서도 각각 pivot을 골라 왼쪽과 오른쪽을 나누는 과정을 재귀적으로 반복하면 배열이 정렬된다.
이때 pivot을 잘 골라야 시간 복잡도를 줄일 수 있다. pivot은 해당 배열의 중간값으로 고르는 것이 좋다. 하지만 중간값을 찾기 위해서는 정렬을 해야 하기 때문에, 배열을 정렬하여 중간값을 찾고 재정렬하는 것은 시간이 낭비된다. 따라서 좋은 pivot을 찾는 방법으로 Median-of-Three rule을 사용한다. Median-of-Three rule은 배열의 첫 번째 값, 정 중앙에 있는 값, 마지막 값 중 중간값을 pivot으로 설정하는 것이다.

3. 시간 복잡도

• 최선의 경우(분할 후 왼쪽과 오른쪽의 크기가 거의 동일할 때): $O(n\log n)$
• 평균: $O(n\log n)$
• 최악의 경우(가장 작은 값이나 가장 큰 값을 pivot으로 설정했을 때): $O(n^2)$

Merge Sort

1. Merge Sort란?

Merge Sort(합병 정렬)은 배열을 정렬하는 방법 중 하나이다. 합병 정렬로 이미 정렬되어 있는 두 배열이 있을 때 이 배열을 정렬된 상태로 합병할 수 있고, 이 방법으로 한 배열을 정렬한다.

2. 예시

위와 같이 정렬된 두 배열 A, B가 있다고 하자. 이 두 배열을 오름차순으로 정렬된 상태로 배열 C에 합치고자 한다. 먼저 두 배열의 맨 첫 번째 값인 2와 1을 비교한다. 이때 더 작은 값이 1이므로, 1을 C에 넣는다.

그리고 다시 A와 B의 첫 번째 값인 2와 3을 비교한다. 이때 더 작은 값인 2를 C에 넣는다.

첫 번째 값인 5와 3 중 더 작은 값인 3을 C에 넣는다.

첫 번째 값인 5와 8중 더 작은 값인 5를 C에 넣는다.

첫 번째 값인 6과 8 중 더 작은 값인 6을 C에 넣는다.

이렇게 하면 A의 값이 모두 삭제되었으므로, C의 뒤에 B의 값들을 순서대로 넣는다. 이렇게 하면 두 배열 A, B를 오름차순으로 정렬된 상태로 배열 C에 합칠 수 있다.

위의 방법을 이용하여 한 배열을 오름차순으로 정렬할 수 있다. 먼저, 배열의 가운데에서 배열을 둘로 나눈다. 더 이상 나눠지지 않을 때까지 이 과정을 반복하고, 위의 방법을 이용하여 두 배열을 정렬된 상태로 합친다. 이 과정을 반복하면 한 배열을 정렬할 수 있다.

3. 시간 복잡도

• 평균: $O(n\log n)$
• 최악의 경우: $O(n\log n)$(최악의 경우에서는 merge sort가 quick sort보다 빠르다.)