선택 정렬

설명

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

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

 

입력

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

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

 

출력

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

 

예시 입력 1 

6
13 5 11 7 23 15

 

예시 출력 1

5 7 11 13 15 23

 

문제 해결

 

 

선택 정렬이란?

1. 주어진 자료들 중 최소값을 찾아 맨 앞에 위치한 값과 교체한다.
2. 맨 처음 위치를 제외한 나머지 자료들 중 최소값을 찾아 두 번째 위치한 값과 교체한다.
...
 위 과정을 반복하며 정렬을 수행하는 방법을 말한다.

이를 코드로 구현해보자. 우선 for문은 주어진 자료보다 1 작은 만큼 반복한다. 

마지막 숫자는 자동으로 정렬되어 비교할 필요가 없기 때문이다.

for(int i = 0; i < N - 1; i++)

 

최소 인덱스 번호를 지정해주기 위해 min이라는 변수를 만들어 주고 이를 i로 초기화시켜준다.

j를 i부터 N까지 돌면서 현재 들어있는 값과 i번째에 들어있는 값을 비교하여 최소값을 찾아주고 이 때의 인덱스 값을 min에 넣어준다.

for (int j = i; j < N; j++) {
    if (arr[j] < arr[min]) {
        min = j;
    }
}

 

최솟값을 찾아주었으면 이를 i회전 했으면 i번째와 바꿔주어야 한다.

for문을 i로 돌고 있기 때문에 배열의 i번째에 있는 값과 min에 들어있는 값을 바꿔준다.

값을 서로 바꿔주는 전형적인 temp 방법을 써주었다.

int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;

 

위 과정을 N-1까지 반복해주면 오름차순으로 정렬이 될 것이다. 그럼 배열에서 값을 하나씩 꺼내 출력해주면 된다.

 

최종 코드

 

import java.util.Scanner;

public class P01_선택정렬 {
    public static void main(String[] args) {

        /** 선택 정렬 : i번째 값과 최솟값 탐색 값을 교환하는 방식을 반복하는 방법 **/

        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = in.nextInt();
        }

        for(int i = 0; i < N - 1; i++) {
            int min = i;

            for (int j = i; j < N; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }

        for (int i : arr) {
            System.out.print(i + " ");
        }

    }
}