Algorithm 삽입(insertion) 정렬

시작하기

처음에는 왼쪽 끝의 숫자를 정렬이 끝났다고 간주합니다.
계속해서 아직 작업하지 않은 숫자 중에서 왼쪽끝에 있는 숫자를 꺼내서 왼쪽의 작업이 끝난 숫자와 비교합니다.
왼쪽의 숫자가 더 크면 숫자를 바꿉니다.
이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도착할 때까지 반복합니다.

[ 4, 2, 6, 8, 3, 1, 5, 7] 왼쪽의 4를 정렬이 끝났다고 간주합니다.
끝난 왼쪽의 숫자인 4와 다음 작업하지 않은 숫자2를 비교합니다. 4 > 2이므로 두 숫자의 자리를 바꾸고 작업을 완료합니다.
[ 2, 4, 6, 8, 3, 1, 5, 7 ] 다음 작업하지 않은 숫자 6과 4를 비교합니다. 6 > 4로 오른쪽의 6이 더 크므로 작업을 완료합니다.
이와 같은 방법으로 끝까지 정렬을 합니다.

Javascript

선택정렬을 javascript로 구현해보겠습니다.

const numbers = [9,3,8,2,1,7,6,4];
const insertionSort = (numberArray) => {
  let i = 1, j, temp;
  for (i; i < numberArray.length; i++) {
    temp = array[i];
    for (j = i - 1; j >= 0 && temp < numberArray[j]; j--) {
      array[j + 1] = array[j];
    }
    array[j + 1] = temp;
  }
  return array;
};
insertionSort(numbers);