Sort(정렬) #

데이터를 일정한 기준에 따라 순서대로 배치하는 작업으로, 그 방식에 따라 여러 알고리즘이 존재한다. 전산학의 대표적인 연구주제로 오랫동안 다루어지면서 다양한 알고리즘들이 개발되어 왔다. 최근에는 인공지능이나 분산처리 기법들이 전산학의 주요 연구 주제이지만, sort는 그 모든 연구의 근간을 이루는 전산이론으로서 앞으로도 계속 연구되고 발전될 것이다.

Sort의 주요 이슈 #

sort알고리즘이 추구하는 것은 다른 많은 전산 이론과 마찬가지로 시스템에 가능한 부담을 적게 주면서 최대한의 성능을 내는 것이다. 이 때 작용하는 요소들은 복잡도, 메모리 사용량, 안정성 등이다. 복잡도는 sort하고자하는 대상들을 비교할 때와 이 비교에 따라서 교환할 때 상승하게 된다.

대표적인 sort알고리즘 #

Bubble sort #

가장 단순한 방식의 sort로 인접한 두 원소들을 비교하며 거품이 올라가듯이 순차적으로 하나씩 재배치하는 알고리즘이다. 최하단부터 원소 한개씩을 인접 원소와 비교하기 때문에 시간복잡도가 n^2 으로 대표적인 sort알고리즘 중에서 가장 느리지만 단순하면서도 가장 안전한 방식이다.

Insert sort #

간단하게 보면 sort 영역을 확장해가는 방식이라고 할 수 있다. sort되지 않은 영역에 있는 원소를 이전에 sort된 영역과 비교하며 위치를 찾아가는 방식이다.

Selection sort #

전체에서 최소값을 찾아 이를 맨 앞에 위치시킨 다음 나머지 그룹으로만 앞 과정을 반복하는 방식으로 시간복잡도가 꽤 높은 편(n^2)이다.

Quick sort #

Divide and Conquer 방식을 쓰는 알고리즘으로, 중심값을 정하고 이 값을 기준으로 원소들을 두 그룹으로 나눈 다음 각 그룹에서의 sort를 수행하는 방식인데, 이 그룹을 원소 두개의 최소단위까지 나누어 재귀적으로 수행한다는 것이 특징이다. 컴퓨터 시스템을 효율적으로 이용할 수 있는 방식이기 때문에 속도가 빠르지만 데이터의 기존 정렬상태에 따라서 복잡도가 유동적으로 바뀌게 되며 다른 알고리즘에 비해 메모리를 많이 사용하게 된다(최악의 경우 복잡도  n^2  평균복잡도 nlogn).