퀵 정렬 (quick sort) 알아보기

반응형

이번 포스팅에서는 퀵 정렬에 관해 알아보겠습니다. 그동안 앞에서 알아본 선택정렬, 삽입정렬, 버블정렬 등은 간단하지만 평균적으로 시간복잡도가 O(n^2) 이 소요되는 정렬 방법이었습니다. 따라서 배열의 크기가 큰 경우에는 해당 정렬 방법을 사용하기에 곤란한 경우가 많습니다. 이런 상황에서는 조금 더 빠른 정렬 방법을 사용해야 합니다. 그 중에 가장 대표적인 정렬 방법이 바로 퀵 정렬입니다. 퀵 정렬은 최악의 경우에는 O(n^2)의 시간복잡도를 갖지만 평균적으로 O(nlogn)의 복잡도를 갖기 때문에 더 빠르다고 할 수 있습니다.

 

퀵 정렬은 분할 정복 (divde & conquer) 알고리즘의 하나입니다. 다시 말해서 정렬할 배열을 더 작은 크기의 배열로 쪼개고(divide), 작은 문제를 해결하면서 점차 큰 문제로 확장해 나갑니다(conquer). 따라서 퀵 정렬에서는 재귀나 반복문 등을 활용하는 코드가 등장하게 됩니다. 분할 정복을 활용하는 다른 정렬 방법 중에 합병 정렬이 있습니다. 합병 정렬은 배열을 균등하게 절반씩 나눠서 정렬하는 반면, 퀵 정렬은 피벗(pivot)에 따라 두 배열로 나누기 때문에 보통의 경우 비균등하게 분할되는 특징이 있습니다.

 

퀵 정렬 과정

퀵 정렬의 과정을 문장으로 먼저 설명하겠습니다. 퀵 정렬에는 피벗(pivot)이라는 개념을 이해해야 합니다. 피벗이란 배열 안에 있는 한 원소로, 기존의 배열을 작은 배열 두 개로 나누기 위한 기준 값이 됩니다. 피벗을 선택하는 방법은 배열 내에 있는 값 중에 가장 왼쪽, 가장 오른쪽에 있는 원소를 선택한다거나, 랜덤하게 선택하는 방법 등 다양하게 있습니다. 어떤 방법을 선택하더라도 통계적으로 큰 차이는 없기 때문에 코드 작성시 편한 방법을 사용하면 됩니다.

 

피벗을 선택하고 나면 이 값을 기준으로 작은 값과 큰 값을 따로 모아서 저장합니다. 이렇게 나누기 때문에 쪼개진 두 배열의 크기가 균등하지 않습니다. 크기가 작아진 두 배열은 각각 다시 피벗을 선택해서 나누는 과정을 거치게 됩니다. 이것을 더이상 나눌 수 없을 때까지 반복해서 진행하는데요. 피벗을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 두었다면 자연스럽게 전체 배열이 오름차순으로 정렬되는 것을 확인할 수 있습니다.

 

구현 아이디어

그렇다면 퀵 정렬을 코드로 구현하기 위해서는 어떻게 하면 좋을지 생각해보겠습니다. 실 구현은 다음 포스팅에서 하고 이번 글에서는 아이디어 위주로 생각해보도록 하겠습니다. 분할 정복을 한다고 했을 때 기존 배열에서 쪼개진 다른 두 배열을 따로 선언해서 갖고 있는 것은 메모리 효율 면에서 좋지 못한 방법입니다. 따라서 아래와 같이 생각해보겠습니다.

 

- 피벗은 가장 왼쪽에 있는 값을 선택

- 배열의 두번째 인덱스를 가리키는 low 와 배열의 마지막 인덱스를 가리키는 high 를 정의

- low는 피벗과 값을 비교하여 더 작으면 오른쪽으로 이동

- high는 피벗과 값을 비교하여 더 크면 왼쪽으로 이동

- 위 과정을 거치고 low 와 high의 위치가 교차되지 않았다면 (low 위치 < high 위치) 해당 위치의 원소를 swap

 -- 이 부분이 제일 핵심이면서 헷갈릴 수 있을 것 같아 코멘트를 덧붙입니다. 3,4번째 단계에서 low와 high는 각자 피벗을 기준으로 더 작은지 / 더 큰지 확인하면서 이동했습니다. 이상적인 경우라면 피벗을 제외한 배열 내 모든 원소가 왼편에는 피벗보다 작은 수들이, 오른편에는 피벗보다 큰 수들이 있어서 한 번만에 low 와 high가 쭉 체크하여 서로 위치가 교차될 수 있겠지만 대부분의 경우 그렇지 못하고 중간에 멈추게 됩니다. 그럴 경우 low 의 값과 high 의 값을 서로 바꿔준 뒤에 다시 한번 위 과정을 거쳐 low 와 high 의 위치가 서로 교차될 때 까지 진행하는 것 입니다.

 

- low 와 high의 위치가 교차되었다면 high에서의 값과 피벗을 swap

- 피벗을 기준으로 왼쪽과 오른쪽을 각각 퀵 정렬 실시

 

 

분할 정복이 조금 생소한 분들이라면 퀵 정렬의 과정이 조금 난해할 수 있습니다. 위 과정을 다시 한번 천천히 곱씹어보면서 이해할 수 있다면 코드 작성도 그렇게 어렵지 않을 것입니다. 다음 포스팅에서는 이것을 실제로 구현한 코드와 결과를 확인해보도록 하겠습니다.