[알고리즘] 삽입 정렬(Insertion Sort)

n개의 데이터가 있는 배열이 있다고 하자.

 

2번째 데이터부터 n번째 데이터까지 하나씩 데이터를 선정하여 반복하는데 

 

선정된 데이터의 번쨰(index)가 k번째 데이터라면

k-1번째 데이터부터 1번째 데이터까지 k번째 데이터와 비교하면서, 

만약 비교당하는 ?번째 숫자가 k번째 데이터보다 크다면 ?번째 데이터를 오른쪽으로 한 칸씩 옮긴다.

 

그리고 ?번째에 원래의 k번째에 있던 데이터를 삽입한다.

 

이 과정이 끝나면 k+1번째를 시작하면서 같은 과정을 n번째 데이터까지 반복한다.

 

Java Code

public static void insertionSort(int[] array){

		for(int i=1; i<array.length; i++){

			int target= array[i];

			int j= i-1;

			while(j>=0 && array[j]> target){

				array[j+1]= array[j];

				j--;

			}

			array[j+1]= target;

		}

	}

 

Javascript Code

const input = [1, 2, 3, -3, -2, 5, 6, -6];

const solution = () => {
    const arr = input;

    for (let l = 1; l < arr.length; l++) {
        let target = arr[l];
        let j = l - 1;
        while (j >= 0 && arr[j] > target) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = target;
    }
    return arr;
};
console.time();
console.log(solution());
console.timeEnd();

 

Time Complexity

 

Best Case 일 때, 즉 자료가 이미 정렬되어 있는 상태일 때

n개의 자료가 있을 때 n-1번 비교를 하게 되므로, Time Complexity는 O(n)이 된다.

 

그러나 Worst Case, 예를 들어 오름차순으로 정렬하기 원하는 데 내림차순으로 정렬되어 있다면

첫 번째 반복에서 1번 비교, 두 번째 비교에서 2번 비교, ... n-1 번째 비교에서 n-1번 비교 하게 되므로

Time Complexity는 O(n^2)가 된다.