퀵 정렬 Quick Sort

선택, 버블, 삽입 정렬 알고리즘들은 시간복잡도가 평균 O( N^2)였으며

이러한 알고리즘들은 정렬할 데이터의 수가 10만이 넘어가면 

너무나 많은 연산이 요구되므로 사용하기 어렵다.

이에 반해 분할 정복 알고리즘 중 하나인 퀵 정렬알고리즘은 평균 시간복잡도가 O( N * logN )이다

퀵 정렬은 불안정 정렬에 속하며 다른 원소와 비교하는 것만으로

정렬을 진행하기 때문에 비교정렬이라도고 할 수 있다.

* 분할 정복의 의미* 

하나의 큰 문제를 2개의 문제로 분리하여 각각 해결한 뒤

다시 그 결과를 합하여 원래 문제를 해결하는 것을 의미한다.

퀵 정렬의 원리는 특정한 값을 기준으로 두 개의 비균등한 크기로 나누고

나눈 부분리스트를 정렬한 뒤 다시 합하여 정렬된 리스트를 만들어내는 정렬이다.

여기서 특정한 기준이 되는 값을 피벗(Pivot)이라고 부른다.

---

이제 그 과정을 한번 살펴보도록 하겠다.

1 4 10 8 6 9 2 7 3 5 

위와 같은 숫자들이 있다고 하고 이를 퀵 정렬을 이용하여 정렬해보겠다.

퀵정렬을 할 때 일반적으로 제일 앞에 있는 수를 피벗 값으로 잡는다.

1 4 10 8 6 9 2 7 3 5 

'왼큰오작'로 진행된다!!

1보다 큰 숫자를 왼쪽에서 부터 찾고 1보다 작은 숫자를 오른쪽에서 부터 찾는다.

10이라는 숫자를 찾을 수 있었지만 1보다 작은 수는 찾을 수 없었다.

이렇게되면 자기자신을 작은 값으로 고르게 되므로 작은 값은 1이된다.

작은수 1이 큰 수 10보다 왼쪽에 있으므로 이는 엇갈렸다고 말할 수 있다.

그러므로 피벗과 작은값 즉, 1과 1을 바꾸게된다.

여기서는 자기자신끼리 바꾼 것이므로 당연히 변화가 없다. 

 

그러므로 아무런 변화가 없으며 이 때는 피벗 값인 1의 왼쪽에는 1보다 작은 값들이

존재하는 것이며 오른쪽에는 1보다 큰 값들이 존재하게 된다.

왼쪽에는 아무것도 없으므로 무시하고 1을 기준으로 오른쪽 배열의 퀵정렬을 진행하면 된다.

이제 다시 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 진행하게 된다.

1 4 10 8 6 9 2 7 3 5

오른쪽 배열에서의 피벗값은 4가된다. 이제 4보다 큰 값을 왼쪽에서부터 찾고 작은 값을 오른쪽에서부터 찾는다.

큰 값으로 10을 찾을 수 있엇고 작은 값으로 3을 찾을 수 있었다.

찾은 두 수의 자리를 바꾸어준다. 

1 4 3 8 6 9 2 7 10 5

이제 다시 4보다 큰값을 왼쪽에서부터 찾고 작은 값을 오른쪽에서 부터 찾는다.

큰 값으로 8,  작은값으로 2를 찾았고 이 둘을 바꾸어준다.

1 4 3 2 6 9 8 7 10 5

역시 아까의 과정을 반복한다. 하지만 아까와 다른 점이 생겼다. 

보통 작은 값은 오른쪽에 큰값은 왼쪽에 있었는데

지금은 그 둘이 엇갈리게 되었다. 

이렇게 엇갈리게되는 경우 작은 값과 피벗 값을 바꾸어주면된다.

1 2 3 4 6 9 8 7 10 5

이제 이렇게 되면 아까 제일 위의 1에서 처럼

4를 기준으로 왼쪽으로는 4보다 작은 수들이 배열되어있고

오른쪽으로는 4보다 큰 수들이 배열되어있게된다.

이제 4를 기준으로 왼쪽의 피벗은 2 오른쪽 피벗은 6으로 정렬을 진행하면 정렬이 완성된다.

1 2 3 4 6 9 8 7 10 5

피벗이 2인 배열부터 진행해보면 왼쪽부터 큰 것을 찾고 오른쪽부터 작은 것을 찾는다.

왼쪽부터 큰 값은 3인데 작은 값은 없다. 그러므로 자기자신을 작은 값2로 고르게 되므로 2와 2를 바꾸게 된다.

1 2 3 4 6 9 8 7 10 5

위와 마찬가지의 이유로 3 또한 그대로가 된다.

1 2 3 4 6 9 8 7 10 5

오른쪽의 배열을 정렬해보자

왼쪽에서 큰 값이 9 오른쪽에서 작은 값이 5이므로 둘의 자리를 바꾼다.

1 2 3 4 6 5 8 7 10 9

이번에는 큰 값이 8 작은 값이 5인데 엇갈려버렸으므로 작은 값 5와 피벗 값을 바꾼다.

1 2 3 4 5 6 8 7 10 9

역시 작은 값과 바꾼 피벗 값 6을 기준으로 왼쪽은 6보다 작은 수들이

오른쪽엔 6보다 큰 수들이 존재한다. 역시나 피벗 값을 잡고 다시 정렬을 진행하면 된다.

왼쪽의 1 2 3 4 5의 경우 이미 정렬이 되어있으나 빼놓고 할 수는 없으므로

다시 정렬을 시도한다. 하지만 이미 정렬이 되어있으므로 비교 시 항상 엇갈려

작은 수는 피벗 자기 자신이 될 것이고 결국 작은 수와 피벗의 교환이므로 변화는 없다.

.

.

.

.

1 2 3 4 5 6 7 8 9 10

위와 같은 진행을 반복하면 정렬이 완성된다.

---

이러한 정렬이 빠른 이유는 쉽게 생각해볼 수 있다.

1 4 10 8 6 9 2 7 3 5 

10개의 숫자를 정렬하려고 했을 때 이전에 배운 선택이나 버블, 삽입정렬의  경우 평균적으로 

N^2 = 10*10 = 100 

하지만 퀵정렬의 경우 분할하기 때문에

1 4 10 8 6 = 5^5 = 25

9 2 7 3 5 = 5^5 = 25

25 + 25 = 50 

50 밖에 되지 않는다.

위와 같은 원리로 각자 정리 후 더한다고 생각해보면 당연히 훨씬 더 빠르다는 것을 알 수 있다.

---

하지만 이러한 퀵정렬은 이미 거의 다 정렬된 경우에는 분할 정렬의 이점을 살릴 수가 없다.

최악의 경우 시간복잡도가 O(N^2)가 된다.

 1 2 3 4 5 6 7 8 

위와 같은 숫자들이 있다면 1을 피벗으로 잡고 진행하더라도 큰 수는 찾을 수 있으나

작은 수는 없으므로 자기자신이 되어 엇갈리게된다. 그러므로 1만 정렬이 될 것이고

고작 1 하나만 정렬이 되고 큰 값만 7개가 남는다. 역시나 다음으로 2를 진행하더라도

2만 정렬될 뿐 큰 값만 6개가 남게되므로 분할 정렬의 이점을 살릴 수 없는 예시가 된다.