💡 최소 값을 골라서 이미 정렬된 마지막 요소와 교환하는 정렬

---

만약 여러분들에게 바닥에 뿔뿔이 흩어진 1~100의 숫자가 적힌 카드를 오름차순으로 정렬하라는 과제가 주어진다면, 어떤 순서로 정렬하시겠습니까?

오름차순으로 정렬하는 경우를 생각해 보겠습니다.

배열 DATA는 정렬된 부분(앞부분)과 ‘정렬되 않는 부분(뒷부분)’으로 나뉩니다.

처음에는 ‘정렬된 부분’이 비어있고 ‘정렬되지 않은 부분’이 배열 전체를 차지 합니다.

1단계 : ‘정렬되지 않은 부분’ 안에서 최소 값을 찾는다.

2단계 : ‘최소값’ 을 선택해서 ‘정렬되지 않은 부분의 1번째 요소’와 교환한다.

3단계 : ‘정렬되지 않은 부분’의 시작 위치를 1칸 뒤로 옮긴다.

4단계 : 정렬되지 않은 부분의 요소 수가 1이 될 때까지 1~3단계를 반복한다.

선택정렬 구현

import java.util.Arrays;
import java.util.Scanner;

public class selectionSort {
	static void swap(int[] arr, int index1, int index2) {
		int tmp = arr[index1];
		arr[index1] = arr[index2];
		arr[index2] = tmp;
	}

	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;
				swap(arr, i, min);
			}
			System.out.println(Arrays.toString(arr));
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		System.out.println("선택 정렬");
		System.out.print("요소 개수 : ");
		int n = sc.nextInt();
		int[] x = new int[n];

		for (int i = 0; i < n; i++) {
			System.out.print("X[" + i + "] = ");
			x[i] = sc.nextInt();
		}
		System.out.println("정렬 과정");
		selectSort(x, n);

		System.out.println("오름차순으로 정렬했습니다.");
		for (int i = 0; i < n; i++) {
			System.out.print("X[" + i + "] = " + x[i] + "\n");
		}
	}
}