출처 : 시간복잡도 분석 연습 - 선택정렬 (종만복)
코드설명
선택정렬(Selection Sort)와 삽입정렬(Insertion Sort)를 구현했습니다.
선택정렬은, 맨 앞에서부터 하나씩 정렬해나가며, 이 정렬과정에서 매번 N-1개, N - 2개, N-3... 1개 이런식으로 반복문이 수행됩니다. 시간복잡도를 계산해보면 O((N)(N-1) / 2) = O(N^2)입니다. 즉, [i .. N]의 탐색범위에서 가장 작은 숫자를 "선택"해서 맨 앞에 설정한다 라고 이해하면 됩니다.
단순하게는 FOR문이 중첩되어 실행되므로 O(N^2)로 봐도 됩니다.
즉, 가장 맨 앞부터 가장 작은 숫자를 하나씩 채워나가는 것 입니다. 항상 가장 작은 숫자가 맨 앞씩 채워진다는 것이 보장되므로 앞의 숫자가 고정되며 A[N]까지 진행하면 결국 모두 정렬됨을 알 수 있습니다.
삽입정렬은, 만약 앞의 숫자(J-1)이 현재숫자(J)보다 크다면, SWAP 시키며 정렬합니다.
최악의 경우 빅 O(N^2) 입니다. 하지만, 만약 정렬된 숫자라면, O(N)의 시간복잡도(선형시간)를 가집니다.
테스트케이스
입력 예시 1
10
5 78 127 42 57 2 87 21 876 971
결과 예시 1
2 5 21 42 57 78 87 127 876 971
입력 예시 2
10
78 5 127 42 57 2 87 21 876 971결과 예시 2
2 5 21 42 57 78 87 127 876 971코드
선택정렬을 수행했을때의 코드입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int answer = 0;
public static int[] input;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
input = new int[N];
for(int i=0;i<N;i++) {
input[i] = Integer.parseInt(st.nextToken());
}
selectionSort(input);
for(int value : input) {
System.out.print(value+" ");
}
System.out.println();
}
public static void selectionSort(int[] A) {
for(int i=0; i<A.length; i++) {
int minIdx = i;
for(int j=i+1; j<A.length; j++) {
if(input[minIdx] > input[j]) {
minIdx = j;
}
}
swap(i, minIdx);
}
}
public static void swap(int aIdx, int bIdx) {
int storeNum = input[aIdx];
input[aIdx] = input[bIdx];
input[bIdx] = storeNum;
}
}선택정렬 코드 2
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[] A = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
A[i] = Integer.parseInt(st.nextToken());
}
selectionSort(A);
for(int i=0;i<N;i++) {
System.out.print(" "+A[i]);
}
}
public static void selectionSort(int[] A){
for(int i=0;i<A.length; i++) {
int minIdx = i;
for(int j=i + 1; j < A.length; j++) {
if(A[minIdx] > A[j]) {
minIdx = j;
}
}
swap(A, i, minIdx);
}
}
public static void swap(int[] A, int posA, int posB) {
int temp = A[posA];
A[posA] = A[posB];
A[posB] = temp;
}
}
삽입정렬을 수행했을때의 코드입니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, M;
public static int answer = 0;
public static int[] input;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
input = new int[N];
for(int i=0;i<N;i++) {
input[i] = Integer.parseInt(st.nextToken());
}
insertionSort(input);
for(int value : input) {
System.out.print(value+" ");
}
System.out.println();
}
public static void insertionSort(int[] A) {
for(int i=0;i<N;i++) {
int j = i;
while( j > 0 && A[j-1] > A[j]) {
swap(j-1, j);
j--;
}
}
}
public static void swap(int aIdx, int bIdx) {
int storeNum = input[aIdx];
input[aIdx] = input[bIdx];
input[bIdx] = storeNum;
}
}삽입정렬 2
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int C, N, M;
public static int answer = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
int[] A = new int[N];
st = new StringTokenizer(br.readLine());
for(int i=0;i<N;i++) {
A[i] = Integer.parseInt(st.nextToken());
}
insertionSort(A);
for(int i=0;i<N;i++) {
System.out.print(" "+A[i]);
}
}
public static void insertionSort(int[] A) {
for(int i=0; i<A.length;i++) {
int j = i;
while(j > 0 && A[j-1] > A[j]) {
swap(A, j-1, j);
j-= 1;
}
}
}
public static void swap(int[] A, int posA, int posB) {
int temp = A[posA];
A[posA] = A[posB];
A[posB] = temp;
}
}