선택 정렬 (Selection Sort)

선택 정렬

- 이름 말 그대로 자리를 선택하고 해당 자리에 들어올 값을 찾아서 넣어주는 정렬

- 버블 정렬과 헷갈릴 수 있으니 조심

- 버블 정렬과 다른 것은 먼저 자리를 선정한다는 점

 

정렬 알고리즘 (오름차순)

출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

1. 배열의 자리를 선정한다. (보통 0번째부터 순서대로)

2. 0번째 자리에 들어갈 값의 인덱스을 찾는다. (오름차순 기준 최솟값)

3. 배열을 쭉 돌면서 찾았으면 이제 자리를 바꾼다. 

4. n 차례 반복했으면 앞의 n 개에는 순서대로 알맞는 값이 쌓이게 된다.

5. 따라서 배열을 쭉 순회하면서 최소값을 찾을때는 n+1 부터 찾으면 된다.

6. 반복.

 

JAVA Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.IntStream;

public class SelectionSort {
    public static void selectionSort(int arr[]) {
        int minIdx, tmp;
        for (int i = 0; i < arr.length-1; i++) {
            minIdx=i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIdx] > arr[j]) {
                    minIdx = j;
                }
            }

            tmp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = tmp;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int _loop = Integer.parseInt(br.readLine());

        int arr[] = new int[_loop];
        for (int i = 0; i < _loop; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }


        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();

        selectionSort(arr);

        IntStream.range(0, arr.length).map(i -> arr[i]).forEach(System.out::print);
        System.out.println();
    }
}