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

 

퀵 정렬(Quick Sort)이란?

리스트에서 하나의 피벗(Pivot)을 정하고, 이를 기준으로 피벗보다 작은 요소들, 피벗보다 큰 요소들로

두 개의 부분 리스트를 만들고(Divide : 분할), 정렬 후 다시 결합(Conquer : 정복)을 재귀적으로 반복하는 방법으로

원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다.

퀵 정렬(Quick Sort)의 특징

1. 주어진 배열(입력 배열) 이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다.

  //주어진 배열만으로 정렬을 할 수 있다.

  //메모리가 제한적인 경우에 이점이 있다.

 

2. 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다

 

3. 시간 복잡도는 Best : O(NlogN), Avg : O(NlogN), Worst : O(N^2)로, 평균적으로 굉장히 빠른 정렬 알고리즘에

   속하며, O(NlogN) 알고리즘에 비해 훨씬 빠르게 동작한다.

 

4. 분할 정복 알고리즘을 기반으로 정렬되는 방식으로, 병합 정렬(Merge Sort)는 하나의 리스트를 절반으로 
   나누어 분할 정복을 하지만, 퀵 정렬(Quick Sort)의 경우 피벗의 값에 따라 하나의 리스트에 대해 비균등하게 나뉜다.

 

5. 일반적으로 병합 정렬(Merge Sort)보다 빠르다.

퀵 정렬(Quick Sort) 결과

주어진 배열을 오름차순 혹은 내림차순으로 정렬

 

퀵 정렬(Quick Sort) 구현 방법

1. 리스트 안에 있는 한 요소를 피벗(Pivot)으로 설정한다.(보통 첫 번째 원소를 피벗 값으로 사용한다.)

2. 피벗을 기준으로 왼쪽에서부터는 피벗보다 큰 값(a)을 찾고, 오른쪽에서부터는 피벗보다 작은 값(b)을 찾는다.

3. a와 b를 교한한다.

4. 왼쪽에서부터 찾은 a값의 위치와 오른쪽에서부터 찾은 b값의 위치가 엇갈리지 않을 때까지 2~3번 과정을 반복한다.

5. 엇갈린 경우에는 오른쪽에서부터 찾은 피벗보다 작은 값(b)과 피벗값을 교환한다.

6. 위의 과정에서 한 번의 분할이 이루어졌고, 두 개의 부분리스트에 대해 다시 1번으로 돌아가 과정을 반복한다.

7. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.

 

//리스트를 분할하여 새로운 부분 리스트를 만들 필요는 없고, 리스트의 인덱스만 부분적으로 탐색해, 부분 리스트를

  표현한다. 정렬이 완료되고 리스트의 모든 인덱스를 출력하여 결합을 표현한다.

 

{3, 7, 8, 1, 4, 5, 2, 6}

 

1.

{3, 7(a), 8, 1, 4, 5, 2(b), 6}

피벗 값을 설정하고, 왼쪽에서부터 피벗보다 큰 값(a=7)을 찾고, 오른쪽에서부터 피벗보다 작은 값(b=2)을 찾는다.

 

2.

{3, 2, 8(a), 1(b), 4, 5, 7, 6}

위에서 찾은 a와 b 값을 교환하고, 다시 피벗 값을 기준으로 a와 b 값을 찾는다.

 

3.

{3, 2, 1(b), 8(a), 4, 5, 7, 6}

위에서 찾은 a와 b 값을 교환하고, 다시 피벗 값을 기준으로 a와 b 값을 찾는다.

//a와 b의 위치가 엇갈렸다.

 

4.

{1, 2, 3, 8, 4, 5, 7, 6}

위에서 찾은 a와 b의 위치가 엇갈렸기 때문에, b와 피벗 값을 교환한다.

//한 번 분할이 이루어졌고, 피벗의 왼쪽 리스트는 피벗보다 작고, 오른쪽 리스트는 피벗보다 크다는 특징을 갖게 된다.

 

5.

{1(b), 2(a), 3, 8, 4, 5, 7, 6(b), a}

분할된 부분 리스트들에 대해 다시 피벗 값을 설정하고 피벗 값을 기준으로 a와 b 값을 찾는다.

//실제로 컴퓨터에서 동작은 한 부분 리스트씩 따로 동작하지만, 글이 길어지기 때문에 부분 리스트들을

  동시에 동작하였다.

//피벗이 8인 부분 리스트에서 8을 기준으로 왼쪽에서부터 8보다 더 큰 값이 없기 때문에, a는 배열의 마지막을

  가리키고 있고, 이 경우도 a와 b가 엇갈렸다고 할 수 있다.

 

6.

{1, 2, 3, 6, 4, 5, 7, 8}

위에서 찾은 분할된 부분 리스트들에서 a와 b가 엇갈렸기 때문에 b와 피벗 값을 교환한다.

 

7.

{1, 2(a,b), 3, 6, 4, 5(b), 7(a), 8}

분할된 부분 리스트들에 대해 다시 피벗 값을 설정하고 피벗 값을 기준으로 a와 b 값을 찾는다.

//2는 더 이상 분할할 수 없기 때문에, 사실상 정렬이 완료되었고, 부분 리스트 {6, 4, 5, 7}에 대해서만

  정렬을 계속 진행한다.

 

8.

{1, 2, 3, 5, 4, 6, 7, 8}

위에서 찾은 a와 b의 위치가 엇갈렸기 때문에 b와 피벗 값을 교환한다.

 

9.

{1, 2, 3, 5, 4(b),a 6, 7, 8}

분할된 부분 리스트들에 대해 다시 피벗 값을 설정하고 피벗 값을 기준으로 a와 b 값을 찾는다.

//7은 더 이상 분할할 수 없으니 종료

//부분 리스트 {5, 4}에서 피벗인 5보다 작은 값이 없기 때문에 a는 리스트의 오른쪽을 가리킨다.

 

10.

{1, 2, 3, 4, 5, 6, 7, 8}

위에서 찾은 a와 b의 위치가 엇갈렸기 때문에 b와 피벗 값을 교환한다.

남은 부분 리스트들이 더 이상 분할할 수 없으니 정렬을 종료한다.

 

최악의 경우(Worst)의 시간 복잡도는 O(N^2)?

위의 구현 방법을 통해 우리는 퀵 정렬이 분할 정복 기법으로 굉장히 효율적인 정렬 방식임을 알았다.

실제로 logN의 시간 복잡도는, N이 1,000,000일 때 logN은 20에 가깝기 때문에 

NlogN의 시간 복잡도를 가진 퀵 정렬은 굉장히 빠르다고 할 수 있다.

하지만 퀵 정렬도, O(N^2)의 시간 복잡도를 가질 때가 있다.

어떤 경우일까?

 

arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

 

위와 같이 정렬이 되어있는 리스트에 퀵 정렬을 해보자.

 

{1(b), 2(a), 3, 4, 5, 6, 7, 8, 9, 10}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

{1, 2(b), 3(a), 4, 5, 6, 7, 8, 9, 10}

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

 

위와 같은 과정이 반복될 것이다.

즉 분할 정복의 이점을 살리지 못하고,

피벗이 1일 때 b를 찾는 과정 10번, 피벗이 2일 때 b를 찾는 과정 9번, ~~~~

10 + 9 + 8 + ... + 1

=> 10 * (10+1)/2 =55

=> N * (N+1)/2

시간 복잡도는 N이 굉장히 크다는 가정 하에, 별 의미가 없는 +1이나 /2같은 연산은 무시하여

O(N*N) == O(N^2)가 나오게 된다.

 

코드(c++, 왼쪽 피벗 설정)

#include <iostream>

using namespace std;

void quickSort(int arr[], int start, int end) {
	
	int pivot = start; //피벗의 인덱스
	int left = pivot + 1; //피벗의 위치를 기준으로 왼쪽부터 시작해서 피벗보다 큰 값의 인덱스를 저장할 변수
    int right = end; //피벗의 위치를 기준으로 오른쪽부터 시작해서 피벗보다 큰 값의 인덱스를 저장할 변수

	cout << '\t';
	for (int i = 0; i < 8; i++) {
		cout << arr[i] << ' ';
	}
	cout << '\n';
	//재귀의 기저 사례
	//더 이상 리스트를 분할할 수 없으면 종료
	if (start >= end)
		return;

	while (left <= right) {//left와 right가 엇갈릴 때까지 반복
		for (; left <= end; left++) {
			if (arr[left] > arr[pivot]) //왼쪽부터 시작해서 피벗보다 큰 값 찾기
				break;
		}
		for (; right > pivot; right--) {
			if (arr[right] < arr[pivot]) //오른쪽부터 시작해서 피벗보다 작은 값 찾기
				break;
		}
		if (left < right) {//엇갈리지 않았다면 left값과 right값 교체
			int temp = arr[left];
			arr[left] = arr[right];
			arr[right] = temp;
		}
		else {//엇갈렸다면 right값과 pivot교체
			int temp = arr[pivot];
			arr[pivot] = arr[right];
			arr[right] = temp;
		}
	}
	//분할된 두 개의 부분 리스트들에 대해 재귀적으로 퀵 정렬 실행
	quickSort(arr, start, right - 1);
	quickSort(arr, right + 1, end);



}


int main() {

	int arr[8] = { 3, 7, 8, 1, 4, 5, 2, 6 };
	int arrSize = 8;
	
	cout << "\tresult" << '\n';
	quickSort(arr,0, arrSize-1);

	

	return 0;
}

코드(kotlin, 가운데 피벗 설정)

fun quickSort(arr: IntArray, s: Int, e: Int){
    if(s>=e) return
    val pivot = (s+e)/2
    var left = s
    var right = e
    while(left<=right){
        while(arr[left] < arr[pivot]){
            left++
        }
        while(arr[right] > arr[pivot]){
            right--
        }
        if(left<=right){
            arr[left] = arr[right].also{arr[right] = arr[left]}
            left++
            right--
        }
    }
    quickSort(arr,s,right)
    quickSort(arr,left,e)
}

fun main() {
    val arr = intArrayOf(8, 3, 1, 4, 2, 5, 7, 6, 10, 9 )
    quickSort(arr,0,arr.size-1)
    println(arr.joinToString(" "))
}