[종만북] 선택정렬(Selection Sort)과 삽입정렬(Insertion Sort) - JAVA

출처 : 시간복잡도 분석 연습 - 선택정렬 (종만복)

코드설명

선택정렬(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;
	}
	
}