단순 선택 정렬(straight selection sort)
가장 작은 요소를 맨 앞으로 이동하고, 두 번째 작은 요소는 맨 앞에서 두 번째로 이동하는 작업을 반복하는 알고리즘
- 아직 정렬하지 않은 부분에서 가장 작은 키값(a[min]) 선택
- a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소 교환
for (int i = 0; i < n - 1; i++) { // min <- a[i], ..., a[n-1]에서 값이 가장 작은 요소의 인덱스 // a[i]와 a[min]의 값을 교환 }
단순 선택 정렬
package ch06_3; import java.util.Scanner; // 단순 선택 정렬 /* 서로 떨어져 있는 요소를 교환하므로 안정적이지 않음 만약 값이 같은 요소가 중복되어 있는 배열을 정렬할 경우 두 요소의 순서가 바뀔 수 있음 */ public class Ex01_selectionSort { // a[idx1]과 a[idx2]의 값을 교환 static void swap(int[] a, int idx1, int idx2) { int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] = t; } // 단순 선택 정렬 static void selectionSort(int[] a, int n) { for (int i = 0; i < n - 1; i++) { int min = i; // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 저장 for (int j = i + 1; j < n; j++) { if (a[j] < a[min]) { min = j; } } swap(a, i, min); // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환 } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.println("단순 선택 정렬"); System.out.print("요솟수: "); int nx = scanner.nextInt(); int[] x = new int[nx]; for (int i = 0; i < nx; i++) { System.out.print("x[" + i + "]: "); x[i] = scanner.nextInt(); } selectionSort(x, nx); // 배열 x를 단순 선택 정렬 System.out.println("오름차 순으로 정렬했습니다."); for (int i = 0; i < nx; i++) { System.out.println("x[" + i + "] = " + x[i]); } } }
'공부기록 > 알고리즘' 카테고리의 다른 글
Chapter 06-4. 정렬 알고리즘_단순 삽입 정렬 (0) | 2024.08.16 |
---|---|
Chapter 06-2. 정렬 알고리즘_버블 정렬 (0) | 2024.08.16 |
Chapter 06-1. 정렬 알고리즘_정렬 알고리즘이란 (0) | 2024.08.16 |
Chapter 05-4. 재귀 알고리즘_8퀸 문제 (0) | 2024.08.11 |
Chapter 05-3. 재귀 알고리즘_하노이의 탑 (0) | 2024.08.11 |
댓글