4. 삽입 정렬 Insertion sort (Java)

1. 삽입 정렬 (Insertion sort)

 

 - 오름차순을 기준으로 정렬 

 - 알고리즘 해석 

  -> 두 번째 자료부터 시작하여 key변수에 저장하고, 그 앞(왼쪽)의 자료들과 비교하여 비교대상 값이 key 값보다 크면, key변수에 더 큰값을 삽입하고, 첫 번째 자료의 위치까지 계속해서 큰값을 찾는 작업을 수행 후, 더이상 큰 값이 없거나, 인덱스가 0이 되면 반복을 마친 후 종료된 시점의 위치에 key값을 옮겨 정렬하는 알고리즘

 - 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

 - 처음 key 값은 두 번째 자료부터 시작.

 

 

1) C언어 코드

void insertion_sort(int n, int data[]){
  for (int i = 1; i < n; i++){
    int tmp = data[i];
    int j = i - 1;
    while (j >= 0 && data[j] > tmp){
      data[j + 1] = data[j];
      j-;
    }
    data[j + 1] = tmp;
  }
}

 

2) Java 코드

package inflearn.chapter1.algorithm;

import java.util.Arrays;

public class InsertionSortImplement {
	
	public static void main(String[] args) {
		
		int[] arrNum = {8, 5, 6, 2, 4};
		insertion_sort(arrNum.length, arrNum);
		System.out.println(Arrays.toString(arrNum));
	}
	
	static void insertion_sort(int n, int data[]) {
	  for (int i = 1; i < n; i++) { //2번째 값부터 시작하여 마지막 값까지 비교하는 수행을 총 자료수(n) -1번 함
	    int key = data[i]; //자리를 찾아줄 값을 임시로 key변수에 저장 
	    int j = i - 1; //바로 옆(왼쪽)에 있는 값(j = i - 1)부터 비교
	    while ( (j >= 0) && (data[j] > key )) { //비교 작업 수행.비교 작업은 최종적으로 첫번째 값까지(j >= 0)
	      data[j + 1] = data[j]; //비교 작업 과정에서 비교 대상의 값(data[j])이 자리를 찾아줄 값(data[i])보다 큰 경우, 비교 대상의 값을 현재 자리를 찾아줄 값으로 대입(교환작업)
	      // !! 왼쪽 값이 크지 않다는 의미는 결국 더 비교할 필요가 없다는 뜻.
              j--; //다음 왼쪽수 비교
	    }
	    data[j + 1] = key; //찾은 자리에 자리를 찾아줄 값 data[i] 대입.
	  }
	}

}

 

1-1 삽입 정렬(insertion sort) 알고리즘의 특징

 - 장점 : 안정적인 정렬 방법. 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 대부분 위 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

 - 단점 : 비교적 많은 레코드들의 이동을 포함한다. 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않다.

1-2  삽입 정렬(insertion sort)의 시간복잡도
 - 최선의 경우

  -> 비교 횟수 : 이동 없이 1번의 비교만 이루어진다.

외부 루프: (n-1)번.

Best T(n) = O(n)

 - 최악의 경우(입력 자료가 역순일 경우)

  -> 비교 횟수 : 외부 루프 안의 각 반복마다 i번의 비교 수행.

외부 루프: (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2).

  -> 교환 횟수 : 외부 루프의 각 단계마다 (i+2)번의 이동 발생.

n(n-1)/2 + 2(n-1) = (n^2+3n-4)/2 = O(n^2)
Worst T(n) = O(n^2)

 

 

*삽입정렬 알고리즘 내용참고

참고: https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html