내가 이해하려고 쓰는 [퀵정렬] Quick sort

 

 

 

* 유투버 동빈나님의 영상을 참조하여 정리한 것입니다.

 

 

 

퀵정렬(Quick sort)는

의미 그대로 속도가 빠른 정렬 알고리즘이며 평균 시간복잡도는 

를 자랑한다. 아래에서 더 자세히 설명할 것이다.

퀵정렬은 또한, 분할정복(Divide&Conquer) 알고리즘의 하나이다.

그 이유는, 퀵정렬을 하는 방식에 있다.

 

 

 

퀵정렬을 하는 방식은

특정한 값을 기준으로 이큰 숫자와 작은 숫자를 나누어서 각각 정렬을 한 후 합친다.

여기서의 기준이 되는 값을 피봇(Pivot)이라고 부른다. 보통 피봇은 맨 앞의 값으로 정한다.

 

 

 

퀵정렬 예시

글로만 쓰면 뭔 소린지 쓰는 나조차도 모를게 분명하므로 예시를 보면서 구체적으로 수행해보자.

e.g. 3 7 8 1 5 9 6 10 2 4 --- 10개의 숫자를 퀵정렬로 정렬하려고 한다.

 

여기서 피봇은 뭐라고? 맨 앞 값이라고 했다. 즉 3이 피봇값이다. 3 7 8 1 5 9 6 10 2 4

 

오른쪽으로 인덱스를 하나씩 증가시키며 스캔해서 피봇값보다 큰 값을 찾는다. 7이 3보다 크다.

큰 인덱스부터 인덱스를 하나씩 감소시키며 스캔해서 피봇값보다 작은 값을 찾는다. 2가 3보다 작다.

* 아래 그림에서 l(large)은 큰 값을 의미하고 s(small)는 작은 값을 의미한다.

이 두 값을 서로 교체exchange해준다. large(7) ⇔ small(2)

그리고 다시 또 l과 s를 찾아주고, 또 exchange를 해준다.

그런데, l과 s를 찾았을 때 이 두 값이 서로 교차cross하는 경우에는

l과 s를 exchange하는 것이 아니라, s와 pivot을 exchange해준다.

그럼 교체된 pivot은 정렬이 완료된 상태이다. why?

이 pivot 3을 기준으로 왼쪽을 보면 3보다 작은 값만 남고, 오른쪽을 보면 3보다 큰 값만 남기 때문이다.

그리고 이 정렬된 값을 기준으로 왼쪽부분과 오른쪽 부분을 나누어 위의 분할정복을 반복한다.

여전히 각 부분에서 맨 앞값이 피봇값이 된다.

 

 

 

3을 기준으로 왼쪽파트를 먼저보자. 피봇값은 맨 앞값이라고 했으므로 1이다.

1보다 큰 값을 찾았더니 2가 발견되었는데, 작은 값을 찾았더니 없다.

이 경우에는 그냥 자기자신을 작은 값으로 고르며, 교차cross한 것과 동일하게 본다.

그러면 어떻게 한다고? s와 pivot을 교체해준다고 했다.

s도 1이고, pivot도 1이므로 자기 자신과 교체되는 것이다. 즉, 그냥 정렬이 이루어지게 된다.

이렇게 1이 정렬이 완료된다.

그리고 1의 오른쪽과 왼쪽을 보는데 왼쪽은 아무것도 없으므로 볼게 없고, 오른쪽의 2를 본다.

2는 스스로 피봇인데, 3이 정렬이 되어버린 상태이므로 3을 넘어가서 볼수는 없다. 따라서 2는 그냥 지혼자 정렬된다.

 

 

 

1,2,3은 정렬이 완료되었고, 이제 위에서 보지 않은 8부터 뒷부분을 똑같이 수행해준다.

l과 s가 교차할때 s와 pivot을 교체해주면 해당 pivot은 정렬이 완료된다. 이 과정을 되풀이.

끝까지 수행하면 결국 모든 값이 정렬이 완료되어 1 2 3 4 5 6 7 8 9 10이 된다.

 

 

 

퀵정렬 알고리즘을 수행할 때 한 부분에서의 시간복잡도는 힙정렬에서 본 것과 같이,

이분할 알고리즘의 시간복잡도가 항상 밑이 2인 로그를 따른다고 알려져 있기 때문에

이다. 예를 들어서, 데이터의 갯수가 20개라면,

20^2 = 400번 수행되어야 하지만, 퀵정렬 수행시 10개와 10개로 쪼개지고, 또 5개씩 4부분으로 쪼개지고,

8부분으로 쪼개지고,  16부분으로 쪼개져서 총 4번 쪼개진다. 시간복잡도에 넣어보면 왜 4번인지 알 수 있다.

여기에 데이터 갯수 n을 곱한

이 퀵정렬의 평균 시간복잡도가 된다. 여기서 중요한 것은, '평균'이라는 단어이다.

최악의 경우에는 그냥 단순 n제곱의 시간복잡도를 가지기 때문이다.

이미 정렬이 되어있는 상태 1 2 3 4 5 6 7 8 9 10에서 피봇을 1로 잡고 수행한다고 가정하면,

큰 값은 계속 찾을 수 있지만 작은 값이 계속해서 전체 데이터를 스캔한 후 자기자신으로 지정된다.

그 후 1이 정렬완료되고 피봇이 2가 되어도 같은 상황이 벌어진다.

즉, 분할정복의 이점이 없어서 밑이 2인 로그의 시간복잡도를 사용할 수가 없다.

 

 

 

퀵정렬을 하는 순서를 번호로 붙여보면,

1. 각 부분에서 맨 첫값을 pivot(key)로 잡아준다.

2. 인덱스를 key부터 늘려가면서 pivot값보다 큰 값을 찾는다.

3. 인덱스를 끝에서부터 줄여가면서 pivot값보다 작은 값을 찾는다.

4. 큰 값과 작은 값을 찾으면 둘이 교체해준다.

5. 4에서 만약 큰 값과 작은 값이 교차하는 경우(인덱스 순서가 바뀌면) 작은 값과 pivot값을 바꿔준다.

6. 1~5가 1세트이다. 즉, 하나의 부분에서 발생하는 정렬코드이다. 반으로 나눠주면서 쪼개지는 부분마다 계속해서 같은 정렬코드를 구현할 수 있도록 재귀함수를 쓴다(자기자신을 불러온다)

 

코드로 구현해보면 다음과 같다.

#include <stdio.h>


int number = 10;
int data[10] = {1,10,5,8,7,6,4,3,2,9};

void quickSort(int *data, int start, int end){
    if(start>=end){  
        return;
    }
    int key=start;
    int i=start+1; 
    int j=end; 
    int temp;
	
    while(i<=j){
        while(data[i]<=data[key]){ 
            i++;
        }
        while(data[j]>=data[key]&&j>start){ 
            j--;
        }
        if(i>j){  
            temp=data[j];
            data[j]=data[key];
            data[key]=temp;
        }
        else{ 
            temp=data[j];
            data[j]=data[i];
            data[i]=temp;
        }
    }
    quickSort(data,start,j-1);
    quickSort(data,j+1,end);
}

int main(void){
    quickSort(data, 0, number-1);
    int i;
    for(i=0;i<number;i++){
        printf("%d ", data[i]);
    }
    return 0;
} 

 

퀵정렬을 하는 순서에 맞춰서 하나씩 차근히 살펴보자.

우선 왜 힙정렬처럼 main에 바로 코드를 짜지않고 quickSort라는 함수를 따로 만들어준건지는 6번에서 설명할 것이다.

 

quickSort의 내부를 일단 먼저 이해하려고 해보자.

quickSort의 parameter중 start는 첫번째 인덱스, end는 마지막 인덱스이다.

만약 start>=end, 즉 첫번째 인덱스가 마지막 인덱스보다 크거나 같으면

데이터가 1개라는 뜻이므로 그대로 return해주면 된다.

 

1. 각 부분에서 맨 첫값을 pivot(key)로 잡아준다.

즉, (pivot)key=start이다.

 

2. 인덱스를 key부터 늘려가면서 pivot값보다 큰 값을 찾는다.

key부터 늘려갈 인덱스를 i로 선언해주고, key보다 큰 값부터 찾아야 되므로 시작점을 i=start+1로 둔다.

그리고 i번째 인덱스의 값이 key값보다 작거나 같으면 큰 값을 찾을 때까지 인덱스를 계속 증가시켜준다. i++;

3. 인덱스를 끝에서부터 줄여가면서 pivot값보다 작은 값을 찾는다.

마지막 인덱스부터 줄여줄 인덱스를 j로 선언해주고, 시작점을 j=end로 둔다.

그리고 j번째 인덱스의 값이 key값보다 크거나 같으면 작은 값을 찾을 때까지 인덱스를 계속 감소시켜준다. j--;

이 때 줄어드는 j값이 첫번째 인덱스를 벗어나서 더 앞으로 가지 않도록 주의한다(j>start를 유지해야함)

 

4. 큰 값과 작은 값을 찾으면 둘이 교체해준다.

이 i(늘어나는 인덱스)와 j(줄어드는 인덱스)가 당연히 서로 i<=j인 경우에 2번과 3번이 수행되어야 한다.

큰 값과 작은 값을 정상적으로 찾은 경우에 temp임시변수를 사용해서 두 값을 서로 교체해준다.

5. 4에서 만약 큰 값과 작은 값이 교차하는 경우(인덱스 순서가 바뀌면) 작은 값과 pivot값을 바꿔준다.

그럼 저 위의 예시에서 설명했듯이 큰 값과 작은 값의 인덱스가 서로 교차해서 i>j가 되면?

즉, 작은 값의 인덱스가 큰 값의 인덱스보다 앞에 있다면? 작은 값(j인덱스)과 pivot(key)값을 교체해준다.

그러면 j인덱스에 pivot값이 들어가서 이 숫자는 정렬이 완료되고 j인덱스를 기준으로 왼쪽과 오른쪽으로 분할된다.

 

6. 1~5가 1세트이다. 즉, 하나의 부분에서 발생하는 정렬코드이다. 반으로 나눠주면서 쪼개지는 부분마다 계속해서 같은 정렬코드를 구현할 수 있도록 재귀함수를 쓴다(자기 자신을 불러온다)

1~5세트를 계속해서 다시 호출할 수 있도록 quickSort함수를 quickSort함수 내부에서 다시 호출해준다.

자기 자신을 다시 불러오기 위해서 quickSort함수를 애초에 만들어준 것이다.

quickSort를 2번 호출하는 이유는, j인덱스를 기준으로 분할되어 왼쪽부분과 오른쪽부분, 즉 두 부분으로 나눠지기 때문이다.

왼쪽부분 quickSort의 start와 end 파라미터는 각각 start값 그대로, j-1값이 된다.

오른쪽부분 quickSort의 start와 end 파라미터는 각각 j+1값, end값이 된다.