내일은 알고리즘

버블 정렬에 이어서 선택 정렬에 대해 알아보겠습니다.

선택 정렬의 아이디어도 간단합니다.

1. 첫 번째 데이터부터 탐색해 가장 작은 수를 찾아 첫 번째 위치로 옮긴다. (오름, 내림차순에 따라 다릅니다.)

2. 이제 첫 번째 위치는 정렬되었으니, 두 번째 데이터부터 탐색한다.

3. 정렬이 완료될때까지 계속 반복한다!

선택 정렬도 한 번 비교가 이루어질 때마다 데이터가 1개씩 정렬되므로 N-1, N-2, N-3 ... 2, 1 번 비교를 해야 합니다.

전체적인 비교의 횟수는 (N*(N-1))/2가 되고, 시간 복잡도는 O(N^2)와 같이 나타냅니다.

다만, 매 번 데이터의 교체가 필요한 버블정렬과 달리 선택 정렬은 위치를 찾은 뒤 마지막에 한 번만 교체하면 되니 버블 정렬보다는 빠르게 정렬이 이루어집니다.

대신 선택정렬의 경우는 stable하지 않은 불안정 정렬인데, 이 내용은 차후에 다루도록 하겠습니다.

그럼 그림을 통해 선택 정렬의 진행을 알아보도록 하겠습니다.

그림에선 8칸의 배열에 각각 3,2,5,7,6,8,1,4의 값이 들어있습니다.

이제 이 배열을 선택 정렬을 통해 정렬해 보겠습니다.

우선 우리가 찾아야 할 데이터의 위치는 첫 번째, 즉 가장 작은 수를 찾아야 합니다.

반복 시행의 첫 시점에서 우리가 알고 있는 정보는 현 위치뿐이므로 가장 작은 수는 3이고 이 수의 위치는 0번 인덱스입니다.

다음 수로 진행하면서 전체를 탐색해 가장 작은 수를 찾아봅시다.

뒤의 수인 7,6,8도 2보다 크므로 계속 진행되다가 일곱번째 수인 1에서 최솟값이 갱신됩니다.

이제 첫번째 시행이 끝났습니다!

우리가 찾는 수는 첫 번째 위치에 올 수, 가장 작은 수이며 그 수의 위치는 6번째 인덱스입니다.

이제 0번과 6번 인덱스의 수를 바꿉니다.

첫 번째 수의 정렬이 완료되었습니다! 

이제 우리는 두 번째 자리에 위치할 수, 즉 일곱 개의 데이터 중에서 가장 작은 수를 찾으려 합니다.

시행을 마쳤습니다!

두 번째 위치, 인덱스 1에 들어있는 2가 현재 정렬되지 않은 가장 작은 수였습니다.

교환은 일어나지 않고, 우리는 두 개의 수를 정렬시켰습니다.

같은 방법으로 세 번째 시행도 진행시켜 봅시다.

이로서 우리는 1,2,3 세 개의 수를 정렬시켰습니다.

앞으로 5번의 시행도 같은 방식으로 진행하면 되지만 과정을 기록하지 않겠습니다.

머릿속으로 테스트를 해보시고 정렬 후의 모습과 비교해보시기 바랍니다.

이렇게 선택 정렬을 통한 정렬이 완료되었습니다!

아래는 JAVA로 구현한 간단한 선택정렬 코드와 테스트입니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.

import java.util.Arrays;
import java.util.Random;

public class sort_02_selection {
	static int size = 10;
	static int bound = 1000;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		int[] data = new int[size];
		Random random = new Random();
		int count = 0;

		for (int i = 0; i < size; i++) {
			data[i] = random.nextInt(bound);
		}
		// 랜덤 값 넣어주기

		System.out.println(Arrays.toString(data));
		// 랜덤하게 들어간 데이터 확인

		/////////////////////// 선택정렬 구현////////////////////////////
		for (int find = 0; find < size; find++) {
			int minIdx = find;
			for (int now = find; now < size; now++) {
				if(data[now] < data[minIdx]) {
					minIdx = now;
				}
				count++;
			}
			int save = data[find];
			data[find] = data[minIdx];
			data[minIdx] = save;
		}
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
		// 정렬 후 데이터와 비교횟수 확인

		int[][] data2 = { { 1, 1 }, { 3, 1 }, { 5, 1 }, { 7, 1 }, { 9, 1 }, { 1, 2 }, { 2, 2 }, { 4, 2 }, { 1, 3 },
				{ 7, 2 }, { 9, 3 }, { 3, 3 }, { 4, 3 }, { 8, 3 }, { 6, 3 } };
		
		for (int find = 0; find < 15; find++) {
			int minIdx = find;
			for (int now = find; now < 15; now++) {
				if(data2[now][0] < data2[minIdx][0]) {
					minIdx = now;
				}
				count++;
			}
			int[] save = data2[find].clone();
			data2[find] = data2[minIdx].clone();
			data2[minIdx] = save.clone();
		}

		for (int i = 0; i < 15; i++) {
			System.out.printf("정렬된 수 : %d, stable: %d\n", data2[i][0], data2[i][1]);
		}
		// stable 정렬이 아님!
	}
}