선택 정렬(Selection sort)

이번 포스트는 선택 정렬에 대해 정리 해보려고 한다.

먼저 선택 정렬이란

선택정렬

• 제자리 정렬 알고리즘의 하나이다.

제자리 정렬 : 입력 배열(정렬되지 않은 값) 이외에 다른 추가 메모리를 요구하지 않는 방법

• 패스스루마다 원소를 넣을 위치는 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘.

선택 정렬의 단계

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

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다.

int min = nums[i]

...

2. 패스스루를 처음 시작했을 때의 값(인덱스)과 최솟값을 교환한다. 패스스루의 반복 횟수가 늘어남에 따라 인덱스도 증가한다.

temp = nums[i]
nums[i] = min

3. 교환이 일어나지 않을 때까지 반복한다.

선택 정렬 코드

코드는 다음과 같다.

int length = nums.length - 1;
for ( int i = 0; i < length; i ++ ){
	int min = nums[i];
	int position = i;
	for ( int j = i + 1; j < nums.length; j++ ){
		if ( nums[j] < min )  {
			min = nums[j];
			position = j;
        }
     }
	nums[position] = nums[i];
	nums[i] = min;
}

Arrays.stream(nums).forEach(System.out::println);