선택 정렬과 효율성

Sundae·2023년 8월 6일

Data Structures and Algorithms Sort

자료구조와 알고리즘

목록 보기

12/19

선택 정렬

선택 정렬은 단순 정렬 분류에 속한다. 이해하기 쉬워서 이렇게 불리지만, 더 빠르다고 알려진 정렬 알고리즘보다 비효율적이다.

선택 정렬은 다음과 같은 단계를 따른다.

배열의 처음 상태는 이렇다.

먼저 인덱스 0에 있는 값을 확인하고 시작한다. 우리는 현재 최솟값이 6으로 기억했다. 최솟값으로 기억한 인덱스는 주황색으로 칠해놓겠다.

1단계 : 6 (현재 최솟값) 과 2를 비교한다.
6은 2보다 작다. 현재 최솟값을 2로 기억하자.

2단계 : 2 (현재 최솟값)과 다음 값 9를 비교한다. 2가 더 작으므로 아직까지 최솟값은 2다.

3단계 : 2(현재 최솟값)과 1을 비교한다. 1이 더 작다. 최솟값을 1로 기억하자.

4단계 : 1(현재 최솟값)과 5를 비교한다. 첫 번째 정렬의 최솟값이 1인 것을 알았다.
5단계: 첫 번째 정렬의 최솟값은 1이다. 맨 왼쪽( 인덱스 0 )과 교환해주자.

인덱스 0은 최솟값이 들어가 있으니 올바른 위치에 있다고 볼 수 있다. 계속 이렇게 진행된다면 다음 정렬에는 두 번째 최솟값이 인덱스 1로 위치할 것으로 예상할 수 있다.

두 번째 정렬을 진행해보자.

인덱스 1부터 시작한다. 인덱스 1의 값은 2이며, 이 값은 두 번째 정렬의 시작 최솟값이다.

6단계 : 2(현재 최솟값)과 9를 비교한다. 2가 더 작으니 여전히 2가 최솟값이다.

7단계 : 2와 6을 비교한다. 2는 6보다 작으니 2는 여전히 최솟값이다.

8단계: 2(현재 최솟값)과 5를 비교한다. 2가 더 작으므로 여전히 최솟값이다.

2는 두번 째 정렬에서 최솟값으로 판별됐다. 이미 올바른 위치에 있으니 교환할 필요는 없다.

세 번째 정렬을 시작하자.

위와 같이 인덱스 한칸이 증가한 인덱스 2에서 시작한다. 값 9는 시작 최솟값이다.

9단계 : 9(현재 최솟값)과 6을 비교한다.

6이 더 작으므로 새로운 최솟값은 6이다.

10단계 : 6(현재 최솟값)과 5를 비교한다.

5가 더 작으므로 새로운 최솟값은 5이다.

11단계 : 배열 끝까지 순회를 끝냈다. 세 번째 최솟값은 5이므로 처음 시작했던 값 9와 교환한다.

여기서 우리 모두는 배열 전체 원소가 잘 정렬됐음을 알지만, 컴퓨터는 모른다.

네 번째 정렬로 넘어가자.

세 번쨰 정렬에서 인덱스 2로 시작했다. 한 칸 넘어간 인덱스 3에서 시작하자. 6이 시작 최솟값이다.

12단계 : 6과 9를 비교한다. 6이 더 작으므로 최솟값은 여전히 6이다.

네 번째 정렬이 끝났다. 최솟값은 6으로 판별됐고, 새로운 최솟값은 없었으니 교환하지 않아도 된다.

전체 배열이 잘 정렬됐다.

선택 정렬 구현

아래는 자바로 구현해본 선택 정렬이다.

	// 선택정렬 메소드
   public static int[] selectionSort( int[] array ) {
	   
	 
	   for( int i = 0; i < array.length-1; i++) {
		   // 최솟값이 들어있는 인덱스
		   int lowestIndex = i;
		   
		   for(int j = i + 1; j < array.length; j++) {
			   // 만약 최소값이 들어있는 인덱스보다 작으면 lowestIndex = j 
			   if( array[lowestIndex] > array[j] ) {
				   lowestIndex = j;
			   }			   
		   }
		   // 최솟값이 이미 올바른 위치에 있다면 실행하지 않음
		   if( lowestIndex != i ) {
			   int tmp = array[i];
			   array[i] = array[lowestIndex];
			   array[lowestIndex] = tmp; 
		   }		   		   
	   }	   
	   return array;
	   
   }

선택 정렬의 효율성

선택 정렬의 효율성을 버블 정렬과 비교해서 설명해보자. ( 버블 정렬에 대한 내용은 버블 정렬과 효율성 게시물에서 볼 수 있다.)
선택 정렬은 버블 정렬과 같이 두 가지 단계로 진행된다. 비교와 교환이다.

비교는 위의 예시에서 볼 수 있듯이, 총 10번 했다.
첫 번째 정렬에서 4번 , 두 번째 정렬에서 3번 , 세 번째 정렬에서 2번 , 네 번째 정렬에서 1번이다.

4 + 3 + 2 + 1 = 10이다.

이를 원소 N개로 나타내면 ( N - 1 ) + ( N - 2 ) + ( N - 3 ) .... + 1 이다.

교환은 시도한 정렬마다 한 번 일어나거나 일어나지 않는다. 새로운 최솟값이 나타나면 교환하고, 그렇지 않다면 교환하지 않기 때문이다.

밑의 표는 버블 정렬과 선택 정렬을 비교한 것이다. (비교하기 위해 버블 정렬 최대 단계 결과를 2로 나누었다.)

데이터 원소	버블 정렬의 최대 단계 수	선택 정렬에서 최대 단계 수
5	5² / 2 = 12.5	14(10번의 비교 + 4번의 교환)
10	10² / 2 = 50	54(45번의 비교 + 9번의 교환)
20	20² / 2 = 200	199(180번의 비교 + 19번의 교환)
40	40² / 2 = 800	819(780번의 비교 + 39번의 교환)
80	80² / 2 = 3239	3239(3160번의 비교 + 79번의 교환)