[알고리즘] 퀵정렬(Quick Sort)

이번 시간에는 면접에서도 자주 나오는 퀵정렬에 대해 알아 보겠습니다. 

퀵정렬에서는 pivot이라는 것을 사용합니다. 이 pivot이 중요한데, 그 이유는 정렬의 기준이 되기 때문입니다.

이 말이 무엇이냐 하면~예를 들어서,

 

 

2 6 4 12 3 17 11 15 19 8라는 숫자를 정렬한다고 해봅시다. 그렇다면 여기서 pivot은 아무거나 잡습니다. 정말로요 ! 여러분이 pivot이라고 정하고 싶은 숫자를 선택하시면 됩니다. 저는 12라는 숫자를 일단 pivot으로 잡아 보겠습니다. 

그렇다면 이제 pivot을 기준으로 pivot보다 작거나 같은 수를 모두 pivot왼쪽으로 넘깁니다. 그러면, 다음과 같은 모양이 되겠네요.

이렇게 pivot왼쪽에는 pivot보다 작거나 같은 수가, pivot오른쪽에는 pivot보다 큰 수가 있게 됩니다. 근데 여기서 중요한 것이 있습니다.

이렇게 한번 반복했을 때, 하나의 원소가 위치가 정해진다는 것입니다. 바로 pivot의 위치입니다. pivot을 기준으로 왼쪽에는 무조건 pivot보다 작거나 같은 수가 존재하고 오른쪽에는 무조건 pivot보다 큰 수가 들어가기 때문에 pivot은 왼쪽,오른쪽으로 더이상 움직일 수가 없습니다. 그 말은 pivot의 지금 위치가 결국 정렬했을 때 자리라는 거죠. 이해가 가시나요 ?

 

그럼 이제 pivot(12) 왼쪽,오른쪽 부분을 다시 위의 과정을 반복해봅시다. 저는 pivot을 다시 6으로 잡겠습니다. 

pivot보다 작은 숫자는 왼쪽, 큰 숫자는 오른쪽으로 위치시키겠습니다.

지금까지 퀵정렬에 대해서 간단하게 설명했는데 이해가 되셨나요 ? 이제 pivot(6)의 위치는 고정입니다. 다시 위의 과정을 반복합니다.

지금은 왼쪽부분만 했는데, 왼쪽부분을 다 했다면 오른쪽 부분을 또 반복해야 합니다.

 

...........................................

 

지금 까지 퀵정렬에 대해서 한번 대략적으로 설명했는데, 이해가 가시나요 ? 다시 한번 복습해 봅시다.

 1. pivot을 정한다.

 2. pivot보다 큰 값은 오른쪽에, pivot보다 작은 값은 왼쪽에 둔다.

pivot을 기준으로 왼쪽부분,오른쪽부분을 다시 1번 과정부터 반복한다. 언제까지요? 왼쪽부분의 길이가 1일때 까지요. 1개면 뭐 비교할게 없잖아요 ? 핵심은, pivot을 기준으로 왼쪽은 pivot보다 작은 값, 오른쪽은 pivot보다 큰 값 입니다 !

 

 

이제 퀵정렬을 코드로 구현해볼 건데 실제로 구현하는 부분에서는 재귀와 분할정복이 사용됩니다.

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        int[] arr = { 7, 3, 5, 9, 12, 8, 4, 0, 2, 22 };

        quickSort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    static void quickSort(int[] arr, int start, int end) { // ---(1)
        if (start >= end) {
            return;
        }

        int pivot = arr[start];

        int[] left = new int[100];
        int[] right = new int[100];

        int leftCount = getLeft(arr, left, start + 1, end, pivot);
        int rightCount = getRight(arr, right, start + 1, end, pivot);

        for (int i = 0; i < leftCount; i++) { // --- (1)
            arr[start + i] = left[i];
        }
        arr[start + leftCount] = pivot; // --- (2)

        for (int i = 0; i < rightCount; i++) { // --- (3)
            arr[start + leftCount + 1 + i] = right[i];
        }

        quickSort(arr, start, start + leftCount - 1); // pivot 왼쪽부분을 다시 정렬
        quickSort(arr, start + leftCount + 1, end); // pivot 오른쪽부분을 다시 정렬
    }

    static int getLeft(int[] arr, int[] left, int start, int end, int pivot) {
        int index = 0;
        for (int i = start; i <= end; i++) {
            if (arr[i] <= pivot) {
                left[index++] = arr[i];
            }
        }
        return index;
    }

    static int getRight(int[] arr, int[] right, int start, int end, int pivot) {
        int index = 0;
        for (int i = start; i <= end; i++) {
            if (arr[i] > pivot) {
                right[index++] = arr[i];
            }
        }
        return index;
    }
}

 

함수는 총 3개의 함수가 나옵니다.

quickSort(arr[],start,end) : arr배열안에 있는 숫자들을 start~index사이의 값을 정렬.

getLeft(arr[],left[],start,end,pivot) : start~index사이의 값 중에서 pivot보다 작거나 같은 값을 찾아 left에 넣고, 개수를 return합니다.

getRight(arr[],left[],start,end,pivot) : start~index사이의 값 중에서 pivot보다 큰값을 찾아 right에 넣습니다.

 

먼저, quickSort함수의 기저조건(탈출조건)은 start>=end입니다. 정렬해야 하는 범위가 1이면 더이상 정렬할 필요가 없겠죠 ?

 

그렇지 않으면, pivot을 정하고 getLeft, getRight함수를 실행합니다. 이후 pivot보다 작거나 같은 값은left[]에, 큰 값은 right[]에 들어있게 됩니다. 

 

그럼 pivot보다 작거나 같고, 큰 값들을 구했으면 이제 뭘 해야할까요 ? 구했으면 기존배열에 다시 적용해 주어여야죠 !!

이 부분을 (1) ~ (3)에서 처리하게 됩니다.

 

(1) 

pivot보다 작거나 같은 값들은 left에 들어가 있고, 이 값들을 다시 원래 배열에 적용하는 부분입니다.

leftCount은 pivot보다 작거나 같은 값들의 개수가 들어있고, 그 수만큼 반복합니다. 그리고 특이한 점은, arr[i]가 아니라

arr[start+i]인 점인데, 이는 당연히 정렬은 start부터 했기 때문에 그렇습니다.

 

(2)

pivot보다 작거나 같은 값들을 모두 넣어줬고, 이제 pivot위치를 고정해줍니다. 마찬가지로 arr[start+leftCount]에 pivot을 넣어주

이는 start부터 leftCount(pivot보다 작거나 값은 값 개수)를 다 채우고, 그 바로 다음 자리에 pivot을 위치해야 합니다.

 

(3)

(1)과정과 거의 비슷합니다. 다른 점은 (1)번은 pivot보다 작거나 같은 값이라면, (3)번에서는 pivot보다 큰 값을 넣어줍니다.

 특이한 점은 arr[start+leftCount+1+i]에서 +1을 해주는 부분인데, 이 것은 중간에 pivot을 추가 했기 때문입니다.

 

마지막으로 다시 왼쪽부분과 오른쪽부분에서 위의 과정을 계속 반복합니다.

 

 

한번 다시 정리해 봅시다.

1. 먼저 배열에서 pivot을 정합니다.

2. pivot을 기준으로 같거나 작은 값을 left[]에 넣고, 큰 값을 right[]에 넣습니다.

3. arr[]에 left[]값들을 start위치에서 leftCount만큼 넣습니다.

4. arr[]에 start+leftCount위치에 pivot을 넣습니다.

5. arr[]에 start+leftCount+1위치에서 rightCount만큼넣습니다.

6. pivot을 기준으로 왼쪽,오른쪽 부분 각각  검사하는 범위, start와 end가 같을떄 까지 1~5의 과정을 반복합니다.

 

이번에는 시간복잡도에 대해서 얘기해 보겠습니다. 대부분 퀵정렬의 시간복잡도를 평균적으로 nlongn를 얘기합니다. 최악의 경우는 n^2 이구요.

 

최악의 경우라면 배열이 이미 정렬되어 있는 경우를 의미합니다. 하지만 대부분 이렇게 정렬되어 있는 데이터가 오는 경우가 없겠죠??

그래서 평균적으로 nlogn이라고 합니다. 빅오표기법으로 생각하면 O(N^2)입니다. 빅오표기법은 최악의 경우를 고려하니깐요.

 

만약, nlon을 시간 복잡도로 표기하고 싶다면 세타표기법을 사용해야 합니다.

 

위의 경우는 pivot이 첫번째 인 경우이고, pivot이 가운데 값인 경우는 아래와 같습니다.

#include <iostream>
using namespace std;
//퀵정렬
int n,cnt, quick[10000001];

void quickSort(int i, int j)
{
	if(i >= j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++;   // pivot보다 큰 값을 만나면 종료
		while(quick[right]>pivot) right--; // pivot보다 작은 값을 만나면 종료
		if(left<=right)
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}

int main() 
{
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&quick[i]);

	quickSort(0,n-1);

	for(int j = 0; j < n; j++) // 출력
		printf("%d ",quick[j]);
}