[알고리즘] 과제 3. Tony Hoare :: QuickSort 논문 해석하기

QuickSort 논문 brief

Part One: Theory

이 sorting은 두 개의 간단한 보조문제로 나뉘어 해결될 수 있는데, 각 문제는 이미 알려진 방식으로 풀 수 있다.

Partition

: key값을 dividing line에 따라 위 아래로 나누어 이분하는 것

실제로 이 dividing line은 흔치 않고, 있다 할지라도 찾기 힘든데 dividing line이 존재하고 그것의 위치만 안다면 item들을 재정렬하기는 쉬워진다.

partition 과정

1. 정렬되어야하는 아이템의 키 중 특정 키를 고른다.

   이 키는 bound 라 불린다.

2. dividing line 아래에는 bound보다 작거나 같은 key값이, 위쪽에는 큰 key 값이 오게 한다.

   dividing line의 위치는 미리 알 필요 없이 정렬 마지막에 드러날 것임

   1. 두 개의 포인터 (lower pointer, upper pointer)가 각각 위로, 아래로 움직인다.

   2. 먼저 lower pointer가 위로(주소가 low => high) 움직이면서 bound보다 큰 값을 찾는다.

   3. 찾으면 upper pointer가 아래로(주소가 high => low) 움직이면서 bound보다 작은 값을 찾는다.

   4. 두 포인터가 가리키는 값을 바꿔준다.

   5. lower pointer가 가리키는 주소가 upper pointer가 가리키는 주소보다 높을 때까지 반복한다.

      이 때 두 포인터의 사이가 dividing line이다.

문제

1. 모든 key value가 같을 때

2. bound가 제일 작거나 제일 큰 값으로 결정되었을 때

   dividing line이 section 밖에 위치함

3. bound 값은 올바른 자리에 있다고 생각할 수 있으므로, 나머지 값에 대해 진행하면 된다.

dividing은 segment가 하나 또는 0개의 아이템을 가지고 있을 때까지 진행

Quicksort

partitioning 후에 두 개의 segment가 나온다.

sort 하기 전 조건

크기가 적당히 커야한다.

1. segment 중 길이가 1이하인 것이 있으면 무시하고 다른 segment만 신경 쓴다.
2. 컴퓨터의 특성에 따라 다르지만 일반적으로 3~4개의 item이 segment에 있으면, 적은 수의 item을 정렬하는 다른 알고리즘을 쓰는 것이 좋다.

sorting

한 segment를 먼저 정렬한다.

그 동안 다른 segment의 첫번째, 마지막 요소는 저장되어있어야한다.

전체 item 갯수가 정렬되고 있는 item 갯수에 비례하기 때문

data 저장은 pointer가 가리키는 연속적인 블록에 저장하는 nest라는 방법을 이용한다.

계속해서 정렬할 segment를 선택하는 동안 나중에 할 블록을 큰 것으로 남겨두는 것이 좋다.

Estimate of Time Taken

N개의 아이템을 segment로 partitioning하기 위해 필요한 비교의 횟수는 bound를 정하는 메소드와 partition 과정을 완성하는 메소드에 달려있다. 어떤 케이스 건 비교의 횟수는 N+k 형태로 나타나지는데 k는 -1,0,1,2 인 경우가 대부분이다.

키 값을 바꾸는 횟수는 상황마다 다양하므로 예상되는 수치가 주어져야한다.

bound 값은 section에서 랜덤으로 취해져야함이 가정되어야 한다. 자연적으로 정렬이 되어있는 section도 랜덤으로 bound를 골라내서 무작위성이 보장되어야한다.

bound가 segment에서 r번째로 큰 값이라고 가정할 때, 우리는 r에 대한 함수로 예상값을 나타낼 수 있다. 조건부 예측이 그 조건의 확률과 곱해져서 더해지면 이것은 확실한 예측값이 된다. 모든 랜덤 예측해서 조건의 확률은 똑같이 1/N이다. 따라서 r값에 대해 주어진 예상값을 N으로 나누어주면 우리는 확실한 예측값을 구할 수 있다.

partition 과정의 마지막에서 bound가 r번째로 큰 key값일 때, 이 아이템은 r번째 자리를 차지하고 있을 것이고 r-1개의 아이템이 그 아래를 차지하고 있을 것이다. bound보다 클 확률은 (N-r-1)/N이고 따라서 r-1개의 아이템이 가질 예상값은 (N-r-1)(r-1)/N 이다. 모든 r에 대해서 이 값을 더하고 N으로 나누면 N/6+5/(6N) 이다.

이러한 형태로 나타내면 항상 partitioning에 필요한 시간은 aN + b + c/N 의 꼴로 항상 나타낼 수 있다. (a,b,c는 루프 횟수에 따라 결정된다.)

최종 식

결국 처음에 하나의 r값을 bound값으로 지정하였다면, N개의 아이템을 정렬하는 시간은 N개의 아이템을 partitioning하는 시간 + r-1개의 더 작은 아이템을 정렬하는 시간 + N-r-1개의 더 큰 아이템을 정렬하는 시간이다. 따라서 식으로 나타내면

Tn = Tr + Tn-r + aN + b + c/N 이다.

따라서 이 식을 모든 가능한 r에 대하여 N으로 나눈 후 더하면

이러한 식이 나온다. (M은 bound까지의 갯수)(?)

타당성 증명

이 해결책의 타당성은 해당 식이 원래 식과 일치하는지 판단함으로써 얻어진다. 각 계수들은 따로 생각할 수 있으므로 먼저 a의 타당성에 대해 알아보자.

*a의 타당성

Wn을

이라 표현하고 Vn을 Tn에서 a의 계수로 생각했을 때,

 

Vn

로 나타낼 수 있다.

M이 2이고 a=1, b=c=T1 =0이라고 가정했을 때, N이 굉장히 크면 가장 큰 항을 제외하고는 무시할 수 있으므로 비교의 횟수는

로 나타낼 수 있다.

전체 entropy가 logN!일 때, binary 비교하는 entropy가 log 2이기 때문에 비교횟수의 최소 횟수는

이러하다.

Quick sort의 비교 평균 횟수는 2ln2~1.4라는 factor에 의해 이론적인 최소 횟수보다 크며 이 factor는 bound의 선택에 따라 달라질 수 있다.

합병 정렬과의 비교

Part Two: 실행

Quick sort는 여러가지 변수에 의해 유연하게 복잡도가 변한다.

1. 컴퓨터의 특성
2. a,b,c,M(계수)의 값

partition without exchange

bound의 값을 다른 메모리 공간에 저장해두고, 낮은 쪽의 pointer는 올라오면서 bound보다 큰 값을 발견하면 높은 쪽의 pointer가 가리키고 있는 위치로 복사하고 높은 쪽의 pointer는 내려오면서 bound보다 작은 값을 발견하면 낮은 쪽의 pointer가 가리키고 있는 위치로 복사한다.

이 과정은 두 pointer가 같은 아이템을 가리킬 때까지 진행된다. 그리고 다른 메모리 공간에 저장해뒀던 bound 값을 그 위치에 저장한다.

이 copy 과정의 횟수는 exchange 횟수의 정확히 2배이다.

Cyclic Exchange

한번의 교환에 많은 과정을 수행하는 것이 더 경제적이다. 읽고 교환하고 쓰는 3N의 과정이 N번의 exchange 동안 수행된다. 이 과정이 한번에 수행된다면 한번 읽고 한번 쓰며 2N-1번 교환하면 될 것이다. 이러한 과정은 다양한 단어가 주어졌을 때, N-fold 과정을 수행하기 위해 사용된다.

key 비교 루프의 최적화

대부분의 정렬 방법에서 포인터가 가능한 범위내에 있나 테스트하는 과정을 매시간 필요하다. 하지만 Quick sort는 이러한 과정이 필요없다. 포인터는 각각 경계범위에서 시작되며 cross 되는 순간 끝나기 때문에 범위를 벗어날 일이 없기 때문이다.

bound가 가장 작은 값이거나 가장 큰 값일때도 마찬가지이다. 상대 pointer가 멈춰줄 것이기 때문이다.

Multi-word 키

하나의 키 값이 컴퓨터가 한번에 저장할 수 있는 범위를 넘으면 비교하는데에 시간이 많이 걸린다. 거의 다 정렬되어있는 데이터가 들어왔을 때 이 문제는 심각해진다. (비교의 횟수가 많기 때문에)

따라서 키 값 중 오직 하나만 정하여 비교하는 식으로 진행한다. 낮은 쪽의 포인터가 bound와 키 값이 같은 요소를 만나면 멈추게 동작하여 bound와 키 값이 같은 것들은 모두 bound 위쪽에 위치하게 한다.

Multilevel Storage

퀵 소트는 여러 레벨의 메모리(마그네틱 디스크, 드럼의 back store)가 있는 기기에 적합하다. backing store에 데이터가 저장되어있으면 퍼져있는 데이터를 random 접근하는 것보다 더 빠르다. 메인 메모리와 backing store 사이에만 정보가 오갈 수 있다면 정보를 찾는 데 드는 시간은 더 미미해질것이다.

마그네틱 테이프 저장방식에서는 이러한 이점이 적용되지 않는다.

결론

퀵소트는 컴퓨터의 무작위적 접근 저장에 적합한 정렬방식이다. 큰 메모리의 마그네틱 드럼이나 디스크와 메인 메모리에 저장되는 시스템에서 적합하다. 비교 루프의 횟수는 이론상 가장 적은 횟수와 가까우며, 빠르게 수행된다. 데이터의 이동은 합리적은 범위 내에서 이루어진다. 그러므로 랜덤 접근 방식을 가지고 있는 컴퓨터에서 추천된다.ㄴ