[C언어 알고리즘] 정렬(1) - 개요

알고리즘에 대한 첫번째 포스팅으로 정렬(Sort)을 선택했습니다. 정렬(Sort)은 컴퓨터를 통해 문제해결을 하는데 역사와 함께 했으며, 가장 연구가 많이 되어 왔습니다.

줄을 서시오~

정렬의 기본 개념은 매우 간단한데요, 바로 "줄을 서시요~" 입니다. 줄을 세울 대상을 자료(Data) 라 하고 줄을 세울 기준을 키(Key)라고 합니다. 예를 들어, 학생 20명인 반에서 번호 순으로 일렬로 서라고 한다면 학생들이 데이터, 번호가 키가 되겠죠. 번호가 작은 학생 부터 줄을 선다면 오름차순(Ascending order), 번호가 큰 학생부터 줄을 선다면 내림차순(Decending order)라고 합니다.

 

정렬 알고리즘의 구분은 구현의 복잡도에 따라 알고리즘이 간단한 선택정렬(Selection sort), 삽입정렬(Insertion sort), 거품정렬(Bubble sort), 쉘정렬(Shell sort) 등이 있고, 복잡한 알고리즘에는 퀵정렬(Quick sort), 기수정렬(Radix sort), 힙정렬(Heap sort), 병합정렬(Merge sort) 등이 있습니다. 간단한 알고리즘은 구현이 쉽지만 일반적으로 느리고 복잡한 알고리즘은 구현이 복잡하지만 일반적으로 속도가 빠릅니다.

또다른 구분은 데이터를 내부 메모리에서 정렬하느냐(내부정렬: Internal sort) 외부기억장치(HDD,SSD등)에서 정렬하느냐(외부정렬: External sort)도 있습니다. 내부정렬은 속도가 빠르지만 모든 데이터를 메모리에 로드(Load)해야하는 부담이 있고 외부정렬은 속도는 느리지만 메모리 용량을 많이 차지하지 않고 대용량 데이터 처리에 장점이 있다고 할 수 있습니다.

 

우리는 컴퓨터를 사용할 때 알게 모르게 정렬을 하고 있습니다. 탐색기에서 파일을 이름순, 크기순, 수정날짜순 등으로 정렬하는 경우도 있고, 인터넷 검색결과를 정확도, 최신순 등으로 정렬하는 경우도 있습니다. 굳이 4차 산업이니 빅데이터 같은 말을 언급하지 않더라도 효과적인 자료 정렬의 중요성은 아주 높아지고 있답니다.

 

일반적으로 가장 빠른 정렬 알고리즘은 퀵정렬(Quick sort)라고 알려져 있습니다. 하지만, 퀵정렬은 거의 정렬이 되어 있는 자료(Data)에 대해서는 다른 기본 정렬 알고리즘(예를 들면 삽입정렬)보다 성능이 떨어집니다. 어느 상황에나 가장 좋은 알고리즘이라는 만능키는 없으며, 주어진 상황에 가장 적합한 알고리즘만이 있을 뿐입니다.