[알고리즘] 선택 정렬(Selection Sort)이란 ?

📁선택정렬

대상 데이터에서 최솟(최댓)값을 찾아 선택하여 선택된 최솟(최댓)값을 차례대로 바꿔가면서
정렬하는 방법으로 구현이 복잡하고 시간 복잡도도 O(n²)으로 효율적이지 않아
코딩 테스트에서는 많이 사용되지는 않는다.

1️⃣ 선택 정렬의 과정

1. 데이터에서 최솟(최댓)값을 찾는다.
2. 남은 데이터에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
3. 정렬되지 않은 가장 앞에 있는 데이터의 위치를 변경한다.
4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

public class Main {
	public static void main(String[] args) {
		int[] arr = new int[] {5, 4, 1, 3, 2};

       arr = selectSort(arr);
       System.out.println(Arrays.toString(arr));
	}

	static int[] selectSort(int[] arr) {
		for(int i = 0; i < arr.length; i++) {
			// 최소 인덱스 i
			int minIdx = i;

			for(int j = i+1; j < arr.length; j++) {
				// 정렬되지 않은 배열 내에 최소 인덱스의 값보다 작은 값이 존재하면 최소 인덱스 변경
				if(arr[j] < arr[minIdx]) {
					minIdx = j;
				}
			}
			int tmp = arr[i];
			arr[i] = arr[minIdx];
			arr[minIdx] = tmp;
		}
	}
}

2️⃣ 선택 정렬 정리

1. 선택 정렬은 메모리 소모가 적으며, 뒤의 index로 갈 수록 최솟값을 찾는 범위가 점점 줄어든다.

2. 안정성을 만족하지 않는다.

   • 값이 같은 데이터가 존재하면 그 데이터의 위치에 따라 결과 값이 변경된다는 특징

3. 제자리 정렬(in-place sorting) 알고리즘의 하나

   • 입력 배열(정렬되지 않은 값) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법

3️⃣ 정렬 알고리즘 시간복잡도 비교

4️⃣ 선택 정렬 코딩테스트 예제

1427. 소트인사이드

📌 문제 탐색하기

🌝 입력

1. 수 N이 주어진다. (1 <= N <= 1,000,000,000)

🌑 출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

🕔 시간제한

2초

🚨 접근

선택 정렬을 활용해 정렬해보자.

• Java에서 제공하는 정렬을 하면 되지만 선택 정렬 공부를 위해 선택 정렬을 통해 정렬을 해보자.

🙆‍♂️ 가능한 시간복잡도

시간 초과는 생각할 필요 없다.

• N이 1보다 크고 1,000,000,000보다 작지만 이 문제의 반복의 경우 10억번의 반복이 일어나는 것이 아닌 문자열 N의 size를 기준으로 반복이 일어나기 때문에 N 반복 한번 당 10번씩 반복이 수행된다.

📌 문제 풀이

1. N을 배열에 저장하여 내림차순으로 정렬한다.
2. 해당 배열을 순서대로 출력한다.

📌 정답 코드

import java.io.*;

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

        String str = br.readLine();
        int[] arr = new int[str.length()];

        for(int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(str.substring(i, i+1));
        }
        selectSort(arr);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
        }
        System.out.println(sb);
    }

    static void selectSort(int[] arr) {

        // 선택정렬 : 최대(최소)값을 찾아 앞쪽 요소부터 자리를 변경하여 정렬한다.
        for(int i = 0; i < arr.length; i++) {
            int max = -1;
            int maxIndex = -1;

            for(int j = i; j < arr.length; j++) {
                if(arr[j] > max) {
                    max = arr[j];
                    maxIndex = j;
                }
            }
            arr[maxIndex] = arr[i];
            arr[i] = max;
        }
    }
}