섹션 6. Sorting and Searching(정렬, 이분검색과 결정알고리즘) 1. 선택정렬

문제

• N개의 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
• 정렬하는 방법은 선택정렬입니다.

입력

• 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.

출력

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

입출력 예제

---

풀이방식

이번 문제는 선택정렬을 사용하여 푸는 문제이다.

 

선택정렬이란 아래와 같이 첫번째 값와 두번째부터 마지막 값을 차례대로 비교하여 정렬하는 것을 말한다.

즉, 13과 5,11,7,23,15를 비교해서 가장 작은 값인 5를 맨 앞으로 놓는 것을 말한다.

아래 배열에서 선택정렬이 1회 수행되면 [5, 13, 11, 7, 23, 15] 가 나온다.

---

설계과정

1. 가장 작은 수가 들어갈 인덱스를 변수에 따로 저장한다.

2. 맨 앞을 제외하고, 1번째부터 N번째까지 돌면서 더 큰 값을 찾아 정렬한다.

3. 작은 수를 앞으로 보내서 정렬한다.

---

풀이과정

1. 값들을 입력받는 코드를 작성한다.

 

2. int[ ] 형으로 메소드를 작성한다.

 

3. 0부터 N-1까지 도는 for문을 작성하고 변수 idx를 선언한다.

• 맨 마지막 원소는 그 앞에 과정을 통해 자동적으로 정렬되므로 한번 더 돌 필요는 없다.
• idx : 가장 작은 숫자의 인덱스 번호를 저장하기 위한 변수

4. i+1부터 N까지 도는 for문을 작성하여 적은 수를 앞으로 보낸다.

• i 번째 수가 더 크다면, j번째 수와 인덱스 번호를 변경한다.

5. 임의의 변수를 선언하여 가장 적은 수를 앞으로 보내서 정렬한다.

---

답안소스

import java.util.Scanner;

public class Main {

	public int[] sort(int N, int[] arr) {
		
		for(int i=0; i<N-1; i++) {
			int idx = i;
			
			for(int j=i+1; j<N; j++) {
				if(arr[j] < arr[idx]) {
					idx = j;
				}
			}
			
			int tmp = arr[i];
			arr[i] = arr[idx];
			arr[idx] = tmp;
		}
		
		return arr;
	}
	
	public static void main(String[] args) {
		Main S = new Main();
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int x : S.sort(N, arr)) {
			System.out.print(x + " ");
		}
	}
}

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.