[Java] 삽입 정렬(Insertion Sort)

삽입 정렬(Insertion Sort)

: 삽입정렬은 현재 가리키는 값을 기준으로 앞에 있는 값들과 한 칸씩 크기 비교를 하여 알맞은 위치에 해당 값을 삽입하는 정렬 방식이다.

 

첫 번째 특징으로는 배열의 [0]은 비워 둔다. 그러므로 정렬할 값들은 배열의 [1]에서부터 저장한다.

두 번째 특징으로는 두 번째 값부터 기준으로 잡아 정렬을 한다. [1]에서부터 저장했으므로 [2]값부터 기준으로 잡는다.

 

일반적으로 시간복잡도는 O(n²)이다.

 

강의자료 그림

 

 

import java.io.*;

public class temp {
	static void InsertionSort(int[] arr, int n) {
		int temp=0;
		
		for(int i=2; i<=n; i++) {	// [2]값부터 기준으로 잡음
			temp=arr[i];
			arr[0]=temp;	// [0]에 현재 기준 값 임시 저장

			int j=i-1;	// j는 기준 값의 앞 부분을 가리킴
			while(arr[j] > temp) {	// 기준 값이 들어갈 위치를 찾음
				arr[j+1] = arr[j];	// 현재 값을 다음 자리에 밀어넣음
				j--;	// 한 칸 왼쪽 값을 가리킴
			}
			arr[j+1] = temp;	// 기준 값이 들어갈 위치를 찾았으므로 다음 자리에 기준 값 넣음
		
        
        	/* while문 대신 for문을 쓰는 방법
            for(int j=i-1; j>=0; j--) {
				if(arr[j] > temp) {
					arr[j+1] = arr[j];	
				}
				else {
					arr[j+1] = temp;
					break;
				}
			}
            */
        
		}
	}
	
	
	public static void main(String[] args) throws IOException{
  		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		
  		int n = 6;	// 값의 수
		int[] arr = new int[n+1];	// [0]을 비워둬야 하므로 크기는 n+1
		
		for(int i=1; i<arr.length; i++) 
			arr[i] = Integer.parseInt(br.readLine());	// [1]에서부터 값 저장
		
		InsertionSort(arr, n);	// 삽입정렬 수행
		
		for(int i=1; i<arr.length; i++) 
			bw.write(arr[i]+" ");	// 정렬된 값 출력
		bw.flush();
		bw.close();
		}
}

코드를 설명하자면

기준 값을 temp라 할 때, 우선 배열의 [0] 자리에 temp를 저장한다.

그리고 기준 값의 왼쪽에 있는 값들과 기준 값의 크기를 비교하여 기준 값보다 작거나 같은 값을 찾을 때까지 반복문이 실행된다. 이는 기준 값이 들어갈 위치를 찾기 위한 과정이다.

 

현재 가리키는 값이 기준 값보다 크면 기준 값이 들어갈 위치가 아니므로 현재 값을 오른쪽 위치에 저장하고 인덱스 j를 감소시켜 왼쪽 값을 가리킨다.

이 동작이 수행되면 기준 값이 원래 위치에서 사라지고 그 왼쪽 값이 기존 값의 위치에 저장되어 왼쪽 값이 2개 존재하게 된다. 하지만 이후 인덱스 j를 감소시키고 다음 자리에 값을 저장하면 중복 값이 사라지므로 걱정할 것이 없다. 

만약 이 동작이 계속 수행 되어 j가 0이 된 경우에는, [0]에는 기준 값이 저장되어 있고 [1]과 [2]에는 [1] 값이 저장되어 있을 것이다. 여기서 arr[0]==temp이므로 while문을 빠져나와 arr[1]에 temp 값을 저장함으로써 [1]에는 기준 값이, [2]에는 [1] 값이 저장된다. [0]은 고려하지 않아도 되며, [1]부터 마지막 index에 정렬이 완료된다. 

 

반면, 현재 가리키는 값이 기준 값보다 작거나 같으면 현재 가리키는 것의 다음 위치가 기준 값이 들어갈 위치인 것이다. 이 경우 while문을 빠져나와 다음 위치에 기준 값을 저장하면 정렬이 완료된다.