4542 - Selection sort

• Submit
• Status
• Discuss
• Summary

Description

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.

Selection Sort로 배열을 오름차순으로 정렬한 결과와 교환 횟수를 구해보자.

어느 방향으로 정렬해도 상관 없지만 이 문제에서는 왼쪽부터 정렬하고 같은 값이 여러 개라면 가장 왼쪽에 있는 요소를 교환하는 방식으로 풀어보자.

Input

* Line 1 : 정렬할 배열 갯수 N (1≤N≤1000)

* Line 2~N+1 : 배열 arr의 크기 n이 입력되고 그 뒤로 배열 arr의 원소들이 공백으로 구분되어 입력된다. (1 ≤ n ≤ 100, -2000 ≤ arr[i] ≤ 2000)

Output

* Line 1~N : 정렬 중의 교환 횟수와 정렬 결과가 공백으로 구분되여 한 줄로 출력한다.

Sample Input

3
3 0 2 1
4 4 3 2 1
7 1 5 3 3 2 6 4

Sample Output

1 0 1 2
2 1 2 3 4
3 1 2 3 3 4 5 6

Hint

{1, 4, 2, 3, 3} 를 Selection Sort로 정렬하기

1~5번째 요소 검사하기:

    첫 번째 요소(1) 가 최솟값1 이므로 교환 안함

2~5번째 요소 검사하기:

    두 번째 요소(4) 와 최솟값(2) 교환 -> {1, 2, 4, 3, 3}

3~5번째 요소 검사하기:

    세 번째 요소(4) 와 최솟값(3) 교환 -> {1, 2, 3, 4, 3}

4~5번째 요소 검사하기:

    네 번째 요소(4)와 최솟값(3) 교환 -> {1, 2, 3, 3, 4}

{1, 4, 2, 3, 3}를 Selection Sort로 정렬할 때 교환은 총 3번 발생한다.