<JAVA/자바> 선택정렬(Selection sort)

💡 개념

선택 정렬이란, 정렬되지 않은 데이터들 중 기준 위치의 데이터와 나머지 중 가장 작은 데이터를 찾아 교환해나가는 정렬 방식이다.
(처음 기준 위치는 0번 인덱스를 가르킨다.)

---

📌 과정

출처: algorithmcanvas

1. 기준 위치를 제외한 나머지 인덱스 중 더 작은 값 중 최소값의 위치를 찾는다.

2. 그 위치를 기준 위치와 변경한다.

   (만약, 더 작은 값이 없다면 pass)

👨‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static int N;
    static int[] selectionSort;

    public static void main(String[] args) throws IOException {
        init();

        for (int switchIdx = 0; switchIdx < N - 1; switchIdx++) {
            int curMinIdx = switchIdx;
            for (int otherIdx = switchIdx + 1; otherIdx < N; otherIdx++) {

                if (selectionSort[curMinIdx] > selectionSort[otherIdx])
                    curMinIdx = otherIdx;

            }

            if (curMinIdx == switchIdx)
                continue;

            int tmp = selectionSort[switchIdx];
            selectionSort[switchIdx] = selectionSort[curMinIdx];
            selectionSort[curMinIdx] = tmp;
        }

        for (int idx = 0; idx < N; idx++) {
            sb.append(selectionSort[idx]).append(" ");
        }

        System.out.println(sb);
    }

    public static void init() throws IOException {
        N = Integer.parseInt(br.readLine().trim());

        st = new StringTokenizer(br.readLine().trim());
        selectionSort = new int[N];
        for (int idx = 0; idx < N; idx++) {
            selectionSort[idx] = Integer.parseInt(st.nextToken());
        }
    }
}

---

⏱️ 시간복잡도

비교 연산

• 첫 번째 루프에서는 N-1번의 비교가 이루어진다.
• 두 번째 루프에서는 N-2번의 비교, 세 번째 루프에서는 N-3번의 비교, ..., 마지막 루프에서는 1번의 비교가 이루어진다.
• 따라서 총 비교 횟수는 다음과 같다.
  $(N-1) + (N-2) + (N-3) + \dots + 1 = \frac{N(N-1)}{2}$
• 즉, O(N²) 로 표현할 수 있다.

교환 연산

• 최대 N-1번의 교환 연산이 이루어진다.
• 교환 연산의 시간 복잡도는 O(1) 이므로, 전체 시간 복잡도에 미치는 영향은 미미하다.