[Sorting] 선택 정렬(selection sort)(BOJ 1427번)

1. 선택 정렬의 정의 2. 선택 정렬의 과정 3. BOJ 1427: 소트인사이드

 

1. 선택 정렬의 정의

배열에서 최솟값(또는 최댓값)을 찾아가며 선택하는 정렬

 

2. 선택 정렬의 과정

① 정렬 범위 내에서 최솟값(최댓값)을 찾는다

② 맨앞의 데이터와 swap한다

③ 정렬 범위를 축소한다

④ 남은 정렬 범위가 없을 때까지 ①~③을 반복한다

public static void selectionSort(int[] arr){
    int index = 0;
    int len = arr.length;
    while(index < len){
        int min = arr[index];
        int minIdx = index;
        for(int i=index; i<len; i++){
            if(arr[i]<min){
                min = arr[i];
                minIdx = i;
            }
        }
        swap(arr, minIdx, index);
        index++;
    }
}​

 

3. BOJ 1427: 소트인사이드

https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

 

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

 

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

 

출력

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

 

난이도

실버 5

 

import java.util.Arrays;
import java.util.Scanner;

public class B1427_소트인사이드 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.next();
        int[] arr = new int[input.length()];

        for(int i=0; i<input.length(); i++){
            arr[i] = Integer.parseInt(String.valueOf(input.charAt(i)));
        }
        // input

        selectionSort(arr);
        // operation

        for(int i : arr){
            System.out.print(i);
        }
        // output
    }

    public static void selectionSort(int[] arr){
        int index = 0;
        int len = arr.length;

        while(index < len){
            int max = arr[index];
            int maxIdx = index;

            for(int i = index; i<len; i++){
                if(arr[i]>max){
                    max = arr[i];
                    maxIdx = i;
                }
            }
            swap(arr, index, maxIdx);

            index++;
        }
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}