easy16
2022. 4. 10. 14:19
1. 선택정렬 : O(n2)
맨 앞쪽부터 정렬됨.
import java.util.Scanner;
class Main {
static int answer = 0;
public static void main(String args[]) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] arr = new int[n];
for ( int i = 0 ; i < n ; ++i)
arr[i] = in.nextInt();
for (int i = 0 ; i < n-1 ; i ++) {
int idx=i;
for ( int j = i+1; j < n ; j++) {
if( arr[idx] > arr[j]) {
idx = j;
}
}
int tmp =arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
}
for ( int v : arr) {
System.out.print(v + " ");
}
}
}
2. 버블정렬 :
맨 뒷쪽부터 정렬됨(비교횟수가 1씩 줄어든다.)
class Main {
public static void main(String args[]) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] arr = new int[n];
for ( int i = 0 ; i < n ; ++i)
arr[i] = in.nextInt();
for (int i = 0 ; i < n-1 ; i ++) {
for (int j = 0 ; j < n-i-1 ; j++) {
if( arr[j] > arr[j+1]) {
int tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
for ( int v : arr) {
System.out.print(v + " ");
}
}
}
3. 삽입정렬 : i 값을 기준으로 큰수를 뒤로 한칸씩 옮겨줌.(앞쪽에서부터 정렬)
최종적으로 tmp는 맨앞이나 자신보다 작거나 같은 수의 뒤에 삽입됨.
class Main {
static int answer = 0;
public static void main(String args[]) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] arr = new int[n];
for ( int i = 0 ; i < n ; ++i)
arr[i] = in.nextInt();
//i=1부터 시작
for (int i = 1 ; i < n; i ++) {
//기준 값을 tmp에 저장
int tmp = arr[i];
//i 이전값을 역방향으로 순회하며 정렬
int j = 0;
for ( j = i -1 ; j >= 0 ; j--) {
//tmp를 기준으로 큰 값을 뒤로 옮겨줌.
if( arr[j] > tmp )
arr[j+1] = arr[j];
else break;
}
// -1 or tmp보다 작거나 같은 값 뒤에 tmp를 저장
arr[j+1] = tmp;
}
for ( int v : arr) {
System.out.print(v + " ");
}
}
}