알고리즘 - 선택정렬

핵심이론

최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 핵심

시간복잡도

N개의 숫자를 정렬한다고 가정하면

1번째 루프에서 N개를 탐색하며 최솟값을 찾고 그 값과 남은 정렬 부분의 가장 앞에 있는 데이터와 swap합니다

두번째 루프에서는 N-1개를 탐색하며 최솟값을 찾고 그 값과 남은 정렬 부분의 가장 앞에 있는 데이터와 swap합니다

이를 반복하게 되면

N번 탐색을 하며 그 탐색을 N번 하므로 N^2의 시간복잡도가 발생하게 됩니다

백준 1427

package org.example;

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] arr = new int[str.length()];

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

        for (int i = 0; i < str.length(); i++) {
            int MAX = i;
            for (int j = i + 1; j < str.length(); j++) {
                // MAX 인덱스를 구하는 코드
                if (arr[j] > arr[MAX]) {
                    MAX = j;
                }
            }
            swap(arr, i, MAX);
        }

        for (int i = 0; i < str.length(); i++) {
            System.out.print(arr[i]);
        }

    }

    static void swap(int[] arr, int i, int MAX) {
        if (arr[i] < arr[MAX]) {
            int tmp = arr[i];
            arr[i] = arr[MAX];
            arr[MAX] = tmp;
        }
    }
}

버블정렬과 달리 탐색범위에 대해 if문을 통해 MAX 값을 가지는 숫자의 인덱스를 찾고 해당 값과 남은 범위의 가장 앞부분을 swap() 해주며 모든 수를 정렬하는 알고리즘입니다