선택 정렬 (Selection sort) 에 대하여 - With Java

제목 : 선택 정렬 (Selection sort) 에 대하여 - With Java

---

가장 기초적인 정렬 중 하나이다.

시간 복잡도는 $ O(N^2) $ 이다.

나는 선택 정렬을 설명하기 위해 이러한 상황을 예시로 들고 싶다.

상황 : 선생님이 걷어온 쪽지 시험을 학생의 고유 번호대로 상승하도록 정렬 해 달라고 부탁하셨다.

그렇다면, 약 40장 정도가 존재한다고 가정한다면 나는 어떻게 정렬해야 할까?

믈론 사람마다 종이를 순서대로 나열하는 데 있어 다른 방식이 있을 수도 있다.

하지만, 1 번부터 찾고 왼쪽에 둔다. 그 다음 2 번을 찾아 1 번의 밑에 둔다.

그리고 또 3 번을 찾고 2번의 밑에 둔다. 그리고 4번도...

이러한 방식으로 1 번부터 40 번 까지 정렬 할 수 있다.

이 방식이 바로 선택 정렬(Selection Sort) 방식이다.

아 물론, 실제 선택 정렬의 상황과 많이 다른 감이 있다. 정직하게 수가 주어지지 않으므로..

라이브러리가 존재하지 않는다는 가정 하에, 이는 구현 할 수 있는 매우 간단한 정렬 방식일 것이다.

그러나, 하나의 요소를 적층하기 위해, 모든 배열을 루프마다 또 탐색해야 한다는 단점이 있다.

컴퓨터로 상황을 변환 해 보자.

우리의 프로그램은 랜덤한 정수 5 개를 정렬해야 한다.

index	0	1	2	3	4
value	5	2	3	4	1

수는 오름차순 으로 정렬 해야 한다.

그렇다면, 이 수를 "정렬" 하기 위해서는 어떤 프로그래밍적 행위가 필요할까?

나는 위의 질문이 정렬 알고리즘 구현을 배우는 것 만큼 매우 중요하다고 생각한다.

이에 대한 답은 내가 예시로 들었던 상황과 행동에서 추출할 수 있다.

현재 몇 번째에 종이를 넣을 것인가? : 어떤 인덱스에 수를 넣을 것인가?

이 글의 의미는, 1 번째로 들어갈 종이를 찾는다면,

우리는 배열의 인덱스 0 에 들어갈 가장 작은 수를 찾고 있는 것이고,

2 번째로 들어갈 종이를 찾는다면,

우리는 배열의 인덱스 1 에 들어갈 가장 작은 수를 찾고 있는 것이다.

이 때, 가장 작은 수는 삽입할 인덱스부터 시작하여 끝 까지 탐색한다.

이미 앞의 인덱스들은, 탐색할 인덱스보다 모두 작기 때문이다. (이미 정렬이 끝난 수 이므로)

가장 작은 번호를 가진 종이를 찾아야 해! : 현재 인덱스에 들어갈 가장 작은 수를 찾자!

사람과 컴퓨터의 인식은 개념 자체가 다르다.

사람은 인식과 사고가 유연하기 때문에, 각 번째에 들어갈 가장 작은 수를 찾기 위해,

이미 어떤 수가 어디쯤에 존재하는지 추상적으로 기억 해 둘 수도 있다.

심지어는, 꽤 앞 쪽의 번호 같다면, 미리 앞쪽으로 종이를 끼워 둘 수도 있는 행동이 가능하다.

그러나,

컴퓨터는 다르다. 음.. 어찌 본다면, 인간의 유연한 사고에 비해, 컴퓨터의 행동 반경은 정말이지, 바보이다.

물론, 인공지능을 빼고 한 말이다.

마트가서 우유사고, 만약에 아보카도 있으면 6개 사와.

프로그래머라면, 언젠가 한 번은 봤을 법한 밈이다.

프로그래머 남편은, 이 말을 아내에게 듣고 마트 갔다와서

"아보카도 있었어" --> 우유 6개를 자랑스럽게 들고 있으며..

웃기기도 하지만, 참으로 컴퓨터적 사고를 결합했다고도 말할 수 있겠다.

이것이 바로 컴퓨터의 사고이다.

컴퓨터가 무엇을 알겠는가? 컴퓨터는 정해진 이진 데이터를 읽거나, 반응하는 수 밖에 없다.

이에 기반해서, 우리가 정렬 즉, Sorting 을 위해서 컴퓨터에게 어떻게 명령해야 하는지 알아야 한다.

우리가 정렬을 수행하기 위해, 필요한 컴퓨터의 사고는 이러하다.

1. 비교 - Compare
2. 삽입 - Insert
3. 추출 - Extract
4. 저장 - Data Store
5. 반복 - Loop

위의 5 가지 행동 요소가 정렬의 주된 요소이다.

이를 통해 들어갈 가장 작은 수를 찾아 보자.

1. i 번째에 들어갈 가장 작은 수를 찾아야 한다.
2. i - 1 번째까지는 이미 정렬되어 있으므로, i 번째부터 시작하여 탐색을 시작한다.
3. N - 1 번 쨰 까지 탐색하며, 지금까지의 가장 작은 수와, 현재 탐색 인덱스의 수를 비교한다.
4. 현재 인덱스의 값이 지금까지의 가장 작은 수 보다 작다면, 현재 인덱스가 가장 작은 수를 가진 인덱스로 저장된다.
5. N - 1 번까지 탐색하여, 가장 작은 수가 존재하는 인덱스를 저장한다.
6. i 번째 인덱스와, 가장 작은 인덱스의 값을 교환한다.
7. i 가 N - 1 일 때 까지 위의 행동을 반복한다.

구현 With Java

위의 과정을 적용하여 실제 코드로 만들어 보자.

예제 입력, 예제 출력 은,

예제 입력	예제 출력
5 5 2 3 4 1	1 2 3 4 5

이라고 가정한다.

맨 위의 입력은 N 이고, 하나의 줄에 입력이 들어온다.

N 개의 줄에 걸쳐 입력이 들어오고, N 개의 줄로 결과를 출력해야 한다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 개를 정렬해야 한다.
        int N = Integer.parseInt(br.readLine());

        // 정렬 할 공간, 즉, 배열을 마련한다.
        int[] arr = new int[N];

        // N 번에 걸쳐 arr 배열에 값을 넣어준다.
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        // 선택 정렬 수행!
        selectionSort(arr);

        // 콘솔에 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(arr[i]).append("\n");
        }
        System.out.println(sb.toString());

    }

    // 선택 정렬 함수 
    public static void selectionSort(int[] arr) {
        // i 번째 부터 배열의 끝 까지 실행한다.
        for(int i = 0; i < arr.length; i++) {
            // i 번째에 들어가야 할 가장 작은 수, 이를 포함한 인덱스를 초기화 해준다.
            int minVal = Integer.MAX_VALUE;
            int minIdx = -1;

            // i - 1 인덱스까지는 전부 정렬이 된 상태이므로, i 인덱스부터 탐색을 시작한다.
            for(int j = i; j < arr.length; j++) {
                // 만약, 현재 가장 작은 값 보다, 현재 인덱스의 값이 더 작다면,
                if(arr[j] < minVal){
                    // 가장 작은 값을 변경하고, 지정 인덱스를 현재 인덱스로 변경한다.
                    minVal = arr[j];
                    minIdx = j;
                }
            }

            // 하나의 루프를 돌면서 가장 작은 값을 지닌 인덱스를 찾았으므로, 이를 i 번째에 넣어 준다.
            swap(arr, i, minIdx);
        }
    }

    // 배열 간의 요소 교환 관심사 분리
    public static void swap(int[] arr, int x, int y) {
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }
}

알고리즘 코드를 작성 할 때, Loop 문법으로 인해 난잡해 질 코드를 편리하게 만들기 위해,

특정 관심사를 분리하여 Method 로 만들어 놓는 것이 매우 좋은 습관이라고 생각한다. - 의견

---

참고 사이트

https://www.w3schools.com/dsa/dsa_algo_selectionsort.php