단순 선택 정렬(Straight Selection Sort)

단순 선택 정렬(Straight Selection Sort)

가장 작은 요소를 골라서 배열의 왼쪽부터 차례대로(오름차순 기준) 알맞은 위치로 옮겨서 정렬하는 방법

 

 

알고리즘 : 

첫 번째 요소부터 차례대로 비교 기준(arr[n])이 된다.비교 기준의 다음번째 위치부터 마지막까지, 각각의 요소와 비교 기준이 되는 요소를 비교한다.더 작은 요소가 위치한 인덱스를 min 변수에 저장하면서 계속 min 변수를 갱신해나간다.마지막 위치의 요소까지 비교를 마치고 나면, 최종적으로 min 인덱스에 위치해 있는 요소(arr[min])와 비교 기준이 되는 요소(arr[n])를 서로 교환한다.

 

 

시간 복잡도 : O(N²)

버블 정렬, 삽입 정렬과 마찬가지로 시간복잡도가 크기 때문에 효율적인 정렬 알고리즘은 아니다.

 

 

 

[예제]

배열 arr의 요소가 차례대로 5 2 3 8 1 4 6 일 때, 이 배열을 오름차순으로 정렬하기

 

 

배열의 0번째 위치한 5가 비교 대상이 된다.

1번째 위치의 요소부터 마지막 위치의 요소까지 차례대로 5와 비교한다.

0번째 요소와 1번째 요소를 비교했을 때, 1번째 요소가 더 작으므로 min이 0에서 1로 갱신된다.

1번째 요소와 4번째 요소를 비교했을 때, 4번째 요소가 더 작으므로 min이 1에서 4로 갱신된다.

최종적으로 min에는 4가 들어있으므로 arr[0]과 arr[4]를 교환한다.

 

위의 과정을 통해 배열의 가장 왼쪽에 가장 작은 값이 옮겨졌다. 

즉, 배열의 가장 첫번째 요소는 정렬된 상태가 되었다.

이제 1번째 요소가 비교 대상이 된다.

2번째 요소부터 마지막 요소까지 차례대로 2와 비교한다.

2번째 요소부터 마지막 요소까지 비교하는 동안 비교 대상인 2보다 작은 수가 없었으므로 

반복문이 종료될 때까지 min은 갱신되지 않는다.

최종적으로 min = 1 이므로 arr[1] 와 arr[1]을 교환한다.

 

 

 

배열의 1번째 요소까지 정렬이 완료된 상태이다.

이제 2번째 요소인 3이 비교 대상이 된다.

3번째 요소부터 마지막 요소까지 차례대로 3과 비교하여 min을 갱신시킨다.

이번에도 역시, 3번째 요소부터 마지막 요소까지중에 3보다 작은 값이 없으므로 min이 갱신되지 않는다.

최종적으로 min = 2 이므로 arr[2] 와 arr[2]를 교환한다.

 

 

 

배열의 2번째 요소까지 정렬이 완료된 상태다.

3번째 요소인 8이 비교 대상이 된다.

4번째 요소부터 마지막 요소까지 차례대로 8과 비교해가며 min을 갱신시킨다.

최종적으로 min = 5가 되어 arr[3]과 arr[5]를 교환한다.

 

 

 

배열의 4번째 요소인 5가 비교 대상이 된다.

8과 6 모두 5보다 크므로 중간에 min이 갱신되지 않는다.

최종적으로 min = 4 이므로, arr[4]와 arr[4]를 교환한다.

 

 

마지막으로 8이 비교 대상이 되어, 6과 비교한다.

6이 8보다 작으므로 min이 5에서 6으로 갱신된다.

최종적으로 min = 6 이므로 arr[5]와 arr[6]을 교환한다.

 

 

 

소스 코드 : 

	public static void selectSort(int[] arr, int n) {

		for (int i = 0; i < n - 1; i++) {
			int min = i;
			for (int j = i + 1; j < n; j++) {
				if (arr[j] < arr[min])
					min = j; // min 갱신
			}
			swap(arr, i, min);
		}
	}