단순 선택정렬(Selection Sort) 란?

1. 주어진 배열 중에 최솟값을 찾는다.

2. 그 값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

4. 하나의 원소만 남을 때까지 위의 1~3과정을 반복한다.

아직 정렬하지 않은 부분에서 '값이 가장 작은 요소'를 선택하고 아직 정렬하지 않은 부분의 '첫번째 요소'와 교환한다.

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값인 arr[min]을 선택한다.
2. arr[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

package Mission4;

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

/**
 * 1. 주어진 배열 중에 최솟값을 찾는다.
 * 2. 그 값을 맨 앞에 위치한 값과 교체한다.
 * 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
 * 3. 아직 정렬하지 않은 부분에서 '값이 가장 작은 요소'를 선택하고 아직 정렬하지 않은 부분의 '첫번째 요소'와 교환한다.
 * 4. 하나의 원소만 남을 때까지 위의 1~3과정을 반복한다.
 */
public class SelectionSort {

    static int num; //배열의 길이

    /**
     * 1. 정렬 메서드
     * num이 아닌 arr.length를 사용할 경우에는 데이터의 값이 수만개 혹은 수십만개로 늘어나면 arr.length로 배열의 크기를
     * 읽는 시간이 엄청 오래걸리는 문제점이 발생한다.
     * int[] arr = new int[num]; 을 이용해서 이미 계산된 배열의 크기를 가져다 쓰기 때문에 문제가 발생하지 않는다.
     */
    static void sort(int[] arr, int num) {

        //이 과정을 배열의 길이 num - 1만큼 반복한다.
        for (int i = 0; i < num - 1; i++) {
            int minIndex = i; //아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록한다

            //k는 i=0일때 배열의 두번째 위치에 해당하는 [1]과 비교를 해야하기 때문에 k = i+1이다.
            for (int k = i + 1; k < num; k++) {
                if (arr[k] < arr[minIndex]) { //k의 값이 minIndex보다 작을경우

                    minIndex = k; //arr[minIndex]의 값과 arr[k]의 값을 교환한다
                }
            }
            //스왑 메서드 실행 : 아직 정렬되지 않은 부분의 '첫 요소'와 '가장 작은 요소'를 교환한다.
            swap(arr, i, minIndex);
        }
    }
    /**
     * 2. 스왑 메서드 : 배열 레퍼런스를 이용한 swap방법 - 연산 우선순위를 이용한 방법도 존재한다.
     */
    public static void swap(int[] arr, int i, int k) {

        //아직 정렬되지 않은 부분의 '첫 요소'와 '가장 작은 요소'를 교환한다.
        int tmp = arr[i];
        arr[i] = arr[k];
        arr[k] = tmp;
    }

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        //배열의 길이를 입력받고 선언한다
        System.out.print("배열의 길이를 입력하세요 : ");
        int num = scanner.nextInt();
        int[] arr = new int[num];

        //숫자입력, 배열의 길이만큼 배열에 값 넣기를 반복
        for (int i = 0; i < arr.length; i++) {
            System.out.println("배열의 넣을 정수를 입력하세요 : ");
            arr[i] = scanner.nextInt();
        }
        System.out.println("입력된 배열 : " + Arrays.toString(arr));
        //정렬 메서드 실행
        sort(arr, num);
        System.out.println("선택 정렬 결과 : " + Arrays.toString(arr));
    }
}