[알고리즘] 삽입 정렬 - Javascript 자바스크립트로 구현하기

삽입 정렬

삽입 정렬은 배열의 앞에서부터 차례대로 각 요소들을 자신의 앞에 위치한 요소들과 비교하여 자기 자리에 맞게 삽입해주는 정렬 방식이다. 

시간 복잡도는 O(n^2) 이다. 

 

삽입 정렬 예제

배열 : [30, 24, 11, 21, 13]

주어진 배열을 삽입 정렬을 이용해 오름차순으로 정렬해보자.

 

 

array[1] = 24의 적절한 위치를 찾아보자. 

index = 1 로 두고 array[1]의 값부터 시작해보자. 

array[index-1] = array[0] = 30 과 비교해보면 24 < 30 이다.

따라서 array[1] = 24는 30의 앞에 위치해야한다. 

 

array[2] = 11의 적절한 위치를 찾아보자. 

이제 다음 index = 2, 

array[2] = 11의 위치를 찾아보자. 

바로 앞의 값 array[1]와 비교해보면 30 > 11이므로 11이 30보다 앞에 위치하여야 한다.

따라서 우선 위와같이 array[1]과 array[2]값의 자리를 교체해준다. 

 

그 다음, 바로 앞의 값은 24이다.  24 > 11 이므로 위와 동일하게 자리를 서로 바꿔준다. 

그럼 위와 같이 11의 적절한 위치 찾기가 끝났다. 

 

array[3] = 11의 적절한 위치를 찾아보자. 

array[2] 값인 30 > array[3] 값인 20 이다. 따라서 21과 30의 자리를 교체한다. 

array[1] 값인 24 > 21이므로 array[1]과 24 자리를 교체한다. 

그 다음 array[0] 값 11 < 21 이므로 자리를 변경하지 않는다. 

 

array[4] = 13의 적절한 위치를 찾아보자. 

위에서 해왔던대로 array[4] 바로 앞의 요소부터 비교한다. 

array[3]은 30 > 13 이므로 둘의 자리를 변경한다. 

다음 array[2]는 24 > 13으로 자리를 변경한다. 

array[1] 은 21 > 13 이므로 자리를 변경한다. 

마지막으로 array[0] = 11 과 13을 비교하면 11 < 13 이므로 자리가 변경되지 않는다. 

 

따라서 

배열이 [11, 13, 21, 24, 30] 으로 오름차순 정렬되었다.

 

위에서 해온 정렬을 이제 코드로 구현해보자. 

삽입 정렬 구현 코드

for (let i = 1; i < array.length; i++) {
  let temp = answer[i];
  let index = i - 1;
  while (index >= 0 && answer[index] > temp) {
    answer[index + 1] = answer[index];
    index--;
  }
  answer[index + 1] = temp;
}

for 문으로 배열의 앞에서부터 차례대로 각 요소들의 위치를 찾아줄 수 있도록 한다.

let temp = answer[i]  는 배열의 i-1번째 요소( 위치를 찾고자하는 타겟 요소 )를 담는다. 

index 는 temp 즉 위치를 찾고자하는 타겟 요소의 앞 요소들의 인덱스 값이 담기는 변수이다. 

ex ) i = 2 일 경우, index 는 차례대로 1, 0 이 될 것이다. 

while 문은 타겟 요소의 앞 요소들과 타겟 요소의 값을 비교하며 타겟 요소의 위치를 정해준다.