[알고리즘] 정렬 알고리즘 #2 (퀵 정렬, qsort() 함수)

💻 오늘의 목표 : 퀵 정렬 완전 정복

[정렬 알고리즘 개념, 버블정렬, 삽입정렬, 선택정렬]

저번엔 정렬 알고리즘의 개념과, 버블정렬, 선택정렬, 삽입정렬에 대해 알아봤다.

[알고리즘] 정렬 알고리즘 #1 (정렬 알고리즘 개념, 버블정렬, 선택정렬, 삽입정렬)

 

오늘은 여러 가지 정렬을 더 알아보자!

 

 

[퀵 정렬(Quick Sort)]

[퀵 정렬 개념]

• 분할 정복 방식을 사용한 정렬 알고리즘

이름에서 알 수 있다시피 (Quick : 빠른) 굉장히 빠른 정렬 알고리즘이다.

[분할 정복 방식(Divide and Conquer)?]

• 문제를 작은 단위로 분할하여 각각 해결하고, 그 결과를 합쳐서 원래 문제의 해를 구하는 방식이다.
• 재귀적으로 구현되며, 큰 문제를 작은 문제들로 쪼개서 해결한 후 결과를 합쳐 전체 문제의 해를 구한다.
• 분할 정복 방식을 사용하는 알고리즘은 '퀵 정렬'과 '병합 정렬' 등이 있다.

 

[분할 정복 방식의 단계]

1. 문제를 작은 단위로 분할
2. 각각의 작은 문제를 재귀적으로 해결
3. 작은 문제의 해를 합쳐 전체 문제의 해를 구함

[퀵 정렬 알고리즘 동작 방식]

퀵 정렬 알고리즘 동작 방식에 중요한 것이 있다. 바로

• 기준 요소 선정
• 분할의 반복

기준이 되는 요소를 Pivot이라고 부른다.

Pivot은 (회전하는 물체의 균형을 잡아 주는) 중심점[축]이라는 뜻을 가지고 있다.

즉, 기준을 잡는 중심점(Pivot)이 중요하다!

 

1. 임의의 Pivot을 선택한다 : 배열의 첫 번째 값, 마지막값, 중간값 등 여러 가지 기준 설정 가능
2. Pivot을 중심으로 작은 값은 왼쪽, 큰 값은 오른쪽에 옮긴다. (배열을 두 개로 분할)
3. 분할된 두 개의 배열에 대해 재귀적으로 퀵정렬을 수행한다. (배열의 크기가 1 이하가 될 때까지 반복)
4. 정렬된 두 개의 배열을 합병한다.

[퀵 정렬 알고리즘 C언어 구현]

퀵 알고리즘을 C언어에서 배열로 구현하는 경우, Pivot의 값보다 크거나 작은 값을 옮길 때 문제가 발생한다.

값을 하나하나 바꿔주어야 하는데, 이때 오버헤드가 크다는 문제점이 있다.

그래서 아래와 같은 방식으로 코드를 구현한다.

Pivot을 제외한 나머지 배열의 양끝에서 Pivot 보다 큰 값이 왼쪽에 있거나, Pivot보다 작은 값이 왼쪽에 있으면 서로 값을 바꾸어가면서, 마지막으로 서로 만날 때까지 이 작업을 수행한다.

위의 작업이 다 끝나면, Pivot보다 작은 값들 중에 가장 오른쪽에 있는 숫자와 Pivot의 자리를 바꾸어준다.

그러면 배열은 자동적으로 피벗보다 작은 배열이 왼쪽, 큰 배열이 오른쪽에 생긴다.

 

그리고 Pivot을 기준으로 생긴 두 개의 배열을 다시 정렬할 때는 재귀를 활용하여 코드를 작성한다.

#include <stdio.h>

int Partition(int arr[], int Left, int Right) {

	int First = Left;
	int Pivot = arr[First];
	int temp;

	++Left;

	while (Left <= Right) {
		while (arr[Left] <= Pivot && Left < Right)
			++Left;

		while (arr[Right] >= Pivot && Left <= Right)
			--Right;

		if (Left < Right) {
			temp = arr[Left];
			arr[Left] = arr[Right];
			arr[Right] = temp;
		}
		else
			break;

	}

	temp = arr[First];
	arr[First] = arr[Right];
	arr[Right] = temp;

	return Right;
}

void QuickSort(int arr[], int Left, int Right) {

	if (Left < Right) {
		int index = Partition(arr, Left, Right);

		QuickSort(arr, Left, index - 1);
		QuickSort(arr, index + 1, Right);
	}
}

int main() {
	int arr[6] = { 5,3,1,6,4,2 };

	QuickSort(arr, 0, 5);

	for (int i = 0; i < 6; i++) {
		printf("%d ", arr[i]);
	}

	return 0;
}

 

[퀵 정렬 알고리즘 성능 측정]

퀵 정렬 알고리즘은 버블정렬이나 선택, 삽입 정렬과는 다르게 재귀를 이용하여 정렬을 수행한다.

따라서 성능을 측정할 때 반복문의 횟수가 아닌 재귀함수를 얼마나 많이 반복하느냐, 재귀함수의 깊이를 파악해야 한다.

 

퀵 정렬 알고리즘은 데이터가 미리 정렬되어 있거나, 역순으로 정렬된 경우 최악의 성능을 보인다.

데이터가 무작위로 배치된 경우 최고의 성능을 보여준다.

 

따라서 자료구조의 크기가 n일 때, 퀵 정렬은 log₂n의 재귀 호출 깊이를 가진다.

그리고 분할을 하기 위한 비교 횟수는 자료구조의 크기가 n일 때 n이다.

따라서 최선의 경우 퀵정렬의 성능은 nlog₂n!

 

버블, 선택, 삽입 정렬보다 훨씬 좋은 성능을 보인다.

---

[C언어 표준 라이브러리 퀵 정렬 함수 : qsort()]

위처럼 직접 퀵 정렬을 수행하는 알고리즘을 작성할 수 있지만,

C언어에서는 퀵 정렬 함수를 제공하고 있다.

 

#include <stdlib.h> 헤더 코드를 작성해 주면 아래와 같은 함수를 사용할 수 있다.

void qsort(void *_Base, size_t _NOE, size_t _SOE, int (*_PtFuncCompare)(void const *, void const *));

• Base: 정렬하고자 하는 배열의 포인터
• NOE(NumberOfElements): 배열의 각 원소들의 총 수
• SOE(SizeOfElements): 배열에서 원소 하나의 크기
• (*_PtFuncCompare): 비교를 수행할 함수 포인터
  C언어에서는 함수를 선언하고 구현한 후에 다음처럼 포인터로 특정 함수를 지정할 수 있다.

 

 

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

int Compare(const void* num1, const void* num2) {
	int* first = (int*)num1;
	int* second = (int*)num2;

	if (*first > * second)
		return 1;
	else if (*first < *second)
		return -1;
	else
		return 0;
}

int main() {
	int arr[] = { 5,3,1,6,4,2 };
	int array_size = sizeof(arr) / sizeof(int);
	
	qsort(arr, array_size, sizeof(int), Compare);

	for (int i = 0; i < 6; i++) {
		printf("%d ", arr[i]);
	}

	return 0;
}

 

[내림차순 정리를 하고 싶은 경우]

int Compare(const void* num1, const void* num2) {
	int* first = (int*)num1;
	int* second = (int*)num2;

	if (*first < * second)
		return 1;
	else if (*first > *second)
		return -1;
	else
		return 0;
}

내림차순의 경우에는 Compare 함수 안에서 조건문의 부등호 방향을 바꾸어주면 된다.

 

[백준 2751번]

그럼 qsort() 함수를 사용하는 문제를 풀어보자!

2751번: 수 정렬하기 2

 

이 문제는 qsort() 함수만 사용한다면, 충분히 해결할 수 있다!

 

#include <stdlib.h>
#include <stdio.h>

int Compare(const void* num1, const void* num2) {
	int* first = (int*)num1;
	int* second = (int*)num2;

	if (*first > * second)
		return 1;
	else if (*first < *second)
		return -1;
	else
		return 0;
}

int main() {
	int N;
	scanf("%d", &N);

	int* arr = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	
	qsort(arr, N, sizeof(int), Compare);

	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}

	return 0;
}

 

여기까지 퀵정렬 알고리즘, qsort() 함수까지 공부 완료~!

---

컴퓨터 프로그래밍 전공하는 대학생이 공부했던 내용을 정리하기 위해 적는 소소한 블로그입니다.
잘못된 내용은 댓글에 달아주시면 피드백 감사히 받겠습니다!

[참고한 도서]
- 데이터 구조 원리와 응용
- 이것이 자료구조 + 알고리즘이다
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략