altair의 프로젝트 일기

정렬 알고리즘을 살펴보다보면 C언어에서 라이브러리에 퀵 정렬 함수가 있다는 것을 알게 된다. 이번에 정렬 알고리즘을 배우면서 qsort 함수를 실행하고 내가 직접 구현한 퀵 정렬과 그 실행시간을 비교할 기회가 있었다. 가장 간단한 퀵 정렬 알고리즘은 최악의 경우 \(O(n^2)\) 의 시간 복잡도를 갖는다. 정렬되지 않은 배열을 정렬할 때 $$log_{2}n$$의 재귀 단계를 가지지만, 피벗을 기준으로 파티션이 극단적으로 나뉠 때는 $$n^2$$의 단계를 갖는다. 많이 쓰이는 힙 정렬은 비록 퀵 정렬보다 살짝 느리지만 이런 최악의 경우를 갖지 않고 항상 안정적인 시간 복잡도를 갖는다는 장점이 있다. 이번 프로젝트에서 확인했던 일반적인 퀵 정렬 알고리즘의 실행시간은 다음과 같다. 데이터 개수는 5만개로 하..