k번째 작은 수 찾기

정렬되지 않은 숫자들 중 k번째 작은 수 찾기 

 

수열 [7, 2, 6, 3, 10, 5, 1, 8, 4, 9] 에서 4번째 작은 수를 찾는다. 

 

> 숫자 하나(Pivot)를 기준으로 작은 수는 왼쪽 큰 수는 오른쪽으로 위치시킨다. 

 

5를 기준(피벗)이라고 하자. 

 

업포인터와 다운포인터를 설정한다. 

업포인터: 왼쪽 -> 오른쪽 이동 (7->2->6-> . . .)

다운포인터: 왼쪽 <- 오른쪽 이동 (. . . <-1<-8<-4<-9)

 

포인터를 한칸씩 움직인다. 

업포인터의 경우 피벗보다 큰 거나 같은 수에 위치할 때 정지. (7에서 정지)

다운포인터의 경우 피벗보다 작거나 같은 수에 위치할 때 정지한다. (4에서 정지)

 

그 후 업포인터와 다운포인터 위치의 숫자를 교환한다.

[7, 2, 6, 3, 10, 5, 1, 8, 4, 9] :

[7, 2, 6, 3, 10, 5, 1, 8, 4, 9] :

[4, 2, 6, 3, 10, 5, 1, 8, 7, 9] :

7 업포인터 위치, 4 피벗, 9 다운포인터 위치

 

두 포인터가 일치하거나 교차하기 전까지 업포인터와 다운 포인터의 교환을 계속한다. 

[4, 2, 6, 3, 10, 5, 1, 8, 7, 9] :

[4, 2, 6, 3, 10, 5, 1, 8, 7, 9] :

[4, 2, 6, 3, 10, 5, 1, 8, 7, 9] :

[4, 2, 1, 3, 10, 5, 6, 8, 7, 9] :

 

[4, 2, 1, 3, 10, 5, 6, 8, 7, 9] :

[4, 2, 1, 3, 10, 5, 6, 8, 7, 9] :

[4, 2, 1, 3, 5, 10 6, 8, 7, 9] :

 

[4, 2, 1, 3, 5, 10 6, 8, 7, 9] :

> 5를 기준으로 작은 수는 왼쪽, 큰 수는 오른쪽에 놓인 것을 알 수 있다. 

 

위를 코드로 구현하자면 다음과 같다. 

#include <iostream>

using namespace std;

int main(void)
{
    int num[10] = {7, 2, 6, 3, 10, 5, 1, 8, 4, 9};

    int index_first = 0;
    int index_last  = 9;
    int *upPointer, *downPointer;
    upPointer = &num[index_first];
    downPointer = &num[index_last];

    int middle_index = (index_first+index_last) / 2; 
    
    int pivot = num[middle_index];  //pivot을 10으로 설정한다. 
    
    while(index_first<index_last)
    {
        if(num[index_first] < pivot)
        {
            index_first++;
        } 
        if(num[index_last] > pivot)
        {
            index_last--;
        } 
        
        int tmp = num[index_first];
        num[index_first] = num[index_last];
        num[index_last] = tmp;
    }
    
    for(int i = 0; i<10; i++)
        cout<<num[i]<<" ";
        // 7 9 2 6 3 5 1 8 4 10


    return 0;
}

 

만약 우리가 구하고자 하는 k번째 작은 수가 3이라면 5의 왼쪽에서 다시 피벗을 설정하여 진행하면 되고,

8이라면 5의 오른쪽에서 다시 피벗을 설정하여 진행하면 된다.