정렬 알고리즘(2020, 고3, 10월)

Photo by Андрей Сизов on Unsplash

 

 

알고리즘은 컴퓨터에서 문제 해결 방법을 논리적인 순서로 설명하거나 표현하는 절차이다. 그런데 문제 해결 방법에는 여러 가지가 있을 수 있어 어떤 방법으로 문제를 해결하느냐에 따라 효율성이 달라진다. 알고리즘의 효율성을 분석할 때 흔히 시간 복잡도를 사용하는데, 시간 복잡도는 반복적으로 수행되는 연산의 횟수를 이용하여 나타낸다. 이때 연산에는 산술 연산뿐만 아니라 원소 간의 비교를 나타내는 비교 연산도 포함된다. 알고리즘 분야 중 정렬은 원소들을 오름차순이나 내림차순과 같이 특정한 순서에 따라 배열하는 것으로, 정렬을 통해 특정 원소를 탐색하는 데 소요되는 시간을 줄일 수 있다.

 

㉠ 삽입 정렬은 정렬된 부분에 정렬할 원소의 위치를 찾아 삽입하는 방식이다. 집합 {564, 527, 89, 72, 34, 6, 3, 0}의 원소를 오름차순으로 정렬하는 경우, 먼저 564를 정렬된 부분으로 가정하고 그 다음 원소인 527을 564와 비교하여 527을 564의 앞으로 삽입한다. 그리고 그 다음 원소인 89를 정렬된 부분인 {527, 564} 중 564와 비교하여 564의 앞으로 삽입하고, 다시 527과 비교하여 527의 앞으로 삽입한다. 정렬된 부분과 정렬할 원소를 비교하여, 삽입할 필요가 없다면 순서를 그대로 유지한다. 삽입 정렬은 원소들을 비교하여 삽입하는 과정 이 반복되므로 비교 연산의 횟수를 구하여 시간 복잡도를 나타낼 수 있다. 이 경우 집합 {564, 527, 89, 72, 34, 6, 3, 0}의 원소를 오름차순으로 정렬하면 시간 복잡도는 28번(1+2 +3+4+5+6+7)이 된다.

㉡ 병합 정렬은 정렬하려는 집합을 두 개의 부분 집합으로 반복 분할한 뒤 다시 병합하면서 하나의 정렬된 집합으로 만드는 방식이다. 집합을 이루는 원소의 개수가 적을수록 정렬에 필요한 연산 횟수가 줄어든다. 집합 {564, 527, 89, 72, 34, 6, 3, 0}의 원소를 오름차순으로 정렬할 때 병합 정렬을 사용 하는 경우, ㉮ <그림>의 Ⓐ와 같이 8개의 부분 집합이 될 때 까지 전체 집합을 분할한다.

 

<그림>

 

그 후 {564}와 {527}을 비교하여 {527, 564}로 병합하고, {89}와 {72}를 비교하여 {72, 89}로 병합한다. {527, 564}를 {72, 89}와 병합할 때에는 527과 72를 비교하고, 527과 89를 비교하여 {72, 89, 527, 564}로 병합한다. 병합 정렬은 원소들을 비교하여 정렬하는 과정이 반복되므로 비교 연산의 횟수를 구하여 시간 복잡도를 나타낼 수 있는데, 이 경우 시간 복잡도는 12번((1+1+1+1)+(2+2)+4)이 되고 삽입 정렬에 비해 시간 복잡도가 감소한다.

 

한편 ㉢기수 정렬은 원소들의 각 자릿수의 숫자를 확인하여 각 자릿수에 해당하는 큐에 넣는 방식이다. 큐는 먼저 넣은 자료를 먼저 내보내는 자료 구조이다. 원소들의 각 자릿수의 숫자를 확인하기 위해서는 나머지를 구하는 모듈로(modulo) 연산을 수행한다. 집합 {564, 527, 89, 72, 34, 6, 3, 0}의 원소를 오름차순으로 정렬할 때 기수 정렬을 사용하는 경우, 먼저 모듈로 연산으로 일의 자릿수의 숫자를 확인하여 564를 큐4에, 527을 큐7에, 89를 큐9에, 72를 큐2에, 34를 큐4에, 6을 큐6에, 3을 큐3에, 0을 큐0에 넣는다. 이렇게 1차 정렬된 원소들을 다시 모듈로 연산으로 십의 자릿수의 숫자를 확인하여 차례대로 해당하는 큐에 넣어 2차 정렬한다. 이때 해당하는 자릿수가 없다면 자릿수의 숫자를 0으로 간주하여 정렬한다. 기수 정렬은 원소들 중 자릿수가 가장 큰 원소의 자릿수만큼 원소들의 자릿수의 숫자를 확인하는 과정이 반복되므로 모듈로 연산의 횟수를 구하여 시간 복잡도를 나타낼 수 있다. 이 경우 집합 {564, 527, 89, 72, 34, 6, 3, 0}의 원소를 오름차순으로 정렬하면 시간 복잡도는 24번(8+8+8)이 된다.

정렬 알고리즘은 원소들의 초기 나열 상태에 따라 효율성이 다를 수 있으므로 실제 컴퓨터에서는 이를 고려하여 여러 정렬 알고리즘을 복합적으로 사용한다.

 

 

― (출전) 이석호, ‘C로 쓴 자료 구조론’

@ 2020학년도 10월 고3 전국연합학력평가, 27~30번.