퀵정렬 알고리즘(Quick Sort)

퀵 정렬 

퀵정렬 알고리즘은 대표적인 빠른 알고리즘으로서 '분할 정복' 기법을 활용하는 알고리즘이다. 평균적으로 O(N*logN)의 속도를 내지만 최악의 경우에는 O(N^2)의 속도를 낼 수도 있다.

 

퀵정렬은 '피벗'(pivot)이라는 하나의 값을 기준으로 큰 숫자와 작은 숫자를 교환한 후에 배열을 두 부분으로 나눈다. 

 

 

기본적인 퀵정렬은 피벗 값을 가장 왼쪽에 있는 값으로 정한다. 즉 위 데이터에서는 7로 정한다.

그 다음 피벗보다 피벗보다 큰 값을 왼쪽에서부터 찾고, 피벗보다 작은 값을 데이터의 오른쪽에서부터 찾는다. 

 

큰 값은 9, 작은 값은 4이다. 이 두 값의 위치를 교환한다.

 

다시 피벗보다 큰 값을 왼쪽에서부터 찾고, 작은 값을 오른쪽에서부터 찾는다.

이번에는 큰 값이 9, 작은 값이 6인데 두 값이 엇갈렸다. 이 경우에는 작은 값(6)의 위치와 피벗(7)의 위치를 교환한다.

그 후 데이터를 이전 피벗 값을 기준으로 두 부분으로 나눈다.

 

두 부분으로 나뉜 데이터

이제 두 부분으로 나뉘었는데, 피벗을 기준으로 보면 피벗의 왼쪽에는 피벗보다 작은 값이 오고, 오른쪽에는 피벗보다 큰 값들만이 위치해있다. 따라서, 왼쪽과 오른쪽 부분 각각에 대하여 같은 작업을 위에서 해온 순서로 재귀적으로 적용해준다면 매번 피벗을 기준으로 계속 두 부분으로 나뉘게 되고 피벗의 왼쪽에는 더 작은 수가 위치하고 오른쪽에는 더 큰 수가 오게 된다. 

왼쪽 부분의 데이터에 대해서 한번 더 작업을 수행해보자. 

 

큰 값이 없다..?

피벗은 가장 왼쪽에 있는 값인 6이다. 이보다 큰 수를 왼쪽에서부터, 작은 수를 오른쪽에서부터 찾아보면, 작은 수는 1이 있는데 큰 수는 없다..? 어떡해야 할까? 큰 수를 찾다보면 존재하지 않기때문에 인덱스가 범위를 넘어간다고 생각해보자. 

 

이렇게 된다. 결국 서로 엇갈린다고 생각하면 되는데 엇갈렸을 경우엔 작은 값과 피벗 값을 바꾸고, 피벗 값을 기준으로 두 부분으로 나누면 된다고 했다. 다시 이 부분을 진행해보면,

오른쪽이 없다.

오른쪽이 없다. 즉 6보다 큰 범위가 데이터 내에 존재하지 않는다는 것이다. 그래서 작은 범위인 왼쪽 부분만 남게 된다.

각 부분에 대하여 계속 작업을 수행해 나가다가 데이터의 갯수가 1개가 되었을 때는 재귀적인 작업을 종료하면 된다. 

 

퀵정렬에 대해서 시간 복잡도를 시각적으로 살펴보자면

 

퀵 정렬에서 각 데이터의 분할에 대해서 최선의 경우에 계속 반으로 나누어 진다고 가정 했을 때 logN만큼의 깊이로 분할이 된다.

그리고 피벗과 비교하는 선형탐색(N)을 진행하므로 N * logN 만큼의 연산을 진행한다고 볼 수 있다. 따라서 평균적으로 시간 복잡도는 N * logN이라고 생각하면 된다.

 

하지만 최악의 경우 피벗과 비교하는 작업에서 매 분할마다 최대 N 번을 탐색하고 그에따라 분할도 N번 일어난다고 생각하면(위에 분할 했을 때 왼쪽 혹은 오른쪽 중 한쪽이 없는 경우, 즉 피벗에 따라 편향적으로 분할이 일어날 경우) N^2의 시간 복잡도를 가질 수도 있다.

퀵소트의 공간 복잡도의 경우에는 logN 만큼을 가지게 된다.

 

퀵정렬이 다른 N * logN 시간복잡도의 정렬 알고리즘보다 빠르다고 여겨지는 이유는 분할하는 매 단계에서 적어도 1개의 데이터가 자기 자리를 찾게 되므로 정렬할 데이터 갯수가 줄어든다. 이런 이유로 퀵(Quick) 정렬이라는 이름이 붙게 되었다고 한다.

 

코드로 구현해본다면 다음과 같다.

 

퀵 정렬

 

이 글은 다음 아래 글과 이어집니다.

https://charlie-junbeom-94043.tistory.com/41

병합 정렬 알고리즘(Merge Sort)

 

참조

https://blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)

 

틀린 부분이 있다면 지적 부탁드립니다