정렬 (Sorting)

정렬은 순서가 없는 사물들을 순서대로 재배열하는 것을 뜻한다. 순서에는 오름차순(ascending order)과 내림차순(descending order)이 있다. 다음 그림은 순서대로 오름차순과 내림차순의 예시를 보여준다.

 

예를 들면, 책은 '제목'이나 '저자명', 그리고 '발간 연도' 등을 기준으로 오름차순이나 내림차순으로 정렬할 수 있다. 인터넷 쇼핑몰에서는 물건들을 '판매 인기순'이나, '가격 낮은 순', '상품 평순' 등으로 정렬할 수 있고, 엑셀 프로그램도 성적처리를 하는 경우 '학번', '성적', '실습 점수' 등의 기준으로 정렬할 수 있다.

 

인터넷에서 다양한 정렬 기준들

정렬은 자료 탐색에서 매우 중요하다. 예를 들면, 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 단어들이 알파벳순으로 정렬되어 있기 때문이다. 만약 사전이 정렬되어 있지 않다면 단어를 빨리 찾는 것은 거의 불가능할 것이다. 컴퓨터 또한, 정렬되어 있지 않은 자료에 대해서는 탐색의 효율성이 크게 떨어진다.

 

보통 정렬시켜야 될 대상을 레코드(record)라고 부른다. 레코드는 여러 개의 필드로 이루어진다. 다음 그림은 학생들의 레코드에 대한 예시이다.  

 

학생의 레코드에서 학번, 소속, 성명 등이 필드가 된다. 여러 필드 중에서 특정한 레코드를 식별해주는 역할을 하는 것을 키(key)라고 한다. 학생의 레코드에서는 학번이 키가 될 수 있다.  결국 정렬이란 레코드들을 키 값의 순서로 재배열하는 것이다.

 

정렬 알고리즘은 다양하게 존재하지만 모든 상황에서 최상의 성능을 보여주는 최적 알고리즘은 존재하지 않는다. 따라서 현재의 프로그램 실행 환경에서 가장 효율적인 정렬 알고리즘을 선택해야 한다. 보통 알고리즘 효율성 평가는 빅오 표기법을 이용해 근사적으로 표현한다.

 

정렬 알고리즘의 분류

정렬 장소에 따른 분류

정렬 알고리즘을 먼저 정렬이 수행되는 장소에 따라 내부 정렬(Internal sorting)과 외부 정렬(external sorting)로 구분할 수 있다. 내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬을 의미한다. 반면, 외부정렬은 외부 기억 장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬을 하는 방법으로 대용량 자료를 정렬하는데 적합하다.

 

구현 복잡도와 알고리즘 효율성에 따른 분류

정렬 알고리즘은 크게 두 가지로 나누어진다. 단순하지만 비효율적인 방법과 복잡하지만 효율적인 방법이다. 효율적인 알고리즘은 정렬할 레코드 수가 많다면 보통 구현하기 까다로운 알고리즘 방법을 사용하는 것이 좋다.

 

• 단순하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬 등

• 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 병합 정렬, 기수 정렬 등 

안정성에 따른 분류

안정성(stability)의 측면에서도 구분할 수 있다. 안정성이란 입력 데이터에 동일한 키 값을 갖는 레코드가 여러 개 존재할 경우, 정렬 후에도 이들의 상대적인 위치가 바뀌지 않는 것을 말한다. 안정성을 충족하는 정렬에는 삽입정렬, 버블 정렬, 병합 정렬 등이 있다.

 

이제 정렬 알고리즘에는 어떤 것들이 있고 구현을 통해 어떤 원리로 작동하며 얼마나 효율적인지 살펴보도록 하겠다.

 

선택 정렬

선택 정렬(selection sort)은 전체 숫자들 중에서 가장 작은 숫자를 반복적으로 선택해 앞쪽으로 옮기는 방법을 사용한다.

 

정렬되지 않은 데이터가 있다고 예를 들어보자. 바꿀 위치(A라고 하겠다)의 값을 안 상태에서 그 위치부터 데이터를 담은 컨테이너의 끝까지 검사한다. 검사한 값들 중 A보다 작으며 그중에서도 최솟값인 B를 선택한다. 그리고 A의 위치와 B의 위치를 서로 변경한다. N개의 데이터가 있는 경우 맨 처음부터 N - 1번째까지 이 작업을 반복한다.

 

다음 그림은 선택 정렬의 과정을 표현한 것이다. 6개의 데이터가 존재한다. 맨 처음 값이 12이다. 그 위치 이후부터 맨 끝 위치까지 검사해보니 12보다 작은 최솟값인 7을 선택한다. 그리고 서로의 위치를 바꾼다. 그리고 두 번째로 넘어간다. 두 번째 값은 10이다.  위치 이후부터 맨 끝 위치까지 검사해보니 10보다 작은 최소값인 9를 선택한다. 그리고 서로의 위치를 바꾼다. 이 작업을 5번째까지 반복하면 정렬된 데이터 결과가 나온다.

 

선택 정렬의 의사 코드는 다음과 같다.

selection_sort(A, n)

for i <- 0 to n - 2 do
    least <- A[i], A[i+1], ..., A[n-1] 중 가장 작은 인덱스;
    A[i]와 A[least]의 교환;
    i++;

입력 배열 이외에 추가적인 메모리가 필요하지 않은 것에 유의하자. 이러한 방법들을 제자리 정렬(in-place sorting)이라고 한다.

 

C++ 코드로 구현하면 다음과 같다.

#include <iostream>
using namespace std;

class SelectionSort
{
public:
	void PrintNotSort(int Arr[], int size)
	{
		cout << "정렬되지 않은 배열 : " << endl;
		PrintArr(Arr, size);
		cout << endl;
	}
	void PrintSort(int Arr[], int size)
	{
		int* tmpArr = new int[size];
		memcpy(tmpArr, Arr, sizeof(int) * size);
		SortProcess(tmpArr, size);

		cout << "정렬된 배열 : " << endl;
		PrintArr(tmpArr, size);

		delete[] tmpArr; 
		tmpArr = nullptr;
	}

private:
	// 선택 정렬 연산
	void SortProcess(int Arr[], int size)
	{
		for (int i = 0; i < size - 1; ++i)
		{
			int min = Arr[i];
			int minIndex = i;
			for (int j = i + 1; j < size; ++j)
			{
				if (min > Arr[j])
				{
					min = Arr[j];
					minIndex = j;
				}
			}
			Swap(Arr[i], Arr[minIndex]);
		}
	}
	// 서로의 위치 변경
	void Swap(int& A, int& B)
	{
		int tmp = A;
		A = B;
		B = tmp;
	}
	// 배열 출력
	void PrintArr(int Arr[], int size)
	{
		for (int i = 0; i < size; ++i)
		{
			cout << "[" << Arr[i] << "] ";
		}
		cout << endl;
	}
};

int main()
{
	SelectionSort s;

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

	s.PrintNotSort(Test, 10);
	s.PrintSort(Test, 10);
}

 

출력 값

 

 

시간 복잡도

선택 정렬 연산은 이중 for문을 사용해야 가능하기 때문에 시간 복잡도는 O(n^2)이다. 

 

삽입 정렬

삽입 정렬(insertion sort)은 카드를 정렬하는 방법과 유사하다. 손안에 정렬된 카드가 있고, 카드를 추가로 한 장씩 더 받을 때마다 그 카드를 올바른 자리에 넣는 것이다. 물론 삽입 후에도 전체 카드는 정렬이 되어 있어야 한다. 이 과정을 새로 받는 모든 카드에 대해 수행하면 전체 카드가 정렬된다.

 

다음 그림은 삽입 정렬 과정을 표현해놓은 것이다. 선택 정렬과 다르게 두 번째 위치부터 시작한다. 두 번째 위치의 값은 7이다. 7 위치의 앞 데이터들을 검사한다. 첫 번째 위치가 3이므로 7은 올바른 위치에 와있다. 그러므로 변화는 없다. 세 번째 위치의 값은 2이다. 2 위치의 앞 데이터들을 검사한다. 2는 3보다 작으므로 2는 첫 번째 위치에 와야 한다. 3과 7을 뒤로 한 칸 이동시켜 첫 번째 위치에 공간을 만든 후 2를 집어넣는다. N개의 데이터가 있다면, 이 작업을 두 번째 위치에서부터 시작해서 N번째가 까지 반복하는 것이 삽입 정렬이다.

 

다음은 삽입 정렬의 의사 코드이다.

insertion_sort(A, n)

for i <- 1 to n - 1 do
    key <- A[i];
    j <- i-1;
    while j >= 0 and A[j] > key do
        A[j+1] <- A[j];
        j <- j-1;
    A[j+1] <- key;

 

C++ 코드로 구현하면 다음과 같다. 나머지는 위 코드와 같으므로 생략한다.

// 삽입 정렬 연산
void SortProcess(int Arr[], int size)
{
	for (int i = 1; i < size; ++i)
	{
		int j = 0;
		int value = Arr[i];
		// 값을 넣을 올바른 위치를 찾는다. 
		// 찾는 동안 뒤로 한칸씩 땡긴다. 
		for (j = i - 1; j>=0 && Arr[j] > value; --j)
		{
			Arr[j + 1] = Arr[j];
		}
		// 올바른 위치에 값을 넣는다.
		Arr[j + 1] = value;
	}
}

출력 값은 위와 같다.

 

시간 복잡도

삽입 정렬의 복잡도는 입력 자료의 구성에 따라 달라진다. 이미 자료가 정렬되어 있는 경우는 가장 빠르다. 내부 루프가 모든 항목에서 한 번 만에 빠져나올 것이기 때문이다. 이 경우 시간 복잡도는 O(n)이다.

 

최악의 경우는 입력 자료가 역으로 정렬된 경우이다. 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다. 따라서 외부 루프와 내부 루프 모든 순회를 하기 때문에 이중 for문이므로 O(n^2)이다.

 

버블 정렬

버블 정렬(bubble sort)은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방법이다. 이러한 비교-교환 과정은 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 비교-교환 과정이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이것은 마치 거품(bubble)이 보글보글 떠오르는 것과 유사하여 버블 정렬이라고 부른다. 비교-교환 과정은 더 이상 교환이 일어나지 않을 때까지 계속된다. 다음 그림은 버블 정렬의 과정을 보여주고 있다.

 

리스트를 한번 스캔하면 오른쪽 끝에 가장 큰 레코드가 위치하게 되고 전체 리스트는 오른쪽의 정렬된 부분과 정렬이 안 된 왼쪽 부분으로 나누어진다. 이러한 스캔 과정은 더 이상 교환이 일어나지 않을 때까지 수행된다.

 

다음은 버블 정렬의 의사 코드이다.

bubble_sort(A, n)

for i <- n-1 to 1 do
    bChanged <- FALSE;
    for j <- 0 to i-1 do
        if( A[j] > A[j+1] )
            A[j]와 A[j+1]을 교환;
            bChanged <- TRUE;
        if( bChanged == FALSE ) return;
        j++;
    i--;

 

C++ 코드로 구현하면 다음과 같다.

// 버블 정렬 연산
void SortProcess(int Arr[], int size)
{
	bool changed = false;
	for (int i = size - 1; i > 0; --i)
	{
		changed = false;
			// 스캔 작업
		for (int j = 0; j < i; ++j)
		{
			// 교환 발생
			if (Arr[j] > Arr[j + 1])
			{
				Swap(Arr[j], Arr[j + 1]);
				changed = true;
			}
		}
			// 교환이 없으면 종료
		if (changed == false) break;
	}
}

 

시간 복잡도

버블 정렬은 이중 for문으로 돌아가므로 시간 복잡도는 O(n^2)이다.

 

함수 포인터를 사용한 정렬

지금까지는 오름차순으로 데이터를 정렬했다. 만약 내림차순으로 정렬을 하고 싶을 때는 어떻게 할 수 있을까? 하나의 방법은 동일한 함수를 만들고 비교의 방향을 반대로 바꿔주면 된다. 더 나은 방법은 비교 함수를 따로 만들어 주고, 정렬 함수를 호출할 때 매개변수로 함수 포인터를 전달하는 방법이다. 비교 함수는 다음과 같이 만들 수 있다.

int ascend (int x, int y) { return y - x; }   // 오름차순 비교함수
int descend (int x, int y) { return x - y; }  // 내림차순 비교함수

x와 y가 같으면 0을 다르면 양이나 음의 값을 반환하는 함수이다. 이제 정렬 함수에서는 항목의 키 값을 직접 비교하지 않고 이 함수를 이용해 비교한다. 다음 코드는 삽입 정렬을 비교 함수를 이용하는 방법으로 변경한 코드이다.

// 삽입 정렬 연산
void SortProcess(int Arr[], int size, int (*cmp_func)(int, int))
{
	for (int i = 1; i < size; ++i)
	{
		int j = 0;
		int value = Arr[i];
		// 값을 넣을 올바른 위치를 찾는다. 
		// 찾는 동안 뒤로 한칸씩 땡긴다. 
		for (j = i - 1; j>=0 && cmp_func(Arr[j], value); --j)
		{
			Arr[j + 1] = Arr[j];
		}
		// 올바른 위치에 값을 넣는다.
		Arr[j + 1] = value;
	}
}

cmp_func 함수 포인터를 매개변수로 받는다. 이제 이 매개변수에 ascend나 descend를 넣어주면 리스트를 오름차순이나 내림차순으로 정렬시킬 수 있게 된다.

SortProcess(tmpArr, size, ascend);  // 오름차순으로 선택 정렬
SortProcess(tmpArr, size, descend); // 내림차순으로 선택 정렬

이것은 다른 정렬 함수 알고리즘에도 동일하게 적용할 수 있다. 이 방식은 보다시피 장점이 많아 널리 사용되고 있다. (심지어 정렬 라이브러리에서도)

 

셸 정렬

셸 정렬(shell sort)은 Donald L. Shell이라는 사람이 제안한 방법으로, 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안했다.  

 

삽입 정렬과 달리 셸 정렬은 전체 리스트를 한꺼번에 정렬하지 않는다. 리스트를 일정한 기준에 따라 분류해 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만들어 앞의 과정을 되풀이한다. 이 과정은 부분 리스트의 개수가 1이 될 때까지 반복된다.

 

다음 그림은 셸 정렬에 대한 과정을 표현한 것이다.

 

i(1)에서는 8(=최대 개수 / 2)만큼 떨어진 요소들끼리 묶어 부분 리스트로 만들고 정렬 작업을 수행한다.. 

{20, 23} {12, 88} {65, 2} {8, 56} {10, 41} {16, 27} {43, 67} {35, 56} // 정렬 전
{20, 23} {12, 88} {2, 65} {8, 56} {10, 41} {16, 27} {43, 67} {35, 56} // 정렬 후

i(2)에서는 8의 절반인 4만큼 떨어진 요소들끼리 묶어 부분 리스트로 만들고 정렬작업을 수행한다.

{20, 10, 23, 41} {12, 16, 88, 27} {2, 43, 65, 67} {8, 35, 56, 56} // 정렬 전
{10, 20, 23, 41} {12, 16, 27, 88} {2, 43, 65, 67} {8, 35, 56, 56} // 정렬 후

i(3)에서는 4의 절반인 2만큼 떨어진 요소들끼리 묶어 부분 리스트로 만들고 정렬 작업을 수행한다.

{10, 2, 20, 43, 23, 65, 41, 67} {12, 8, 16, 35, 27, 56, 88, 56} // 정렬 전
{2, 10, 20, 23, 41, 43, 65, 67} {8, 12, 16, 27, 35, 56, 56, 88} // 정렬 후

i(4)에서는 2의 절반인 1만큼 떨어진 요소들끼리 묶어 부분 리스트로 만들고 정렬작업을 수행한다.

{2, 8, 10, 12, 20, 16, 23, 27, 41, 35, 43, 56, 65, 56, 57, 88} // 정렬 전
{2, 8, 10, 12, 16, 20, 23, 27, 35, 41, 43, 56, 56, 65, 67, 88} // 정렬 후

이때 부분 리스트의 개수가 1개 이므로 정렬 연산은 끝이 난다.

 

다음은 셸 정렬을 구현한 C++ 코드이다.

// 부분 리스트들을 삽입 정렬
static void sortGapInsertion(int Arr[], int range_first, int range_last, int gap)
{
    int key = 0;
    for(int i = first + gap; i <= last; i += gap)
    {
        key = Arr[i];
        for(int j = i - gap; j >= first && key < Arr[j]; j -= gap)
            Arr[j+gap] = Arr[j];
        Arr[j+gap] = key;
    }
}

// 셸 정렬 연산
void SortProcess(int Arr[], int size)
{
	for (int gap = size/2; gap > 0; gap /= 2)
	{
		if((gap % 2) == 0) gap++; // gap이 짝수이면 1을 더함
        for(int i = 0; i < gap; ++i) // 부분 리스트의 개수는 gap이다
            sortGapInsertion(Arr, i, n-1, gap);
	}
}

 셸 정렬은 삽입 정렬에 비해 2가지의 장점이 있다.

 

1. 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동한다. 따라서 교환하는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

 

2. 부분 리스트가 하나가 되면 셸 정렬은 전체 리스트를 정렬해야 한다. 그러나 거의 정렬된 리스트에 대한 삽입 정렬이므로 매우 효율적으로 수행한다.

 

실험적인 연구를 통해 셸 정렬의 시간 복잡도는 O(n^2)이지만 평균적인 경우에는 O(n^1.5)인 것으로 알려져 있다.

 

병합 정렬

앞에서 봤던 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 충분히 좋은 방법들이다. 그러나 자료가 많거나 자주 정렬해야 할 필요가 있으면 보다 빠른 방법을 사용해야 한다. 앞에서 본 방법들보다 훨씬 빠른 방법들을 살펴보도록 하겠다.

 

병합 정렬(merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이것은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 하나의 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 

 

분할 정복 기법의 개념

배열을 병합 정렬을 이용해 처리하는 과정을 살펴보자. 다음과 같은 단계들로 이루어진다.

 

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

 

2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할 정복 기법을 적용한다.

 

3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 통합한다.

 

이러한 병합 정렬 알고리즘은 다음과 같이 표현된다.

merge_sort(list, left, right)

if left < right
    mid = (left+right) / 2;
    merge_sort(list, left, mid);
    merge_sort(list, mid+1, right);
    merge(list, left, mid, right);

병합 정렬에서 실제 정렬이 이루어지는 시점은 2개의 리스트를 병합(merge)하는 단계이다. 2개의 배열의 요소들을 처음부터 하나씩 비교하여 두 요소 중에서 더 작은 요소를 새로운 배열로 옮기는 과정을 반복한다. 이것은 하나의 배열이 모두 끝날 때까지 반복하고, 다른 배열의 남은 요소들을 전부 새로운 배열로 복사하면 병합이 종료된다. 다음 그림은 그 과정을 보여주고 있다.

 

출처 : https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

다음은 병합 연산의 의사 코드이다.

merge(list, left, mid, last)
// 2개의 인접한 배열 list[left~mid]와 list[mid+1~right]를 병합

i <- left;
e1 <- mid;
j <- mid+1;
e2 <- right;
sorted 배열을 생성
k <- 0;
while i <= e1 and j <= e2 do
    if(list[i] < list[j])
        then
            sorted[k++] <- list[i++];
        else
            sorted[k++] <- list[j++];
요소가 남아있는 부분배열을 sorted로 복사한다.
sorted를 list로 복사한다.

 

다음은 병합 정렬의 C++ 코드이다.

// 부분 리스트의 병합 연산
static void merge(int Arr[], int left, int mid, int right)
{
    int i = 0, j = 0, l = 0, k = left;                 // 정렬될 리스트에 대한 인덱스
    static int sorted[MAX_SIZE    // 병합된 리스트 저장을 위한 임시배열
    // 분할 정렬된 list를 병합
    for(i = left, j = mid + 1; i <= mid %% j <=right; )
        sorted[k++] = (list[i] <= list[j]) ? list[i++] : list[j++];  
    // 한쪽에 남아 있는 레코드의 일괄 복사
    if(i > mid)
    {
        for(l = j; l <= right; l++, k++)
            sorted[k] = list[l];
    }
    else
    {
        for(l = i; l <= mid; l++, k++)
            sorted[k] = list[l];
    }
    // 배열 sorted[]의 리스트를 배열 Arr[]로 다시 복사
    for(l = left; l <= right; l++)
        list[l] = sorted[l];
}

// 병합 정렬
void SortProcess(int Arr[], int left, int right)
{
	if(left < right)
    {
        int mid = (left+right) / 2;      // 리스트를 균등 분할
        merge_sort(list, left, mid);     // 왼쪽 부분 리스트 정렬
        merge_sort(list, mid+1, right);  // 오른쪽 부분 리스트 정렬
        merge(list, left, mid, right);   // 병합
    }
}

 

시간 복잡도

병합 정렬은 재귀 호출 구조로 되어 있다. 일반적으로 요소의 개수 n이 2^k라고 하면 부분 배열의 크기는 2^k -> 2^(k-1) -> ... -> 2^0 이 되어 재귀 호출 깊이가 k가 된다. 그러므로 k = log2N이다.  그리고 부분 배열을 병합하는 연산에서 최대 n번의 비교 연산이 일어날 수 있다. 이제 이 부분 배열의 요소들을 정렬되도록 순서대로 임시 배열에 이동해줘야 한다. 이 이동연 산은 요소의 개수가 n개인 경우 레코드의 이동이 2n번 일어난다. 

 

최종적으로 총 (N(비교) + 2N(이동)) * log 2 N(분할) = 3Nlog2N 번의 연산이 필요하다. 빅오 표기법으로 병합 정렬은 O(Nlog2N)의 복잡도를 가지는 알고리즘이다. 이는 전에 봤던 정렬 기법들보다 매우 효율적이다. 또한 최악, 평균, 최선의 경우에도 모두 동일한 시간이 걸린다는 장점이 있다. 하지만 단점은 정렬된 배열을 옮길 임시 배열이 필요하다는 것이다. 

 

퀵 정렬

퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 병합정렬과 같이 분할-정복법을 사용한다. 하지만 병합 정렬과 다르게 균등한 분할을 할 필요가 없다.

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

먼저 리스트 안에 있는 한 요소를 피봇(pivot)으로 선택한다. 위 그림에서는 첫 번째 요소를 피봇으로 선택하였다. 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로 옮기고 피봇보다 큰 요소들은 모두 피봇의 오른쪽으로 옮긴다. 결과적으로 피봇을 중심으로 왼쪽은 작은 요소들로 구성되고 오른쪽은 큰 요소들로 구성된다. 이 상태에서 피봇을 제외한 왼쪽, 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

 

어떻게 피봇을 기준으로 나누어진 부분 리스트를 정렬할까? 여기서도 재귀호출이 사용된다. 부분 리스트에서도 다시 피봇을 정하고 피봇을 기준으로 2개의 부분 리스트로 나누는 과정이 되풀이되다. 이 과정은 더 이상 부분 리스트로 분할할 수 없을 때까지 반복된다.

 

퀵 정렬 함수 코드는 다음과 같다.

void quick_sort(int list[], int left, int right)
{
    int q;
    if(left < right) // 정렬 범위가 2 이상일 경우 => 계속 분할할 수 있다.
    {
        q = partition(list, left, right); // 좌우로 분할
        quick_sort(list, left, q-1); // 왼쪽 부분리스트 퀵정렬
        quick_sort(list, q+1, right); // 오른쪽 부분리스트 퀵정렬
    }
}

퀵 정렬에서 가장 중요한 함수는 partition()이다. 이 함수는 데이터가 들어 있는 배열 list의 left부터 right까지를, 피봇을 기준으로 2개의 부분 리스트로 나눈다. 나누는 과정은 다음과 같다.

 

출처 : https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

피봇값 5를 선택하고, 변수 low와 high는 각각 왼쪽 부분 리스트와 오른쪽 부분 리스트를 만드는 데 사용된다. low는 왼쪽에서 오른쪽으로 탐색해가다가 피봇보다 큰 항목을 찾으면 멈춘다. hight는 반대 방향으로 탐색하다가 피봇보다 작은 항목을 찾으면 멈춘다. 이 항목들은 부분 리스트에 적합하지 않으므로 low와 high를 서로 교환한다. 이러한 교환 과정을 반복하다 보면 high와 low가 언젠가 엇갈리게 된다. 마지막으로 high가 가리키는 데이터와 피봇을 서로 교환하면, 피봇을 중심으로 왼쪽은 작은 항목, 오른쪽은 큰 항목만 남는다. 코드로 구현하면 다음과 같다.

int partition(int list[], int left, int right)
{
    int tmp;
    int low = left + 1;
    int high = right;
    int pivot = list[left];
    while(low < high) // 역전되지 않는 한 반복
    {
        // 각각 교환할 위치를 먼저 찾는다. 
        for(; low < right && list[low] < pivot; ++low);
        for(; high >= left && list[high] > pivot; ++high);
        if(low < high)  // 아직 교차하지 않았으면 선택된 두 레코드 교환
            SWAP(list[low], list[high], tmp);
    }
    SWAP(list[left], list[high], tmp); // high와 피봇항목 교환
    return high;
}

시간 복잡도

n개의 레코드를 가지는 리스트를 n / 2^k의 크기로 나누어질 것이다. 크기가 1이 될때까지 나누어지므로 n / 2^k = 1일 때까지 나누어질 것이고 따라서 k = log2N 개의 패스가 필요하게 된다. 각각의 패스에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어진다. 따라서 퀵 정렬은 평균적으로 O(Nlog2N) 알고리즘이 된다. 

 

퀵 정렬 최악의 효율을 내는 경우는 정렬이 되어 있는 상태의 리스트일때다. 리스트의 첫 번째 레코드를 피봇으로 설정하면, 왼편 리스트가 텅 비게 되는 불균형 분할이 연속해서 이루어진다. 이 경우 레코드의 수만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 n^2 번 실행하게 된다. 따라서 최악의 경우 O(n^2)의 시간 복잡도를 가진다.