정렬(5) 퀵정렬

3

7

2

5

1

8

6

4

 

위와 같은 수가 있다.

이를 오름차순으로 정렬하는데 있어 퀵정렬을 이용하고 싶다.  퀵 정렬이란 무엇일까.

 

퀵정렬의 원리는 다음과 같다.

첫번째 배열 원소의 시작 주소와 마지막 배열 원소의 마지막 주소를 구하고

즉 L과 R를 구하라는 의미이다.  그런 이후 그 둘의 중간 기준점을 구한다.M 의 값을 구하란 의미이다.
위같은 경우라면 [0] 과 [7] 을 나누고 [3]을 기준으로 잡는다

기준값 왼쪽에는 기준값보다 작은 값을 두고 기준값보다 큰 값은 오른쪽에 둔다.

 

예를 들어 

기준 값 [3]에 있는 값이 5라고 그런다면 5보다 작은 수들은 [0]~[2]에 넣겠다.

기준 값 [3]에 있는 값이 5라고 그런다면 5보다 큰 수들은 [4]~[7]에 넣겠다.

 

그러면 [0] 은 하나씩 증가하면서 기준점 [3]의 값과 비교를 한다. 다음과 같이 말이다.

[0] < [5] 

그러면 [7]은 하나씩 감소하면서 기준점 [3]의 값과 비교를 한다 다음과 같이 말이다.

[5]<[7]

 

하지만 정렬이 되지 않은 상태에서 기준값과 비교를 하게 된다면 

[0]~[2] 에는 기준값보다 큰 값이 있는 경우가 있을 것이고

[4]~[7] 에는 기준값보다 작은 값이 있는 경우가 있을 것이다.

 

따라서 [0]~[2]에서 만난 큰 값이나 [4]~[7]에서 만난 작은 값을 만나게 된다면 

[0]~[2] 에서 만난 큰 값과 [4]~[7]에서 만난 작은 값 서로의 위치를 바꾼다.

 

3

7

2

5

1

8

6

4

 

글로는 이해하기 힘들 수 있다 위 예를 들어 설명하겠다. 기준값이 위에서는 5가 되는데

3 < 5 를 비교하고 기준 값보다 작은 값이라면 1 증가를 하게 된다. 그럼 다음 만나는 값은 7인데 5보다 크다.

왼쪽에 있어야 하는 값들은 5보다 작은 값이어야 하는데 7이므로 더 이상 증가하지 않고 잠시 멈춰 있는다.

 

그런 이후 5 < 4 를 비교하게 된다. 하지만 오른쪽에 있어야 하는 값들은 5보다 큰 값이어야 하는데 4이다.

이러면 4는 잠시 멈춰있는다.

 

이렇게 된 경우 서로 멈춰 있던 7과 4의 위치를 바꿔준다.

3

4

2

5

1

8

6

7

 

그런 다음 다시 2 > 5를 비교하게 되고 1 증가시킨다.

그럼 5 > 5 를 만나게 되는데 5는 기준 값임으로 왼쪽에 위치하든 오른쪽에 위치하든 상관없다.

왼쪽에 위치한다면 작은 값중에 최고 큰 값이 될 것이고 오른쪽에 위치한다면 큰 값중에 제일 작은 값이 될테니.

하지만 조건에 맞지 않으니 잠시 멈춰 있는다.

 

5 < 6 을 비교하게 되고 1감소 시킨다. 5 < 8 비교하고 1 감소 시킨다. 5 < 1 비교하고 5보다 작은 값임으로 

서로 멈춰 있는 곳에서 값의 위치를 바꾼다. 다음과 같이 말이다.

3

4

2

1

5

8

6

7

 

위와 같이 된 경우

결국은 L 값은 M보다 같거나 커져 있는 순간이 오게 된다. R값 역시 M보다 같거나 작아져 있는 순간이 온다.

결국 L과 R이 크로스 형태를 띄고 있다는 얘기가 된다. 

이때를 기준으로 값을 분리한다.

3

4

2

1

5

8

6

7

 

그런 이후 다시 위 했던 방식 그대로 기준 값을 구하고 분리해주고 반복하게 되는 과정을 겪게된다.

 

그런데 분리를 하면서도 변하지 않는 것이 있다. 그것은 바로 배열 시작주소 와 배열 마지막 주소이다

L의 값은 1씩 증가하면서 결국은 마지막 주소의 값과 같아지거나 큰 값이 될 것이고

R의 값은 1씩 감소하면서 결국은 시작주소의 값과 같아지거나 작아지게 될 것이다. 

 

이것이 퀵 정렬의 기본 원리이다. 

 

이를 바탕으로 코드로 구현해보자.

#include <iostream>

void function(int *p_array, int left, int right) { 
    int PL = left; 
    int PR = right; 
    int PM = (left+right)/2;
    int temp;
    
 do {
    while(p_array[PL] < p_array[PM]) { 
        PL++;
    }
    
    while(p_array[PR] > p_array[PM]) { 
        PR--;
    }
    
    if(p_array[PL]>=p_array[PR]) { 
        temp = p_array[PL];
        p_array[PL] = p_array[PR];
        p_array[PR] = temp;
        PL++; PR--;
    } 
 }while(PL < PR);
 
 if(PL<right){
    function(p_array, PL, right);
 }
 
 if(PR>left) { 
     function(p_array, left, PR);
 }
}

int main() { 
    int array [] = {3,7,2,5,1,8,6,4};
    int left = 0; int right = 8-1;
    function(array, left, right);
    for (int i = 0; i<8; i++) { std::cout<<array[i]<<' '; } 
}