방통대 알고리즘 4강 정렬 (2) - 퀵 정렬

 

 

내가 이해하려고 쓴 글.. 생각보다 이거 쓰는 것도 시간 오래걸리네 ;

 

 

 

퀵 정렬?

특정 데이터를 기준으로

주어진 배열을 2개의 부분배열로 분할하고,

각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식

 

 

피벗 pivot, 분할 원소

주어진 배열을 두 부분배열로 분할하는 기준이 되는 특정 데이터

보통 주어진 배열의 첫 번째 데이터로 지정.

 

 

특정원소를 기준으로 주어진 배열을 두개의 부분배열로 쪼갠다. 바꿔말하면, 피벗을 기준으로 주어진 배열을 두개로 쪼갠다, 피벗이 제자리를 잡도록 해서 정렬하는 방식.

 

 

피벗이 제자리를 잡도록 하여 정렬하는 방식

? : 피벗

입력 배열 A[ ]    30 45 20 15 40 25 35 10

분할 후 상태       25 10 20 15 30 40 35 45

 

왼쪽 부분배열[25 10 20 15]의 모든 값들은 오른쪽 부분배열[40 35 45]의 값들은 35보다 작음

25는 오른쪽 부분배열보다 다 작음. 

 

왼쪽 부분배열의 모든 데이터 < 오른쪽 부분배열에서 가장 작은 데이터(35)

왼쪽 부분배열에서 가장 큰 데이터(25) < 오른쪽 부분배열의 모든 데이터 

 

왼쪽 부분 배열의 모든 값 < 피벗 < 오른쪽 부분배열의 모든 값

 

이 과정을 순환해서 계속 반복함.

 

 

퀵 정렬의 전체적인 처리 과정

(보통 왼쪽부터 먼저함)

? : 피벗

? : 픽스(제자리 찾음)

 

30 45 20 15 40 25 35 10 

                1st 분할

25 10 20 15 30 40 35 45

                 2st 분할

15 10 20 25 30 40 35 45

                 3st 분할

10 15 20 25 30 40 35 45

                 4st 분할

10 15 20 25 30 40 35 45

                 5st 분할

10 15 20 25 30 40 35 45

                 6st 분할

10 15 20 25 30 40 35 45

                 7st 분할

10 15 20 25 30 35 40 45

                 8st 분할

10 15 20 25 30 35 40 45

 

 

이렇게 보면 결국 분할만 계속 한거임. 피벗을 중심으로 왼쪽과 오른쪽으로 분할.

==> 이게 퀵정렬 

 

 

피벗 = j

2번은 왼쪽부분배열이니까 0..j-1 만큼 돌고,

3번은 오른쪽부분배열이니까 j+1...n-1만큼 도는 것. 

 

퀵정렬은 순환 알고리즘 분할함수라는 게 핵심

 

 

퀵 정렬 알고리즘

QuickSort(A[ ],n)

{

  if(n > 1) {

     //1.피벗을 기준으로 두 부분배열로 분할

     //pivot은 제자리를 잡은 피벗의 위치(인덱스)를 표시

     pivot = Partition(a[0..n-1],n);

    

      //2.왼쪽 부분배열레 대한 퀵 정렬의 순환 호출

     QuickSort(A[0..pivot-1], pivot);

 

      //3.오른쪽 부분배열레 대한 퀵 정렬의 순환 호출

     QuickSort(A[pivot+1...n-1], n-pivot-1);

  }

}

 

 

(순환 알고리즘의 성능은 점화식으로 표현된다. 점화식에서는 폐쇄형을 구해야지만 알고리즘의 성능을 나타낼 수 있다. )

 

퀵정렬은 순환보다는 어떻게 분할 할거냐? 가 핵심

 

 

분할 과정

 

피벗 = A[0] 

Left = 1 피벗보다 큰(같은) 값을 찾음.

Right = 7 피벗보다 작은(같은) 값을 찾음.

30 45 20 15 40 25 35 10 

30 45 20 15 40 25 35 10  => left와 right 서로 교환 일어남   left < right.  1<7

30 10 20 15 40 25 35 45

30 10 20 15 40 25 35 45 => left와 right 서로 교환 일어남  left < right.  4<5

30 10 20 15 25 40 35 45  => 여기선 교환 안일어남  왜?      left > right.   5<4(X).  end 처리 ==> left와 피벗과의 교환 발생. 

25 10 20 15 30 40 35 45  => 피벗을 기준으로 왼쪽 부분배열, 오른쪽 부분배열 나뉘게됨.

피벗 제자리 지정 완료.

 

 

이와 같은 분할과정을 왼쪽, 오른쪽 데이터를 순환처리 하면됨. 

 

 

분할 함수 Partition

 

 

퀵정렬 분할 예시

 

 

무한대가 있다고 생각하고 처리하면 됨

피벗이 제일 큰 값인 경우에는 맨 오른쪽에 무한대가 있다라고, 가정하고 처리하면 쉽게 처리가능. 

 

 

 

성능과 특징

분할 함수 Partition()의 성능

피벗과의 비교 횟수?

피벗보다 큰가, 피벗보다 작은가 비교

right와 피벗이 교환하되면서 피벗 제자리 위치.

 

 

이 데이터들이 피벗과 몇 번 비교할까?

각 데이터들은 피벗과 적어도 1회는 비교, 많아야 2회씩 비교.

 

2회씩 비교하는 경우는 30, left 40, right 10 인경우 위치가 바뀌는 경우엔 2번씩 진행. 

전체 n개의 데이터에 대해서 1번 또는 2번 반복.

==> ϴ(n) 

빅세타엔, 데이타 갯수에 비례하는 만큼의 비교가 이루어진다. 

 

 

퀵 정렬 QuickSort() 의 수행시간은 분할되는 두 부분배열의 크기에 따라 달라짐 

왼쪽에 몇개 있는지 알 수 없어 nʟ(엔엘)

오른쪽에 몇개 있는지 알 수 없어 nʀ(엔알)

 

데이터 n개를 퀵정렬하는 시간은

분할함수 시간 점화식으로 기본형태 만들 수 있음. 모두 더함. 

갯수만 알면 구할 수 있음.

 

 

 

평균시간은 분할된 두 부분배열의크기를 모두 더해서 평균을 냄. 

 

 

재미있는 부분.

1. 배열이 항상 0 : n-1 또는 n-1 : 0으로 분할되는 경우

(일단 모든 배열이 다 정렬되어있음을 전제.)

 

 

 

(분할되는 경우를 봤더니 항상 0:n-1, n-1:0의 경우더라~ )

 

• 극심한 불균형적 분할 -> 최악의 경우

0:n-1, n-1:0 -> 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분 배열이 되는 경우. 끝단에 부분배열이 없는것.

피벗만 제자리에 있고 나머지 데이터가 모두 왼쪽으로 가던지, 피벗만 제자리에 있고 나머지 데이터가 모두 오른쪽으로 가던지. 

(왼쪽만 있거나, 오른쪽만 있거나)

피벗이 항상 부분배열의 최솟값 또는 최댓값인 경우임. 

입력 데이터가 정렬된 경우 AND 피벗을 배열의 첫 번째 원소로 정한 경우(항상 최솟값이나, 최댓값이 되는거임. 결국 분할이 0:n-1 이거나 n-1:0이 됨.)

 

이 원리를 점화식으로 나타내면.

T(n) = T(n-1) + T(O) + ϴ(n)       (n>1),T(1)=1

==> T(n) = T(n-1) + ϴ(n)

 

 

퀵 정렬의 최악의 수행 시간은 T(n) = O(n²) 빅오엔제곱 이다. 

 

 

 

2. 배열이 항상 n / 2 : n / 2 으로 분할되는 경우

(분할할때 항상 n/2 : n/2로 나뉘어져, 가장 이상적인 경우임. 피벗이 항상 중앙이 됨.)

 

 

25 40 10 35 15 30 20   ///n/2 : n/2

15 20 10 25 35 30 40   ///n/2 : n/2

10 15 20 25 35 30 40

10 15 20 25 35 30 40

10 15 20 25 35 30 40   ///n/2 : n/2

10 15 20 25 35 30 40

10 15 20 25 35 30 40

10 15 20 25 35 30 40

 

 

• 가장 균형적인 분할 -> 최선의경우

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

피벗이 항상 배열의 중간값이 되는 경우

이 원리의 점화식은

T(n) = T(n/2) + T(n/2) + ϴ(n)           (n>1),T(1)=1

==> T(n) = 2T(n/2) + ϴ(n)      

T(n) = O(nlogn)

 

퀵 정렬의 최선의 수행 시간은 T(n) = O(nlogn) 빅오엔로그엔

 

 

 

성능과 특징

퀵 정렬의 평균 수행시간

 

부분배열의 모든 분할 비율에 따른 수행시간의 평균

피벗은 동일한 확률을 가지고 분할 후 배열의 어느 곳에나 위치 가능

 

0:n-1, 1:n-2, 2:n-3, ..., n-2:1, n-1:0

 

 

 

퀵 정렬의 평균 수행시간은 O(nlogn)

 

 

 

 

피벗 선택의 임의성만 보장되면 평균 수행시간을 보장

피벗선택시 최악의 경우(O(n²))가 있는데 (0:n-1, n-1:0)

피벗선택만 제대로하면(임의성만 보장되면) 최악의 수행시간을 피할 수 있음. 

 

피벗을 배열의 첫 번쨰 원소로 지정하는 경우 , AND 배열이 정렬된 경우 => 배열이 정렬되면  0:n-1, n-1:0 으로 만들어짐

피벗을 배열의 첫 번째 원소로 뽑지 않으면 됨 -> 랜덤으로 뽑아

그럼 평균적인 수행시간을 보장할 수 있음.

배열에서 임의의 값을 선택한 후, 배열의 첫 번째 원소와 서로 교환후 정렬 수행

 

 

퀵정렬은 제자리 정렬 알고리즘 이다.

: 입력 배열 이외에 추가적인 저장 공간을 상수 개(left,right, tmp,n,pivot)만 사용

 

 

퀵정렬은 안정적이지 않은 정렬 알고리즘이다.

 

 

 

 

퀵정렬은 분할정복 방법이 적용된 알고리즘이다.

: 분할정복 방법이 되면, 순환알고리즘, 순환알고리즘의 성능은 점화식으로 표현된다.

• 분할

피벗을 기준으로 주어진 배열을 두 부분배열로 분할 -> 두 부분배열의 크기는 일정하지 않음

• 정복

두 부분배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬함

• 결합(X)

필요없음