[알고리즘] 퀵 정렬 함수 - qsort()

문제를 풀다가 유용해보이는 정렬함수를 찾았다! 바로 퀵 정렬을 구현하는 C언어의 stdlib.h 내장함수, qsort! 주로 사용하던 버블 정렬보다 퀵 정렬의 시간복잡도가 훨씬 빠른 것으로 알고 있긴 했지만,, 어려워서 미루다가 이번에 조금 알아보았다!

퀵정렬이란?

퀵정렬로 이름을 지을 만큼 빠른 퀵정렬은 전쟁 전략 중 하나인 분할정복에 바탕을 둔 알고리즘이다. 전체를 공략하는 대신, 전체를 잘게 나누어 공략하는 것이다. 퀵 정렬의 동작과정은 한마디로 기준요소를 선정하고 분할하는 것의 반복이다.

📌
자료구조에서 기준요소(Pivot)를 선정하고 이보다 작은 값을 가진 요소는 기준에서 왼쪽으로, 큰 값은 오른쪽으로 옮긴다.
분할이 일어나 왼쪽과 오른쪽 그룹으로 나누어지면, 위의 과정을 반복한다.
그룹의 크기가 1 이하가 될 때까지 반복하면 정렬 완료.

퀵 정렬의 평균 복잡도는 𝛩(nlogn)으로 매우 빠르지만 최악의 경우, 𝛩(n^2)으로 버블정렬과 비슷한 효과를 낼 수 있다. 퀵정렬 구현 코드와 복잡도 구하는 방법은 다음에 기회가 되면 다뤄보는 것으로...

정렬 별 시간 복잡도는 아래 표에서 확인 할 수 있다. 예시 런타임을 보니 이래서 퀵정렬이구나 싶은 생각과 함께.. 이래서 버블정렬로 백준 풀 때 가끔씩 시간초과가 나는구나,, 깨달았다

$O(1) < O(logN) < O(N) < O(N*logN) < O(N^2) < O(2^N) < O(N!)$
오른쪽으로 갈수록 시간 복잡도가 큰 경우!

그래서 qsort()가 뭔데?

qsort()는 C언어 표준 라이브러리(stdlib.h)에서 지원하는 퀵정렬 알고리즘 구현 함수이다. 복잡한 퀵정렬을 직접 구현하지 않고도 빠르게 정렬할 수 있다니,, 너무 신기하고 편리했다!

qsort() 구현 코드

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

int ComparePoint(const void* _elem1, const void* _elem2) {
	int* elem1 = (int*)_elem1; // void*형인 _elem1을 int*형으로 형변환
	int* elem2 = (int*)_elem2; // void*형인 _elem2을 int*형으로 형변환
	if (*elem1 > *elem2) return 1; // *elem1이 더 크다
	else if (*elem1 < *elem2) return -1; // *elem2이 더 크다
	else return 0; // 둘의 크기가 같다
}
// 오름차순 정렬 qsort()함수
// *elem1과 *elem2을 비교할 때 부등호를 바꾸면 내림차순 정렬이 된다.

int main() {
	int Dataset[] = { 6, 4, 2, 3, 1, 5 };
	int length = sizeof Dataset / sizeof Dataset[0]; // 배열의 크기를 구함.
	int i = 0;
	qsort((void*)Dataset, length, sizeof(int), ComparePoint);
    // 배열과 배열의 크기, 개별 데이터 요소의 크기, 비교함수를 qsort()에 넘겨줌
	for (int i = 0; i < 6; i++) {
		printf("%d ", Dataset[i]); // 정렬된 배열 출력
	}
}

1 2 3 4 5 6

리뷰

알고리즘 공부의 필요성을 느끼고,, 배우면서 정리도 해보니 신기하고 재밌었다! 그리고 소프트웨어 수학에서 배웠던 내용보니 반가웠다.. 학교 공부를 열심히 해야하는 이유~.. 다음 포스팅에서는 이를 활용한 백준 문제 풀이를 가져올 예정 :)