내가 개발해볼게!!
[Sorting] 선택 정렬(selection sort)(BOJ 1427번) 본문
1. 선택 정렬의 정의 2. 선택 정렬의 과정 3. BOJ 1427: 소트인사이드 |
1. 선택 정렬의 정의
배열에서 최솟값(또는 최댓값)을 찾아가며 선택하는 정렬
2. 선택 정렬의 과정
① 정렬 범위 내에서 최솟값(최댓값)을 찾는다
② 맨앞의 데이터와 swap한다
③ 정렬 범위를 축소한다
④ 남은 정렬 범위가 없을 때까지 ①~③을 반복한다
public static void selectionSort(int[] arr){
int index = 0;
int len = arr.length;
while(index < len){
int min = arr[index];
int minIdx = index;
for(int i=index; i<len; i++){
if(arr[i]<min){
min = arr[i];
minIdx = i;
}
}
swap(arr, minIdx, index);
index++;
}
}
3. BOJ 1427: 소트인사이드
https://www.acmicpc.net/problem/1427
문제
배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.
입력
첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.
난이도
실버 5
import java.util.Arrays;
import java.util.Scanner;
public class B1427_소트인사이드 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String input = sc.next();
int[] arr = new int[input.length()];
for(int i=0; i<input.length(); i++){
arr[i] = Integer.parseInt(String.valueOf(input.charAt(i)));
}
// input
selectionSort(arr);
// operation
for(int i : arr){
System.out.print(i);
}
// output
}
public static void selectionSort(int[] arr){
int index = 0;
int len = arr.length;
while(index < len){
int max = arr[index];
int maxIdx = index;
for(int i = index; i<len; i++){
if(arr[i]>max){
max = arr[i];
maxIdx = i;
}
}
swap(arr, index, maxIdx);
index++;
}
}
public static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
'Algorithm > Algorithm' 카테고리의 다른 글
[Sorting] 삽입 정렬(selection sort)(BOJ 1427번) (0) | 2023.06.23 |
---|---|
[Sorting] 버블 정렬(BOJ 2750번) (0) | 2023.06.16 |