섹션6. Sort - 1. 선택 정렬

📌 문제 설명

N개의 숫자가 입력되면 선택 정렬(Selection Sort) 알고리즘을 이용해 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

---

📝 입력 & 출력

입력

• 첫 번째 줄에 자연수 N(1 ≤ N ≤ 100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 기준으로 입력됩니다.

출력

• 선택 정렬 알고리즘을 이용해 오름차순으로 정렬된 수열을 한 줄로 출력합니다.

---

🔹 예제 입력 & 출력

예제 입력 1

 

6
13 5 11 7 23 15

 

예제 출력 1

 

5 7 11 13 15 23

---

💡 해결 방법

• 선택 정렬은 배열을 순회하면서, 가장 작은 값을 찾아 앞으로 보내는 방식입니다.
• 각 회차마다 현재 위치 이후의 값들 중 가장 작은 값을 선택하여 현재 위치와 교환합니다.
• 시간 복잡도는 O(N²)이지만, 구현이 간단하고 정렬의 개념을 이해하는 데 유용한 알고리즘입니다.

---

💻 코드 구현 (Java)

package partSort;

import java.util.*;

public class Problem1 {
	public int[] solution(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) {
		Problem1 T = new Problem1();
		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();
		for (int x : T.solution(n, arr)) System.out.print(x + " ");
		kb.close();
	}
}

---

📖 코드 설명

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;
}

• i번째 위치에 들어갈 최소값을 찾기 위해 j를 이용해 뒤쪽 배열과 비교
• 가장 작은 값을 가진 idx를 찾고, i번째 요소와 교환

---

⏳ 시간 복잡도 분석

• 이중 반복문 사용: O(N²)
• 선택 정렬은 데이터의 크기에 관계없이 항상 동일한 시간복잡도

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런