정렬 알고리즘 - Quick Sort (평균- nlogn, 최악- n^2)

안녕하세요

정렬 알고리즘1 글을 써놓고 2는 바빠서 못썼네요ㅎㅎ..

오늘은 퀵정렬만 정리해보려고 합니다. 

퀵정렬은 개념을 아예 모르시는 분들이 보면 이해하기가 처음엔 힘들어요.

그래서 그런분들을 위해 퀵정렬만!! 정리해보려고해요.

하하

정렬 알고리즘 - Quick Sort 

---

퀵정렬!!

자, 이름부터 퀵(Quick)이네요.

퀵은 다들 아시는 것처럼

뜻은

① (동작·활동 등이) (재)빠른 

②(속도상으로·걸리는 시간이 짧아서) (재)빠른

 ③(재)빨리, 신속히

입니다. 

이름부터 뭔가 빠른 정렬 알고리즘 같죠? 실제로

다른 정렬 방법에 비해 일반적으로 가장 빠른 알고리즘으로 알려져 있습니다. 

하지만!!

대상 데이터의 특징이나 데이터 크기에 따라 반드시 위 말이 맞는 것은 아닙니다. 

실제로 최악의 경우에 시간복잡도가 n^2기도 하구요.

이 글을 읽기전에 정렬 알고리즘1끝부분에 써놓은 퀵정렬에 대한 설명을 

꼭 읽고 와주세요.

그것마저 귀찮으신 분들을 위해 요약해드리면

---

 퀵정렬은 평균적으로 nlogn의 시간복잡도를 가지지만,

최악의 경우 n^2의 시간복잡도를 가진다. 

---

자, 어떤 알고리즘이길래..

제가 처음 퀵정렬을 접하시는 분들을 위해서라도

최대한 자세히 설명드리도록 하겠습니다.

퀵 정렬 (Quick Sort)

특징

1. 랜덤배열에서 빠른 정렬 속도를 보인다.

2. 피벗(pivot)을 선정하는 방법에 따라 속도가 달라진다.

3. 순열이나 역순의 경우 매우 느린 속도를 보인다.

4. 재귀함수 기반으로 구현시 복잡하게 생각될 수 있다.

시작하겠습니다. 

일단 

퀵정렬이 뭐지? 하고 찾아보시면

이런 설명을 보셨을 겁니다.

퀵정렬은 분할 정복 (Divide and conquer)을 이용하여 

정렬을 수행하는 알고리즘이다. 

분할정복..?;;

어렵게 생각하지마세요!!

분할정복은 간단히 말해서

어떤 문제가 있습니다.

이 문제는 이상태로는 해결할 수 없습니다.

그래서 우리는 이 문제를 작은 문제들로 쪼개서 

문제를 해결할 거에요.

이게 바로 분할 정복입니다.

이름 그대로 분할해서 정복해나가는 거죠.

퀵정렬이 분할정복을 이용하여 정렬을 어떻게 수행할까요?

뭔가 정렬할 데이터들을 쪼개는 것 같네요.

퀵정렬에서 알아야 할 것이 있습니다. 

바로 기준 값 인데요,

퀵정렬에서는

pivot point라고 기준이 되는 값을 하나 설정 하는데, 

이 값을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 옮기는 방식으로 정렬을 진행합니다. 

이를 반복하여 분할된 배열의 크기가 1이되면 배열이 모두 정렬 된 것입니다.

역시 글로 쓰니까 하나도 모르겠네요.

[ 4,3,7,5,2,8,1,6 ]

이 데이터들을 정렬해보겠습니다.

과정을 먼저 살펴볼까요?

1. 기준값(=Pivot)을 정한다.

(이 피봇을 선택하는데서 수행시간의 차이가 일어납니다. 밑에서 설명할게요.)

2. L은 기준값보다 작아야하며, R은 기준값보다 커야한다.

 L < 기준값 < R

3. L과 R이 만나는 자리가 기준값의 자리이다!

이까지 읽으시면 이해가 하나도 안가실거에요!

그래서 제가 동영상을 하나 만들었습니다..

00:14초 부터 보시면돼요.

이거 동영상 한번만 보시면 퀵정렬이 어떻게 이루어지는지

한번에 알 수 있습니다.

6분만 투자해보세요.

ㅊ

참고 : https://www.youtube.com/watch?v=S2c4zAGgVgI&t=169s

이해가 좀 가셨나요?

이 방법 말고도 다른 방법으로 정렬을 할 수 있습니다.

하지만 원리는 같아요.

저는 이 방법이 가장 이해하기 쉬운 것 같아서 

위 참고 동영상을 보고 따라 만들었어요.

자, 이제 정말 흥미진진한 시간복잡도를 생각해 볼때입니다.

인터넷에서 퀵소트의 시간복잡도는 O(nlogn)이라는 글을 많이 보셨을거에요.

이거는 정확히 맞는 말은 아닙니다.

( 최악의 경우 n^2의 시간복잡도를 가지므로 )

평균적으로 nlogn의 시간복잡도를 가져요.

그래서.

어떻게 이 nlogn의 평균적인 시간복잡도가 나오는지 생각해봅시다. 

n 개의 원소인 배열을 정렬할 때 걸리는 수행 시간을 T(n)이라고 합시다. 

퀵 정렬은 재귀적인 방법으로 해결하고 반 씩 나누어 

재귀 호출이 이루어지는데,

 재귀 호출이 진행하기 전에 비교에 걸리는 시간을 S(n)이라고 합시다.

 그리고 n 개인 원소를 재귀 호출 전에 비교하는 횟수는

 n번이므로 S(n)=n입니다.

T(n) = 2*T(n/2) + n = n^2T(n/n^2) + 2*n = … = h*n
-> T(n) = 2*T(n/2) + n = 2^2T(n/2^2) + 2*n = 2^hT(n/2^h) + h*n = h*n 

재귀는 원소 개수가 1보다 작으면 탈출하므로 n^h =1 일 때 더 이상 재귀 호출은 발생하지 않습니다.

h = logn이므로 T(n) = nlogn

자, 왜 nlogn인지 아시겠나요?

하나도 모르시겠다구요?

예를 들어서 설명드릴게요. 

 31개의 요소들을 대상으로 퀵 정렬이 진행된다고 가정해봅시다.

피벗이 가장 이상적인 중간 값으로 결정된다고 가정을 한다면

첫 번째 분할에서 15개씩 둘로 나뉘게 됩니다.

그리고 두 번째 분할에서 각각 7개씩 나뉘어 총 4개의 영역으로 구분됩니다.

이 영역은 또 다시 3개씩 나뉘어 총 8개의 영역으로 구분되며

최종적으로 1개씩 나뉘어 총 16개의 영역으로 나뉘게 됩니다.

 

총 네 번의 분할 과정이 진행됩니다.

즉, 분할 횟수를 k라고 가정할 때, 요소들의 개수 n과 k는 다음과 같은 식으로 표현할 수 있습니다.

자, 이것을 요소들의 개수 만큼 진행하므로 n을 곱해줘야겠죠?

최종적으로 퀵정렬의 연산 횟수는

이 되게 됩니다!!

그러면 최악의 경우는 어떤 경우일까요?

바로 피봇을 최솟값이나 최댓값으로 선택한 경우입니다.

[1,2,3,4,5,6,7,8]

이라는 정렬된 배열이 있다고 생각해봅시다.

이때, 1 또는 8을 기준값으로 선택해봅시다.

먼저, 1을 기준값으로 선택하여 위 동영상과 같이 퀵정렬을 진행하면

어떻게 될까요?

L은 1에, R은 8에 위치할 것입니다.

8부터 1과 비교하겠죠?(n번)

하지만 모든 데이터가 1보다 큽니다.

L은 움직이지도 않고 R이 L에게로 와 

1은 다시 자기자리로 들어갈 것입니다.

이제 1은 정렬이 끝났으니 2를 기준값으로 하겠죠?

또 위와같은 상황이 발생하게 되어 2역시 자기자리로 돌아가게 됩니다.

.

.

.

이 과정을 배열안에 있는 데이터의 수(n)만큼 진행하게되고 

매번 n-1개의 데이터들과 비교하게됩니다.

그러므로 최악의 경우에는 O(n^2)이 되는 것이죠.

아니 그럼;;왜 퀵소트야....;

최악의 경우가 n^2으로 빠르지는 않다고 볼 수 있는 시간복잡도를 

가졌는데 말이죠..

왜일까요?

먼저 최악의 시간복잡도인 O(n^2)이 나오는 상황은

데이터들이 정렬되어있거나 역순으로 정렬되어 있을 때 뿐입니다.

보통 정렬된 상태로 데이터를 주지 않을 뿐더러

랜덤하게 주어진 자료가 오름차순 또는 내림차순으로 제공될 확률을 계산해보면

2/n!이어야 하고 

자료의 크기가 10개정도만 되어도 이런 식으로 자료가 주어질 확률은 

거의 불가능에 가깝게 됩니다.

특히, O(n log n)의 복잡도를 가지는 다른 정렬알고리즘 보다도 

더 빠르게 수행된다는 것이 증명되었습니다.

 

이러한 이유는 불필요한 데이터의 이동을 줄이고 

먼 거리의 데이터를 교환할 뿐만아니라, 

한번 결정된 기준은 추후 연산에서 제외되는 성질을 가지기 때문이에요.

위에서 말했듯이 시간복잡도가 n^2이 나올확률은 극히 적기때문에,

평균적으로 퀵정렬의 시간복잡도는 nlogn이다.

라고 말하는 거에요.

하지만 함정에 빠지시면 안됩니다.

그럼 퀵소트는 평균적으로 O(nlogn)의 시간복잡도를 가지네요!!

----> 이렇게 말씀하시면 안됩니다. O는 최악의 수행시간을 나타낼 때 사용하는 표기법이니까요.

앞 정렬알고리즘1 글에서도 말씀드렸다시피 

퀵소트에 대한 시간복잡도는

평균복잡도는 nlogn이지만 최악의 경우엔 n²이므로,

 빅오표기법으로 표현한다면 시간복잡도는 O(n²)입니다.

만약, nlogn의 시간복잡도로 말하고싶다면,

Θ(세타)(nlogn)의 시간복잡도를 가집니다.

라고 말씀하시면 됩니다.

이 글이 퀵소트를 이해하는데 도움이 되었으면 좋겠어요!!🙏