정렬 알고리즘 : 선택정렬

선택정렬이란 말 그대로 선택적으로 정렬을 한다는 의미입니다. 정렬 순서에 맞게 하나씩 선택해서 옮기는 것이죠. 이해하기 쉽게 그림으로 설명 드리겠습니다.

1. 선택정렬 : 이해와 구현

이렇게 정렬 되지 않은 배열과 Min이라는 버퍼가 있다고 가정해 봅시다.

1단계

1-1단계 : 인덱스 0의 값을 Min 버퍼에다가 넣어둡니다. 즉 3을 최소 값 이라고 세팅을 해놓고 시작하겠습니다.

1-2단계 : 인덱스 1과 비교합니다. 3이 더 작으므로 변화가 없습니다.

1-3 단계 : 인덱스 2와 비교합니다. 2가 더 작으므로 버퍼를 2로 바꿔서 채웁니다.

1-4 단계 : 마지막 인덱스 3과 비교합니다. 1이 더 작으므로 버퍼를 1로 바꿔서 채웁니다.

그럼 최종 버퍼에는 1이 들어가 있으므로 처음 기준으로 삼았던 인덱스 0의 값과 바꿔 줍니다. 그럼 최종적으로 1 4 2 3 의 값이 들어가게 됩니다. 위 과정을 그림으로 표현하면 다음과 같습니다.

2단계

2-1 단계 : 인덱스 0은 정렬된 상태이니 인덱스 1의 값을 기준으로 삼고 버퍼에다가 넣어줍니다. 즉 4를 넣어 줍니다.

2-2 단계 : 인덱스 2와 비교합니다. 2가 더 작으므로 버퍼를 2로 바꿔 채움니다.

2-3 단계: 인덱스 3과 비교합니다. 3이 더 크므로 변화 없습니다.

 

그럼 최종 버퍼에는 2가 들어가 있으므로 처음 기준으로 삼았던 인덱스1과 값을 바꿔 줍니다. 그럼 최종 적으로 1 2 4 3 의 값이 들어가게 됩니다. 이 과정도 그림으로 표현하겠습니다.

3단계

3-1 단계 : 인덱스2의 값을 기준으로 삼고 버퍼에 넣어 줍니다. 즉 4를 버퍼에 넣습니다

3-2 단계: 인덱스 3과 비교합니다. 3의 값이 더 작으므로 버퍼에 3을 넣어 줍니다.

 

그럼 최종 버퍼에는 3이 들어가 있으므로 아까와 마찬가지로 기준으로 삼았던 인덱스2와 스왑을 해줍니다. 최종적으로 1 2 3 4 의 값이 들어가게 됩니다. 그림으로 표현하면 다음과 같습니다.

이러한 과정을 코드를 통해 구체적으로 설명 드리겠습니다.

선택정렬 함수의 이름은 SelSort입니다. 매개변수로는 배열, 그리고 배열 사이즈를 받습니다.

첫 번 째 for( i=0 ; i<size-1 ; i++ ) 은 배열의 크기가 4이므로 인덱스 0부터 3까지 반복해야 합니다. 이 3번의 반복이 아까 설명한 3단계를 뜻합니다. 그리고 내부의 for (int j = i + 1; j < size j++)은 각 단계 별로 존재하는 세부 단계들 1-2, 1-3, 1-4, 2-2, 2-3, 3-2 단계 들을 뜻합니다. 참고로 1-1, 2-1, 3-1 단계는 두 개의 for문 사이에서 수행되는 단계입니다.

 

쉽게 설명하자면 인덱스 0, 1, 2를 한번 씩 기준으로 삼고 수행을 해야 하고 기준으로 삼은 인덱스를 기준으로 세부 단계로 나눠지게 됩니다. 

인덱스 0부터 기준점이 시작되므로 수행이 한번 진행되면 그다음 인덱스를 기준으로 잡고 진행을 해야 하기 때문에 시작점인 j가 i+1 로 시작하게 되는 것입니다. i가 바로 시작 기준점이고 j가 비교를 시작하는 인덱스입니다.

코드를 보면 33번 째 줄 min=i 에서 기준점 인덱스를 min 변수에 저장합니다. 두 번째 for문 안의 조건문을 보면 

기준점 인덱스와 비교대상 인덱스들을 비교하는 과정입니다. 기준점 인덱스의 값이 더 크면 현재 비교대상의 인덱스를 min 에 저장합니다.

두 번째 for문의 비교가 끝나면 현재 비교 연산에서 가장 작은 값을 가지고 있는 인덱스 min의 값을 처음에 기준점으로 정한 인덱스 i 의 값과 변경 시켜줍니다. 이러한 과정이 바로 이 부분의 코드에 해당됩니다. 

 tmp = ary[i]                               //        기준점(인덱스 i)의 값을 임시버퍼에 저장하고

 ary[i] = ary[min]                         //         가장 작은 값을 가지고 있는 min 인덱스를 기준점 인덱스에 넣어주고

 ary[min] = tmp                          //         임시버퍼의 값을 가장 작은 값을 가지고 있었던 인덱스 위치에 다시 넣어줍니다.

2. 선택정렬 : 성능 평가

 선택 정렬의 코드만 봐도 버블 정렬과 성능 상 큰 차이가 없습니다. 그럼 비교 횟수의 확인을 위해 선택 정렬의 일부인 반복문을 봅시다.

위 코드를 보면 바깥쪽 for문의 I가 0일 때 안쪽 for문의 j는 1부터 size-1 까지 증가하여 선택정렬의 비교연산은 size-1회 진행됩니다. 그리고 바깥쪽 for문의 I가 1일 때는 안쪽 for문의 j가 2부터 size-1까지 증가하여 선택 정렬의 비교연산은 size-2회 실행됩니다. 즉 비교연산의 횟수는 다음과 같이 정리가 가능합니다.

 

(size-1) + (size-2) + .... 2 + 1 따라서 등차수열 공식으로 (n^2-n)/2 가 되고 따라서 선택 정렬의 빅-오는 O(n^2)이 된다. 이는 버블 정렬과 똑같습니다.

 

그럼 이는 버블 정렬과 성능과 차이가 없을 까요? 비교횟수를 기준으로 보면 차이가 없지만 데이터 이동 횟수를 비교하면 차이가 있습니다.

 

버블 정렬에서 데이터 변환부 는 안쪽 for문 안에 존재하고 선택정렬에서 데이터 변환부는 안쪽 for문 바깥에 속해 있습니다. 안쪽 for문안에 위치하게 되면 비교연산의 횟수에 영향을 미치게 되지만 바깥쪽 for문에 포함되어 있으므로 최선의 경우와 최악의 경우에 상관없이 항상 size-1 * 3 의 대입 연산이 일어납니다.

 

최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대 할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지는 않는다는 사실을 감안하면 이 둘의 우열을 가리는 것은 무의미하다고 볼 수 있습니다.