Insertion Sort (삽입 정렬)

 
const array = [1, 4, 2, 3, 5];
 
const insertionSort = (arr) => {
  // 2번째 요소부터 시작
  for (let i = 1; i < arr.length; i++) {
    // 이미 정렬된 배열 부분과 비교
    for (let j = i; j > 0; j--) {
      // 현재 요소가 이전 요소보다 작으면 교환
      if (arr[j] < arr[j - 1]) {
        let temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      } else {
        // 현재 요소가 이전 요소보다 크면 정렬 완료
        break;
      }
    }
  }
  return arr;
};
 
console.log(insertionSort(array)); // [1, 2, 3, 4, 5]