[JS] 삽입 정렬

1. 삽입 정렬

 삽입 정렬은 선택 정렬, 버블 정렬과 함께 시간복잡도 $$ O(n^2) $$ 을 가진다.

 

 하지만 삽입 정렬은 선택정렬, 버블 정렬과 같은 시간복잡도를 가지지만, 두 정렬보다는 빠른 속도를 가진다.

 

 그 이유는 선택, 버블 정렬의 경우에는 일일히 원소 값을 비교하는 탐색 과정을 거치지만,

 

 삽입 정렬의 경우, 필요할 때만 위치를 바꾸는 방식을 이용하기 때문이다. 

 

 「자바로 배우는 쉬운 자료구조, 한빛 미디어」 책에서는 S(정렬 되어있는 부분집합), U(정렬되지 않은 부분집합)으로

 

 나누어서 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서

 

 위치를 찾아 삽입하는 방식을 이용한다고 설명하지만, 결국 의미는 같다.

 

 음, 그러니까 그냥

 

필요할 때만 위치를 바꾼다.

 

라고 생각하면 될 것 같다.

 

2. 동작 순서

동작 순서를 보면, "필요할 때만 위치를 바꾼다"라는 말을 왜 했는지 알 수 있을 것이다.

 

지난 번에 글을 썼던 버블 정렬, 선택 정렬의 입력 예제를 똑같이 가져와서 설명을 하겠다.

 

[그림 1] 입력 예제

 

 우리는 이제 삽입 정렬을 이용해서 [5, 10, 1, 2, 6]을 오름차순으로 정렬할 것이다.

 

 먼저, [5, 10, 1, 2 ,6]을 S(정렬 되어 있는 부분집합), U(정렬 되지않은 부분집합) 두 개의 부분집합으로 나눈다.

 

[그림 2] 두 개의 부분집합 S, U

 명심해야 할 것은 하나의 배열을 나누어서 부분집합을 두 개로 만드는 것이지, 집합을 두 개 만들 필요는 없다.

 

 따라서 이를 프로그래밍하면 다음과 같다.

const arr = [5, 10, 1, 2, 6]; //입력 리스트

/*
이런식으로 나눌 필요는 없다.

const s = arr.shift();
const u = arr;

그저 우리는 이중 반복문을 다음과 같이 만들어서 S, U로 나누면 된다.
*/

for(let i=1; i<arr.length; i++){
	let j = i;
    while(arr[j-1] > arr[j]){
    	스와핑 작업
    }
}

  

 for문을 보자. for문 안에 i를 1부터 시작하게 한 이유는 부분집합을 

 

S = [5]  U = [10, 1, 2, 6]

 

 으로 나누기 위해서다.

 

 그 다음으로는 U라는 집합에서 원소를 하나씩 꺼내서 S 집합 요소를 끝에서부터 비교하면 되는 것이다.

 

 이 과정을 그림으로 좀 더 디테일하게 풀어보면 다음과 같다.

 

[그림 3] while문의 과정

 주황색 부분을 S, 노란색 부분을 Y라고 하자.

 

for(let i=1; i<arr.length; i++)
	let j = i;
	while(arr[j-1] > arr[j]){
    	스와핑
        j--;
	}

 먼저 arr[1]인 10을 5와 비교한다. 5가 10보다 작기 때문에 while문에 진입하질 못한다.

 

 하지만  i=2일 경우, arr[2]는 1이 된다. arr[1]은 10, arr[2]는 1, 10은 1보다 크기때문에

 

 1과 10의 위치를 스와핑 한 후 j의 값을 1감소한다.

 

 j=1이 되고, arr[0]은 5, arr[1]은 1, arr[0]은 arr[1]보다 크기때문에 두 값을 또 스와핑한다.

 

 이런 방식으로 정렬을 수행한다면, 오름차순으로 정렬을 할 수 있을 것이다.

 

3. 시간 복잡도

 삽입 정렬의 시간복잡도는 최악의 경우가 $$ O(n^2) $$ 이다. 

 

 하지만 선택 정렬과 버블 정렬보다는 비교적 빠르다.

 

 또한 

 

 [2, 3, 4, 5, 1] 처럼 90% 정렬이 되어있는 입력 값이 들어오는 상황에서는

 

 퀵 정렬, 힙 정렬 보다도 빠르다.

 

 따라서, 삽입 정렬은 상황에 따라 최고의 성능이 될 수도, 최악의 성능이 될 수 있다.

 

4. 프로그램 코드

 프로그램 코드는 다음과 같다.

const bubbleSort = (arr) => {
  for(let i=1; i<arr.length; i++){
    let j = i;
    let temp = 0;
    while(arr[j-1] > arr[j]){
      temp = arr[j-1];
      arr[j-1] = arr[j];
      arr[j] = temp;
      j--;
    }
  }
  return arr;
}

 

5. 참고자료

1. 동빈나 님의 블로그 - 4. 삽입정렬

2. 자바로 배우는 쉬운 자료구조, 한빛 미디어