[Section 6] 정렬 알고리즘의 종류와 특징

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

정렬(Sorting) 알고리즘의 의의는 문제의 복잡성(Complexiy)을 획기적으로 줄여준다는 점에 있다. 그리고 데이터 베이스를 구축하는데 중요한 이 정렬 알고리즘의 분류와 대표 알고리즘을 간단히 알아보자.

1. 정렬 알고리즘의 분류 _ 어떤 수단을 이용하는가?

어떤 리스트 내에 존재하는 데이터의 특정한 순서를 수 관점에서 낮은 수부터 높은 수로 나타내는 것을 오름차순(Ascending) 정렬, 높은 수부터 낮은 수로 정렬할 것을 내림차순(Descending) 정렬이라고 한다. 그렇다면, 정렬 알고리즘은 어떤 방법으로 데이터를 체계화할까? 정렬 알고리즘은 대표적으로 약 8가지의 방법으로 분류가 이루어지는 것으로 알려져 있다. 가장 먼저, 데이터 수의 비교 또는 교환을 통해서 정렬을 구현할 수 있다. 그리고 각각 메모리 사용량, 재귀, 안정성, 그리고 적합성으로 정렬 알고리즘을 분류하기도 한다.

 

정렬 알고리즘의 분류

2. 구현해볼 대표적 정렬 알고리즘 _ 어떤 알고리즘을 배워야 하는가?

흔히 퀵 정렬(Quick Sort)이라고도 불리는 재귀적 분류의 특징은 반복문을 사용 여부에 따라 분류가 결정된다. 대표적으로 버블 정렬(Bubble Sort)이 이 재귀 방법을 이용한 정렬 알고리즘이다. 재귀적 방법을 사용하지 않은 정렬 또한 비-재귀(Non-recursive) 정렬로 분류한다. 하지만, 실질적으로 이용하는 알고리즘들은 혼합적인 알고리즘이 많다. 따라서 우리는 분류에 따른 알고리즘이 아니라 어떤 알고리즘을 배우는 가에 초점을 맞추기로 하자.

구현이 쉬운 정렬 알고리즘 _ 버블 (Bubble), 삽입(Inserction), 그리고 선택 정렬(Selection Sort)

버블, 삽입, 그리고 선택 정렬은 구현이 쉽다는 장점을 가지고 있다. 따라서 현업에서도 많이 사용되는 정렬 알고리즘이라 할 수 있겠다. 다음은 위 3가지 정렬 알고리즘의 복잡도를 비교한 표이다.

 

	버블 정렬	삽입 정렬	선택 정렬
시간 복잡도 _ 최악	n2	n2	n2
시간 복잡도 _ 최고	n	n2	n2
시간 복잡도 _ 평균	n2	n2	n2
공간 복잡도 _ 최악	1	n2 (전체)	1

 

* 알고리즘의 특징과 구현 방법은 이후의 내용을 참고하기로 하자. 

혼합된 방법으로 구현하는 정렬 알고리즘 _ 힙(Heap), 퀵(Quick), 그리고 합병 정렬(Merge Sort)

비교적 복잡한 힙, 퀵, 그리고 합병 정렬은 혼합된 방법으로 정렬을 구현한다. 조금은 어렵지만, 배워두면 나쁘지 않은 알고리즘이므로 한 번 구현해 보도록 하자. 다음은 위 4가지 정렬 알고리즘의 복잡도를 비교한 표이다. 퀵 정렬을 제외한 정렬 알고리즘의 복잡도는 빅-세타 노테이션 표기법을 생략한 것이다.

 

	힙 정렬	퀵 정렬	합병 정렬
시간 복잡도 _ 최악	nlog(n)	O(n2)	nlog(n)
시간 복잡도 _ 최고	nlog(n)	O(nlog(n))	nlog(n)
시간 복잡도 _ 평균	nlog(n)	O(nlog(n))	nlog(n)
공간 복잡도 _ 최악	n	O(1)	n

 

* 알고리즘의 특징과 구현 방법은 이후의 내용을 참고하기로 하자. 

기타 정렬 알고리즘 _ 위상(Topological), 그리고 트리 정렬(Tree Sort)

위상과 트리 정렬은 데이터베이스의 형태가 비선형 구조를 가질 때 유용하고 대표적인 정렬방법이므로 반드시 알아야 한다. 이 정렬 방법은 이전의 트리와 그래프 알고리즘을 참고하도록 하자.