선택 정렬 (Select Sort)

선택 정렬은 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다.
오름차순을 기준으로 정렬한다.

개념

제자리 정렬의 알고리즘 중 하나이다.
정렬 되지 않은 입력된 배열 외에 다른 메모리를 사용하지 않는다.
해당하는 n번째에 넣을 정렬된 원소 자리는 이미 정해져있고,
어떤 값을 넣을지를 선택하는 알고리즘이다.

동작 과정

1. 주어진 배열에서 최솟값을 찾는다.
2. 그 최솟값을 배열의 맨 앞의 수와 자리를 교체해준다.
3. 맨 처음 값을 뺀 나머지 배열로부터 최솟값을 찾는다.
4. 교체한 다음 맨 앞의 배열과 값을 바꿔준다.
5. 이 과정을 정렬이 완료될 때까지 계속 반복한다.

보기 좋은 예시 이미지를 가져와봤다.
이제 그러면 구현을 해보도록 하자.

Select Sort 구현

n 길이를 가진 배열을 생성하고 다음줄에 n개의 숫자를 입력받아 선택정렬 한다.

public class SelectionSort {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //길이가 n
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[n]; //n개의 숫자를 넣을 배열

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        final int[] results = solution(arr);

        for (int result : results) {
            System.out.print(result);
        }
    }

    private static int[] solution(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            //최소값과 해당 반복 index의 맨 앞자리와 치환
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
}

결론

이런 사소한 지식이라도 안적어두면 까먹고 또 기억이 안나는것 같다.
위의 예시도 ide도움 없이 손코딩으로 포스팅을 올려보는데 더 상기되서 까먹지 않을것 같다.
계속 까먹기 때문에 이렇게 기록으로 남겨두는것이 좋을듯 하다. 😎

기본 알고리즘부터 풀어보는데에 있어서

이 소수를 구하는것에 상당히 애를 먹는다.

물론 소수 뿐만이 아니라 다른 유형의 문제들도

결국 머릿속에선 정리가 매우 잘되지만, 이걸 코드로 구현하는게 쉽지가 않다.

아무튼 각설하고, 소수를 판별하는 알고리즘에 대해 알아보도록 하자.

소수

소수는, 1보다는 큰 자연수들 중 1과 자기 자신만을 약수로 가지고 있는 수를 의미한다.

위키피디아의 이미지를 가져와보았다.

순서는 2부터 소수를 구하고자 하는 목표값 까지의 모든 수를 나열한다.

그다음 2는 소수기에 Prime Numbers에 2를 넣어준다.

그 다음 자기 자신을 제외한 2의 배수를 다 지운다.

지우는 이유?

자기 인수의 배수를 다 지우는 이유는 그 수들은 이미 배수라서 약수에 인수가 포함되기 때문이다.

이 구간을 계속 반복해주면 목표 수 사이까지의 소수가 구해지게 된다.

말로는 설명하기 어려운것 같다.

코드로 자세히 봐보도록 하자.

자바 코드로 구현하기

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

        //여기서 N의 값을 9라고 해보자.
        int N = Integer.parseInt(br.readLine());

        boolean[] array = new boolean[N + 1]; // 배열은 0부터 시작하기 때문에 자릿수를 맞춰주는 개념으로 1을 더해주었다.

        //0과 1은 소수가 아니다.
        array[0] = true;
        array[1] = true;

        //2부터 시작해서 배열 총길이의 제곱근 값까지 반복한다.
        for(int i = 2; i <= Math.sqrt(array.length); i++) {
            if (array[i]) {
                continue;
            }

            // 소수가 아닌수를 true
            for(int j = i * i; j < array.length; j += i) {
                array[j] = true;
            }
        }

    }
}

이렇게하여 boolean[] array의 배열값에서 true이면 전부 소수가 아닌수가 된다.

여기서 true로 바꾸어주는 로직이 i * i로 시작하는 이유는

i의 처음 인수가 2이다. 근데 소수에서는 0과 1을 제외하면 2, 3까지는 무조건 소수임이 보장되어 있다.

그래서 i * i로 4부터 시작하여 자기 자신만큼을 더해주는게 배수의 원리이니까 전부 true로 바꿔주는게 된다.

이렇게 하여 소수를 구할 수 있게 된다.