Computer Science/Algorithm, Data Structure

자바스크립트 알고리즘 삽입 정렬(Insertion Sort)

Write and Remember 2019. 6. 17. 19:47

출처: https://reactgo.com/javascript-insertion-sort-algorithm/

 

삽입 정렬(Insertion Sort)

 

출처: Wikipedia

 

삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

 

자신의 위치를 찾아 삽입함으로써 정렬을 완성한다.

 

배열의 두 번째부터 시작하고, temp라는 변수를 만들어서

 

값을 임시로 저장을 하고, 저장한 임시의 값보다 0번째 인덱스 값이 크다면

 

스왑 해준다. 

 

예를 들면,

 

array[0] = 4, array[1] = 1 

 

temp = array[1]

 

array[1] = array[0]

 

array[0] = array[1]

 

array[0] = 1, array[1] = 4

 

function insertionSort(arr, length = arr.length) {
  for (let i = 1; i < length; i++) {
    let temp = arr[i];
    let j;
    for (j = i - 1; j > -1 && arr[j] > temp; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = temp;
  }

  return arr;
}

console.log(insertionSort([4, 1, 3, 7, 2, 10, 9, 5])); // [1, 2, 3, 4, 5, 7, 9, 10]
1 2 3 4 5 6 7 8 ··· 12