티스토리 뷰
퀵 정렬은 정렬을 하는 알고리즘이다. 퀵 정렬은 말의 뜻 그대로 빠른 정렬이다.
선택 정렬보다 더욱 빠를 뿐더러 실제로도 더 자주 사용되는 정렬이다.
그 예로 C언어 표준 라이브러리에서는 qsort라는 함수가 있다. 이 녀석은 바로 퀵 정렬을 구현한 함수라고 할 수 있다.
퀵 정렬에서도 분할 정복 전략(Devide and Conquer)를 적용할 수가 있다.
배열을 퀵정렬로 정렬해서 사용을 해보자. 정렬을 시키는데 필요한 가장 간단한 배열은 무엇일까?
예전에 필자가 언급했던 어드바이스를 기억하는가? 그렇다. 아예 정렬을 할 필요가 없는 정렬도 있다.
비어있는 배열, 원소가 하나인 배열.
이런 종류의 배열은 정렬할 필요가 없다.
비어있는 배열이나 원소가 하나인 배열은 배열이라는 것의 어떤 기본적인 단계가 되어준다.
이때는 배열을 그냥 그대로 반환시키면 된다. 정렬을 할 것이 없는 것이다.
def 퀵정렬(array):
if len(array) < 2:
return array
더욱 크기가 큰 배열에 대해서 생각을 해보자. 원소가 단 두개일뿐인 배열은 정렬하기 쉬운편에 속한다.
|
2 |
8 |
원소의 갯수가 3개라고해도 마찬가지이다.
지금 우리는 디바이드 앤 컨쿼 전략을 사용하고 있는 것이다. 이것을 잘 기억해 두어야 한다.
그러니까 추가적으로 말하자면 이 배열을 기본적인 어떤 상태가 될 때가지는 계속해서 나눠야 하는 것이다.
퀵 정렬의 동작은 다음과 같은 스타일로 이루어진다. 우선 배열에서 원소를 하나 선택한다. 이 원소를 기준이 되는 원소라고하여 pivot이라고 한다.
기준점이 되는 원소를 어떻게 셀렉트하는지는 추후에 설명하도록 하자. 일단은 먼저 생각해야 될 건 배열의 첫 원소가 기준원소라고 생각하는 것이다.
그렇다면 이제 모든 원소를 기준이 되어준 엘리먼트와 큰 엘리먼트로 분류를 하면 된다.
이런것을 바로 분할이라고 부른다. 그렇다면 바야흐로 이제 당신들 앞에 있는 것은 다음과 같다고 볼 수 있다.
- 기준 엘리먼트보다 작은 숫자들이 들어가 있는 아래단계의 배열
- 기준 엘리먼트
- 기준 엘리먼트보다 더욱 커다란 숫자들로 이루어진 아래단계의 배열
이 두 개의 하위 배열은 정렬이 되어 있지가 않다. 그렇지만 만약 이것들이 정렬이 되어 있다면 상황은 달라질까?
정답부터 말하자면 전체 배열을 정렬하는 것은 정말 쉬워진다는 것이다.
만약 밑에 있던 배열들이 정렬이 되어 있다면 첫번째 배열과 기준 엘리먼트 두번째 배열로 이것들을 합칠수가 있다. 그렇게 되면 전체적으로 보면 결국 정렬이 완료된 배열이 되는 것이다. 앞의 경우엔 [12, 25] + [44] + [ ] = [12, 25, 44]로 정렬된 배열이 되는 것.
그렇다면 하위 배열은 어떻게 정렬해야 할까? 일단 퀵 정렬의 기본적인 단계에서 원소의 개수가 두 개인 배열을 생각해보자. 이런 경우에는 원소가 존재하지 않는 껍데기 배열을 정렬하는것이 가장 좋다. 그러니까 일단 이 두개의 아랫단계 배열에 대해서도 퀵 정렬을 부른다음에 결국 그것을 합성하면 전체 배열이 정렬되는 것이다.
이런 정렬의 개념을 왜 알아야 할까?
근원적으로 들어가보면 결국 이런 정렬에 대한 기초가 프로그래밍에서 매우 중요하기 때문이다.
만약 이걸 제대로 알지 못한다면 언젠가 정말 고생하게 될 것이 뻔하다.
그런말이 있다면 사람을 믿지 마라, 상황을 믿어야지.
내 뇌피셜을 믿으면 안된다. 정렬과 자료구조, 알고리즘을 믿어야 한다.
뭔 그에소리인가 싶겠지만, 결국 이런것들은 반드시 필요한 메시지를 전하고 있는 것이다.
이 방법은 기준 엘리먼트가 무엇이 되더라도 결국 동작하게 된다.
25를 기준 엘리먼트로 골랐다고 할 지언정, 결국 하위 배열들은 각각 한개씩의 원소만 가지고 있을 뿐이다.
때문에 이런 배열들을 정렬하기 위해서 엘리먼트가 여러개인 배열을 정렬하는 방법도 알 수 밖에 없게 된다.
일단 기준이 되는 녀석을 고르고나서 그것보다 작은 원소, 큰 원소의 배열을 하위로 놓는다.
그러니까 말하자면 분할을 하라는 것이다.
그리고나서 하위 배열에 대해서 반복적인 재귀를 통해서 퀵 정렬을 호출해버린 그만이다.
그렇다면 만약 배열의 엘리먼트가 갯수가 5개라면 어떻게 될까?
그것은 여러분의 상상에 맡기겠다.
만약 44를 기준으로 골랐다고 가정해보자.
그렇게 되면 원소는 결국 몇개가 될까? 이런것 역시 결국 알수밖에 없는 원소의 개수가 된다.
그러니까 이미 3~4개를 정렬하는 방법을 알고 있기 때문에 그 숫자가 늘어나면 리커시브하게 처리하면 그만인 것이다.
분할정복.
모든 하위 어레이들이 이런식으로 돌아갈 것이 뻔하다. 그렇기 때문에 당신들은 퀵 정렬을 통해서 원소의 개수가 제로에서 포개의 배열을 정렬시켜 버리는 방법을 알고 있게 된다.
한마디로 어떤 엘리먼트를 기준으로 삼든지 간에 그 하위에 해당하는 배열에 재귀적으로 퀵 정렬을 때려버리면 되는 것이다.
예를들어, 기준이 되는 엘리먼트를 4라고 해보자. 그러면 다음과 같은 하위 배열에 대해서 퀵 정렬을 콜해버린다.
그러면 각 배열들이 모두 정렬이 되면 합성이 진행되게 된다. 그렇게 되면 전체 배열이 정렬되는 것이다. 이런식으로 돌아가는 배열의 정렬이 바로 퀵 정렬이다.
이렇게 원리를 파악하고 나니 그렇게 어려운 개념은 아니라는 것을 알 수 있다. 결국 기준이 되는 엘리먼트를 무엇을 고르든지간에 같은 동작방식으로 작동할 수 밖에 없다. 그렇기 때문에 그 몇개의 엘리먼트를 가졌다고해도 정렬이 가능하다는 논리가 성립하게 되는 것이다.
8개든지, 10개든지 그러한 숫자는 이제 더이상 문제가 아니다.
이런식으로 증명을 하는것이 바로 귀납적인 방식의 접근으로 인한 증명을 하는 것이다. 귀납적 증명은 알고리즘이 시키는 대로 똑바로 굴러갔는지를 증명하는 하나의 메소드이다. 이런 귀납적 추론을 할때도 결국 기본이 되는 base case와 결국 결론에 다가서게되는 inductive case 두 단계는 필요하다.
이제 슬슬 이 개념이 이해가 되기 시작할 것이다.
이것은 마차 사다리를 타거나 계단을 오르는것과 같다.
어디가 끝인지를 알 수 없지만, 일단 1층에 있으면 2층에 올라갈 수 있고, 2층에서도 마찬가지의 방법으로 3층에 올라갈 수 있다.
퀵 정렬에 있어서도 이런 매커니즘을 차용할 수가 있다. 그러니까 기본적인 단계와 귀납단계를 나눈다.
기본 단계에서 돌아가도록 증명한다.
즉 일과 이에서 증명이 되면 이와 삼에서도 동작이 가능하다고 보는 것이다.
어쨋든 이쯤되면 이 이상으로 파고들 필요는 없다. 귀납적 증명이라는것이 매우 중요할 뿐더러, 이것이 퀵정렬과 아주 밀접한 관계를 가지고 있다는것을 파악했다면 충분한 수준으로 생각할 수 가 있다.