2021. 4. 22. 18:31ㆍ데이터 구조
오늘은 정렬 알고리즘 중에서 퀵소트(Quick Sort)에 대해 공부해보았다.
실제 많은 곳에서 사용된다는 퀵소트는 무엇이고, 어떠한 방식으로 구현이 되는지를 알아보았고,
시간복잡도와 최악의 경우, 또 그 해결법을 살펴보았다.
퀵소트(Quick Sort)란 무엇일까?
- 출처 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC
퀵소트는 분할 정복 방식을 이용한 정렬 알고리즘으로,
하나의 큰 문제를 여러 개의 작은 문제로 쪼개어 풀어나가는 것이 특징이다.
퀵소트는 아이러니하게도 시간복잡도가 최악의 경우 O(n^2)라는 매우 느린 값을 가지면서도
빠른 정렬 알고리즘이라고 알려져 있다.
또한, 특이하게 BIG-O Notation을 최악의 경우가 아닌 평균 시간복잡도인 O(nlog(n))로 나타낸다.
**평균 시간복잡도는 O(nlog(n))이다.
**Swap을 사용하는 알고리즘이기 때문에 배열에 대한 메모리만 필요하므로 공간 복잡도면에서도 우수하다. (O(n))
어떻게 그런 일이?
정답을 먼저 말하자면, 사전에 어떠한 설계를 더해줌으로써 위와 같은 최악의 경우가 나오지 않게 개선하는 것이 가능하다.
이 해결법에 대해서는 후반부에서 다루도록 하겠다.
퀵소트 알고리즘을 알아보자!
퀵소트에는 피벗(pivot)이라는, 이른바 기준점이 존재한다.
이 피벗을 선택하는 방식에 따라서도 정렬 속도가 달라질 수 있기 때문에
주의해서 선택할 필요가 있다. (마치 하이퍼 파라메터...)
피벗을 선택하는 방식은 보통 다음 4가지로 구분한다.
- 첫번째 인덱스
- 중간 인덱스
- 마지막 인덱스
- 랜덤 인덱스
퀵소트를 좀 더 쉽게 이해하기 위해서 다음 예에서는 첫번째 인덱스 방식을 사용할 것이다.
| 4(pivot) | 5(i) | 2 | 8 | 9 | 1 | 3 | 5 | 7(k) |
여기서 첫번째 인덱스를 pivot 포인터가 가르키고 있는 것이고,
pivot을 제외하고 제일 왼쪽 인덱스를 i포인터, 오른쪽 인덱스를 k포인터 라고 하겠다.
①
i포인터는 제일 왼쪽에서부터 오른쪽으로, pivot 값보다 큰 값이 나올 때까지 한 칸씩 이동한다.
k포인터는 제일 오른쪽에서부터 왼쪽으로, pivot 값보다 작은 값이 나올 때가지 한 칸씩 이동한다.
| 4(pivot) | 5(i) | 2 | 8 | 9 | 1 | 3(k) | 5 | 7 |
②
둘 다 찾았다면 i포인터의 값과 k포인터의 값을 swap해준다.
| 4(pivot) | 3(i) | 2 | 8 | 9 | 1 | 5(k) | 5 | 7 |
③
i포인터와 k포인터가 서로 교차할 때가지 ①과 ②를 반복한다.
| 4(pivot) | 3 | 2 | 8(i) | 9 | 1(k) | 5 | 5 | 7 |
| 4(pivot) | 3 | 2 | 1(i) | 9 | 8(k) | 5 | 5 | 7 |
④
서로 교차하게 되면 k와 pivot을 swap해준다.
| 4(pivot) | 3 | 2 | 1(k) | 9(i) | 8 | 5 | 5 | 7 |
| 1(k) | 3 | 2 | 4(pivot) | 9(i) | 8 | 5 | 5 | 7 |
④번까지의 과정이 끝나면 pivot을 중심으로 왼쪽은 pivot보다 작은 값들, 오른쪽은 pivot보다 큰 값들이 오게 된다.
⑤
이제 pivot을 기준으로 왼쪽 구간, 오른쪽 구간으로 나뉘고, 각 구간마다 ①~④과정을 반복한다.
| 1(pivot) | 3(i) | 2(k) |
| 9(pivot) | 8(i) | 5 | 5 | 7(k) |
**위가 왼쪽 구간, 아래가 오른쪽 구간.
⑥
더이상 pivot기준으로 나눌 수 없다면 정렬이 끝났다 볼 수 있다.
전체적인 흐름도를 보면 다음과 같은 트리형식으로 나오게 된다.
출처: https://morioh.com/p/b0deaa623ac4
단, 위의 예시는 첫번째 인덱스가 아닌 마지막 인덱스를 pivot으로 한 case이다.
최악의 경우와 대처법
위에서 간단하게 Quick Sort란 무엇인가와 어떻게 동작을 하는지 살펴보았다.
이번엔 Quick Sort가 언제 최선, 최악의 경우이고, 최악의 경우에 어떻게 대처해야 하는지를 알아보겠다.
최선의 경우
피봇을 기준으로 정확히 반반씩 나뉠 때, 최선의 시간복잡도가 나오게 된다.
이때 시간복잡도는 2 * T(n/2) + n이고, 이것은 O(nlog(n))이 된다.
최악의 경우
피봇을 기준으로 한쪽으로만 치우쳐져서 나뉘었을 때, 최악의 시간복잡도가 나오게 된다.
즉, 0개와 n-1개로 나뉘어 질 때를 말한다.
이때의 시간복잡도는 T(n-1) + n이고, 이것은 O(n^2)이 된다.
최악의 경우의 예) 정렬 또는 역정렬 되어 있을 경우.
| 1(pivot) | 2(i) | 3 | 4 | 5 | 6 | 7 | 8 | 9(k) |
이 때, 위의 ①~④과정을 거치게 되면 pivot 왼쪽으로는 아무것도 없기 때문에, 오른쪽으로만 나뉘게 된다.
| 2(pivot) | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
대처법
글 초반에 pivot을 고르는 방식에 따라 처리 속도가 달라질 수 있다고 말했다.
바로 이 pivot을 선택하는 방식을 바꿔줌으로써 위의 경우가 나올 확률을 많이 낮출 수 있다.
1. pivot을 랜덤으로 선택하는 방식
이 방식은 말 그대로 pivot 인덱스를 랜덤으로 선택하는 기법이다.
랜덤으로 선택이 됨으로써 최악의 pivot이 나올 확률이 1/n이 되며, 모든 재귀를 통합해서 1/(n^2)가 된다.
2. pivot을 중간 인덱스로 선택하는 방식
이 방식도 마찬가지로 최악의 pivot이 나올 확률을 줄여주게 된다.
이상으로 Quick Sort에 대해서 알아보고, 최악의 경우에 대한 대처법도 살펴보았다.
보통 대처법 중에 2번째 방식을 사용하여 만든다고 하니 참고하면 되겠다.
다음에 시간이 좀 되면 Quick Sort를 직접 구현해보는 시간을 갖도록 하겠다.
**사용된 이미지에 대해서 출처를 같이 적었지만 문제가 된다면 삭제하겠습니다. 메일로 연락주세요.
If you any problem with Images uploaded, Contact me by email please. I will delete it.
'데이터 구조' 카테고리의 다른 글
| [데이터 구조] 합병 정렬(Merge Sort) (0) | 2021.06.11 |
|---|