자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_선택정렬)

1. 선택정렬

 

예시 입력 1 

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

 

 

선택정렬

 

선택 정렬(Selection Sort)은 간단하고 기본적인 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 배열에서 가장 작은 (또는 가장 큰) 요소를 선택하여 해당 위치로 이동시키는 방식으로 동작합니다. 선택 정렬은 비교적 간단하지만 효율성이 떨어지므로 큰 데이터셋에 대해서는 비효율적일 수 있습니다. 


1. 배열에서 최소값(또는 최대값)을 찾습니다.
2. 최소값을 현재 위치와 교환합니다.
3. 다음 위치로 이동하고 위의 두 단계를 반복합니다.

// 배열을 순회하면서 최소값을 찾아 현재 위치와 교환하는 과정을 반복하여 배열을 정렬합니다.

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;

            // 현재 위치부터 배열 끝까지 최소값을 찾음
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 현재 위치와 최소값 위치를 교환
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        System.out.println("원래 배열: " + Arrays.toString(arr));

        selectionSort(arr);

        System.out.println("정렬된 배열: " + Arrays.toString(arr));
    }
}

 

강의 풀이(Time: 161ms Memory: 27MB)

 

i 가 제일 앞일때, j는 1부터 끝까지 쭈욱 순회합니다. 오름차순이니까 맨 앞에 제일 작은 숫자를 둬야 합니다.

0번 위치에 올 수있는 제일 작은 숫자 최솟값를 찾아내야 합니다. 그러기 위해 idx번호가 있어야 합니다.

처음에는 id에 i값을 놓습니다. 그리고 나서 jfor문이 도는데 i+1부터 돌면서 idx의 값을 찾으면 됩니다.

idx에는 i번째부터 끝까지 가장 작은 숫자인 위치의 인덱스를 저장해야 합니다.

 

i가 고정된 상태에서 j가 계속 돌고 있는건데, arr[j]가 arr[idx]보다 작으면 idx에 j를 재할당해줍니다.

j for문을 돌아도 arr[idx]보다 더 작은 것을 못 찾으면 arr[idx]값과 arr[i]값을 교환해줘야합니다.

 i번째에 들어올 숫자를 찾고 있는 과정입니다. 그 숫자의 인덱스 번호가 Idx입니다. 

다시 말해서 i 번째로 옮겨야 할 숫자의 인덱스번호가 idx입니다. 그래서 arr[i]와 arr[idx]를 스와프 해줍니다.

그다음에는 이제 i가 증가하고 j는 i+1부터 for문을 돌기 시작합니다.

 

이렇게 계속 i번째 올 숫자를 찾아주면, 오름차순 했을때 처럼 i번째 올 숫자부터 정렬되어있습니다.

 

    // 내장함수로 오름차순하는 방법이외에 선택정렬 하는 방법도 알아야함!
    public int[] solution(int n, int[] arr ){
        Arrays.sort(arr);
        return arr;
    }

import java.util.Scanner;

public class Main {

    public int[] solution(int n, int[] arr ){
        // i가 마지막 자료까지 돌 필요없다.
        // 왜냐하면 i의 값이 23이고 마지막 값이 17이라고 하면 어차피 스와프해줘야하므로 i가 17까지 갈 필요 없음
        // 한번이라도 덜 돌기 하기 위함
        for (int i = 0; i < n-1; i++) {
            int idx = i;
            for (int j = i+1; j < n; j++) {
                // jfor문을 다 돌고 나면 가장 작은 값을 가진 인덱스 번호가 idx에 저장된다
                if (arr[j] < arr[idx]) idx = j;
            }
            // 뒤로 옮겨줄 arr[i]값을 tmp변수에 할당
            int tmp = arr[i];
            // 최솟값 찾은걸 arr[i]에 재할당하면서 스와프
            arr[i] = arr[idx];
            // 16 라인에서 찾은 값을 arr[idx]에 스와프
            arr[idx] = tmp;
        }
        return arr;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        for (int x : T.solution(n, arr)) {
            System.out.print(x + " ");
        }
    }
}