선택 정렬 코드 질문

질문 내용

선택정렬 구현코드에서, exch(a, i, min)을 i, min이 교환된다는 의미로 받아들였는데 위에 min = i가 있음에도 불구하고 왜 exch을 사용하는지 궁금합니다.

제시된 선택 정렬 코드

public class Selection extends AbstractSort {
	public static void sort(Comparable[] a) {
		int N = a.length;
		for (int i = 0; i < N - 1; i++) {
			int min = i;
			for (int j = i + 1; j < N; j++) {
				if (less(a[j], a[min]))
					min = j;
			}
			exch(a, i, min);
		}
		assert isSorted(a);
	}

	public static void main(String[] args) {
		Integer[] a = {10, 4, 5, 2, 1, 8, 3, 6};
		Selection.sort(a);
		Selection.show(a);

	}

}

함수 설명

• exch(a, x, y): a 배열에 있는 x번째 원소와 y번째 원소를 교환하는 함수
• show(a): a 배열을 출력하는 함수

코드 설명

보내주신 코드는 두 가지 경우를 생각할 수 있습니다.

1. a[j] < ai를 만족하는 경우가 없을 경우 이 경우 아무런 교환이 일어나지 않아도 됩니다. for문을 수행하더라도 less(a[j], a[min])을 만족하는 경우가 없기 때문에 min의 값과 i의 값은 동일합니다. exch(.., .., ..) 함수를 수행하더라도 min의 값과 i의 값이 동일하기 때문에 수행되지 않은 것과 같은 결과가 나타납니다.

2. a[j] < ai를 만족하는 경우가 하나 이상 존재할 경우 이 경우 i보다 큰 인덱스 중 가장 작은 값을 가지는 인덱스와 i가 교환되어야 합니다. for문을 수행하여 less(a[j], a[min])을 반복해서 검사하면 i보다 큰 인덱스 중 가장 작은 값을 가지는 인덱스가 min값이 됩니다. exch(.., .., ..) 함수를 수행하면 i번째 인덱스에 i 이상의 인덱스에 있는 값이 들어가게 되고, min 인덱스에는 원래 i의 값이 들어가게 됩니다.

위를 반복해서 수행하면 i에는 i 이상의 인덱스에 든 값보다 무조건 작은 수가 있게 되어 정렬이 종료됩니다.