[알고리즘] 선택 정렬 with Java

1. 선택 정렬

 

설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 선택정렬입니다.

입력

첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.

두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

오름차순으로 정렬된 수열을 출력합니다.

예시 입력 1 

6
13 5 11 7 23 15

예시 출력 1

5 7 11 13 15 23

선택정렬, 예전에 공부했고 계속 했던건데도 원리를 자꾸 까먹는다.. 메모리 낭비가 적은 대신 그렇게 썩 좋은 알고리즘은 아닌 것으로 알고있다.

 

오늘 배운 것

1. 선택정렬 알고리즘

. 제일 최소를 선택 한 후, 기준이 되는 배열의 요소와 값을 바꿔준다.

. O(N^2)의 복잡도를 가진다.

. 메모리 낭비가 적다.

 

2. 문제 풀이

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        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();
        }
        solution(arr);

    }

    private static void solution(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int idx = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[idx] > arr[j]){
                    idx = j;
                }
            }
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }

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