알고리즘 2장 - 정렬 문제 : 선택 정렬 -

알고리즘 2장

- 정렬 문제 : 선택 정렬 -

 

정렬문제는 Sorting problem으로 n개의 숫자들의 배열을 입력으로 받게 되면 입력된 숫자의 배열이 특정 조건을 만족하도록 다시 나열한 결과를 출력으로 나타내는 문제이다. 특정 조건으로는 오름차순이나 내림차순과 같은 것이 예시가 될 수 있다. 만약 input으로 <5, 2, 4, 6, 1, 3>과 같이 들어오게 된다면 오름차순으로 재배열을 시켜서 내보내는 문제일 경우 output으로 <1, 2, 3, 4, 5, 6> 값을 가지게 만들어주는 것이다.

정렬문제 중에서 선택정렬 알고리즘이 있다. 이를 알고리즘 설명과 정확성 증명, 성능 분석을 통해 알고리즘에 알아보도록 하자. 선택정렬은 말 그대로 선택하여 정렬하는 알고리즘이다. 여기서 중요한 핵심은 무엇을 선택해서 정렬을 할 것인가에 대한 의문이 생긴다. 최솟값을 선택하여 선택 정렬을 할 경우 가장 작은 값을 선택하게 되니 오름차순으로 정렬을 진행하게 되고 최댓값 선택 정렬의 경우 내림차순으로 정렬하게 된다.

최솟값 선택 정렬의 순서를 보도록 하자. 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택하고 선택한 숫자를 정렬되지 않은 숫자들 중 첫 번째 숫자와 자리를 바꾸면 선택된 숫자는 정렬이 된 것이다. 모든 숫자를 옮길 때까지 앞의 과정을 반복하면 정렬이 완료가 된다. 맨 처음에 나온 예시를 다시 사용하게 되면 <5, 2, 4, 6, 1, 3>일 경우 첫 번째 자리의 수인 5와 가장 작은 수인 1이 바뀌게 되고 1은 정렬된 상태로 놓이게 된다. 그런 후 남은 값들 중에 또 가장 낮은 숫자인 2를 택하게 되고 두 번째 자리인 2를 바꾸게 되는데 같은 위치에 같은 숫자이므로 정렬이 된 채로 놓아두면 된다. 이를 계속 반복하여 마지막 자리의 숫자까지 진행하면 정렬이 완료가 된 형태인 <1, 2, 3, 4, 5, 6> 으로 나타나게 된다. 

정확성 증명은 수학적 귀납법을 이용하여 증명할 수 있다. I번째 선택한 숫자가 I번째로 작은 숫자인지를 증명하면 된다. 성능 분석을 해보면 수행시간을 살펴보면 된다. 첫 번째 숫자를 시작으로 모든 숫자를 비교해야하므로 수행시간의 경우 n^2의 형태로 나타나게 된다. 첫 번째 숫자는 n-1번 비교를 하고 두 번째 숫자는 n-2번, 이렇게 진행해서 마지막 항에서 바로 앞의 항은 1번 비교를 하는 형태이므로 이런 숫자를 다 더하게 되면 n^2만큼의 수행시간이 소요되는 것을 알 수 있다.