[자바 Do It! 알고리즘]Chapter06 정렬 (비재귀적인 퀵 정렬)

[비재귀적인 퀵 정렬]

1. 05장의 recur 메서드는 데이터를 임시 저장하기 위해 '스택'을 사용했습니다. 이번 퀵 정렬도 마찬가지로 '스택'을 사용합니다.

1) lstack : 나눌 범위의 왼쪽 끝 요소의 인덱스를 저장하는 스택입니다.

2) rstack : 나눌 범위의 오른쪽 끝 요소의 인덱스를 저장하는 스택입니다.

3) 두 스택의 용량은 right - left + 1 입니다. (나눌 배열의 요솟수 )

2. 스택의 변화

1) lstack 에 left 를, rstack에 right를 푸시합니다. a에서 볼 수 있듯이 lstack에 푸시되는 값은 0, rstack 에

푸시되는 값은 8입니다.

2) lsatck 에서 팝한 값을 left에 대입한 다음 그 left의 값을 다시 pl에 대입합니다.(rstack도 동일한 과정), 그 결과

left와 pl의 값은 0, right와 pr의 값은 8이 됩니다. 이 값은 정렬할 배열의 범위를 의미합니다. 이렇게 값을

설정하면 a[0] ~ a[8]이 배열 왼쪽 그룹(a[0] ~ a[4])과 오른쪽 그룹 (a[5] ~ a[8])으로 이루어집니다.

3) 첫 번째 if 문에서 lstack, rstack에 각각 0과 4를 푸시하고 두 번째 if 문에서 각각 5와 8을 푸시합니다.

그 결과 스택은 c 상태가 되고 그 다음 while 문에 의해 루프 본체( 1),2) ) 가 반복됩니다.

4) lstack에서 5가 팝되어 left와 pl에 대입되고, rstack 에서 8이 팝되어 right와 pr에 대입됩니다.(d) 이 과정을

거치고 나면 배열의 한 부분(a[5] ~ a[8])으로 나누어집니다. 즉, a[5]~a[6]의 왼쪽 그룹과 a[7]~a[8]의

오른쪽 그룹으로 나누어집니다.

5) lsatck 과 rstack에 {5,6} 과 {7,8}을 푸시합니다.(e)

​

[스택의 용량] (이 내용은 도저히 이해가 안되서 결과만 적습니다..)

1. 일반적으로 요소의 개수가 적은 배열일수록 적은 횟수로 분할을 종료할 수 있습니다.

2. 따라서 요소의 개수가 적은 그룹을 먼저 분할하면 스택에 동시에 쌓이는 데이터의 최대 개수가 적어집니다.

3. 배열의 요소 개수가 n이라고 하면 스택에 쌓이는 데이터의 최대 개수는 log n보다 적습니다.

4. 따라서 요소의 개수가 백만 개여도 스택의 최대 용량은 20개면 충분합니다.

​

[피벗 선택하기]

1. 피벗을 선택하는 방법은 퀵 정렬의 실행 효율에 큰 영향을 줍니다.

2. 피벗 선택하는 방법

1) 나눌 배열의 처음, 가운데, 끝 요소를 정렬한 다음 가운데 요소와 끝에서 두 번째 요소를 교환합니다.

2) 피벗으로 끝에서 두 번째 요소의 값(a[right -1])을 선태갛여 나눌 대상의 범위를 a[left + 1] ~ a[right -2]로

좁힙니다.

(1) 왼쪽 커서 pl의 시작 위치 left + 1

(2) 오른쪽 커서 pr의 시작 위치 right -2

3. 이 방법은 나눌 그룹의 크기가 한쪽으로 치우치는 것을 피하ㅂ면서도 나눌 때 스캔할 요소를 3개씩 줄일 수 있다는

장점이 있습니다.

​

[시간 복잡도]

1. 퀵 정렬은 배열을 조금씩 나누어 보다 작은 문제를 해결하는 과정을 반복하므로 시간 복잡도는 O(n log n)입니다.

2. 다만 정렬할 배열의 초깃값이나 피벗의 선택 방법에 따라 시간복잡도가 증가하는 경우도 있습니다.

3. 예를 들어 매번 단 하나의 요소와 나머지 요소로 나누어지면 n번의 분할이 필요합니다. 따라서 최악의

시간 복잡도는 O(n2)이 됩니다.