정렬 알고리즘 - Quick Sort

안녕하세요

정렬 알고리즘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

재귀는 원소 개수가 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)의 시간복잡도를 가집니다.

라고 말씀하시면 됩니다.

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

출처: http://zeddios.tistory.com/35 [ZeddiOS]