Tutorial : 퀵소트(Quick Sort 빠른정렬) timer 1s memory 512MB

[퀵소트(Quick Sort)]

퀵소트는 토니 호어(찰스 엔터니 리처드 호어 - Charles Antony Richard Hoare)가 1959년에 개발한 알고리즘이다.

원소들간의 비교와 교환을 통하여 정렬하는 비교기반정렬 알고리즘이다.

원소들 중에 같은 값이 있는 경우 정렬후에 이들의 순서가 달라질 수 있어 불안정 정렬에 속한다.

( 3을 피봇으로 하고 전통적인 방법으로 하는 예 5_1, 5_2, 3, 2, 1)

( 2_2를 피봇으로 하고 아래 설명한 방법으로 하는 예 2_1, 3, 1, 2_2)  ​

N개의 데이터를 정렬할 때, ​시간복잡도는 ​평균 O(N * logN), 최악의 경우 O(N^2) 이 소요된다.

매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다.

이때문에 비교정렬중에서는 비교적 빠른 시간복잡도를 보이며 퀵소트(빠른정렬)라는 이름의 기원이 되었다.

분할정복 알고리즘의 좋은 예중에 하나이다.

합병정렬과는 다르게 비대칭 분할이 이루어지며 분할과 정복 과정은 있으나 합병과정이 없다.

[퀵소트(오름차순) 알고리즘 프로세스]

정렬할 배열을 A[], 구간의 첫 인덱스(배열번호)를 low, 마지막 인덱스를 high 라고 하자.

1. low >= high 라면 현재 구간은 정렬된것으로 본다.

2. 분할(Dividing : Partition) 과정 :

구간내의 임의의 원소를 pivot값으로 정한다. 여기서는 pivot = A[low]로 한다.

1) pivot 이하의 값들을 배열의 왼쪽에 pivot 이상의 값들을 오른쪽에 배치시킨다.

2) pivot 의 자리를 찾아준다.

* 분할 과정을 구현하는 여러가지 방법이 있으나 여기서는 다음과 같은 방법을 사용한다.

여기에서 다루는 방법은 two pointer를 이용한 것으로 전통적인 방법이다.

(1) 두 포인터의 초기값은 i=low+1, j=high 이다.

(2) i포인터를 위(오른쪽)로 움직이면서 pivot보다 큰 값을 찾는다.

(3) j포인터를 아래(왼쪽)로 움직이면서 pivot보다 작은 값을 찾는다.

(4) i <= j 라면 두 포인터가 가리키는 값을 바꾼다.

(5) i < j인 동안 (2), (3), (4)를 반복한다.

(6) i >= j가 되면 pivot값과 j번째 값을 바꾸어 pivot의 자리를 찾아 준다.

이제 피봇을 기준으로 아래(왼)쪽에는 pivot보다 작거나 같은 값들이

위(오른)쪽에는 pivot보다 크거나 큰 값들이 위치한다.

3. 정복(Conquer) 과정 :

pivot은 정렬되어 있다. 따라서 pivot을 제외하고

pivot의 아래(왼)쪽과 위(오른)쪽을 재귀호출하여 정렬시킨다.

[퀵소트(오름차순) 의사코드]

[문제]

N개의 정수를 입력받아 퀵소트의 단계별 결과를 출력하는 프로그램을 작성하시오.

각 단계별로 분할 이후 배열 전체의 모습을 행으로 구분하여 출력한다.