정렬(sorting)이란?

1. 정렬이란?

 

정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 의미한다. 정렬은 컴퓨터 공학에서 가장 기본적이고 중요한 알고리즘 중의 하나로 일상생활에서 많이 사용된다.

 

정렬은 자료 탐색에 있어서 필수적이다. 예를 들어 사전에서 우리가 단어를 쉽게 찾을 수 있는 것은 사전안의 단어들이 알파벳 순으로 정렬되어 있기 때문이다. 만약 사전이 알파벳 순으로 정렬되어 있지 않다면 특정 단어를 찾는 것은 거의 불가능할 것이다. 이는 컴퓨터도 마찬가지이며, 정렬되어 있지 않은 자료가 주어지면 탐색의 효율성이 크게 떨어진다.

 

지금까지 개발된 정렬 알고리즘은 매우 많지만 모든 경우에 있어서 최상의 성능을 보여주는 최적의 알고리즘은 존재하지 않는다.  따라서 이들 방법들 중에서 현재의 프로그램 수행환경에서 가장 효율적인 알고리즘을 선택하여야한다. 정렬 알고리즘을 평가하는 효율성의 기준으로는 정렬을 위해 필요한 비교 연산의 횟수와 이동 연산의 횟수이다.

 

일반적으로 이동 횟수와 비교 횟수가 서로 비례하지 않는다. 즉 어떤 알고리즘은 비교 횟수는 많지만 이동 횟수는 적을 수 있고 또 그 반대도 가능하다. 숫자와 숫자를 비교하는 것은 시간이 걸리지 않지만 문자열과 문자열을 비교하는 것은 상당히 시간이 걸리는 작업이다. 또 숫자를 이동시키는 것은 간단하지만 큰 구조체를 이동시키려면 상당한 시간이 걸릴 것이다. 현재 개발중인 응용에 맞추어서 가장 적절한 정렬 알고리즘을 선택한다.

 

정렬 알고리즘은 대게 크게 2가지로 나누어진다. 단순하지만 비효율적인 방법, 복잡하지만 효율적인 방법이 있다.

단순한 정렬 알고리즘은 구현하기가 쉬운 대신에 비효율적이다. 반면 효율적인 알고리즘은 구현하기가 까다롭지만 효율적이다.

 

• 단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬 
• 복잡하지만 효율적인 방법 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬 등

대개 자료의 개수가 적다면 단순한 정렬 방법도 괜찮지만, 자료의 개수가 일정 개수를 넘어가면 반드시 효율적인 알고리즘을 사용하여야한다.

 

정렬 알고리즘을 내부 정렬(internal sorting)과 외부 정렬(external sorting)로 구분할 수도 있다.

 

• 내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬이다.
• 외부 정렬은 외부 기억 장치에 대부분의 데이터가 있고, 일부만 메모리에 올려놓은 상태에서 정렬하는 방법이다.

 

정렬 알고리즘을 안전성(stability)의 측면에서 분류할 수도 있다. 정렬 알고리즘에서 안전성이란 입력 데이터에 동일한 키값을 갖는 레코드가 여러개 존재할 경우, 이들 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않음을 뜻한다. 이와 반대로 같은 키 값을 갖는 레코드들이 정렬 후에 위치가 바뀌게 되면 안정하지 않다고 한다. 정렬의 안정성이 필수적으로 요구되는 경우에는 정렬 알고리즘 중에서 안정성을 충족하는 삽입정렬, 버블정렬, 합병 정렬 등을 사용해야한다.