삽입정렬(insertionSort)

출처:위키백과

삽입정렬이란?

 

버블정렬(버블솔트), 선택정렬(셀렉션솔트) 와 함께 나오는 기본 정렬 알고리즘 중 하나

 

한번돌때마다 데이터의 최종위치가 결정되지 않는다.

 

점점 사이즈를 키워가는 방식으로 정렬된다.

 

const insertionSort = function (arr) {
  // TODO: 여기에 코드를 작성합니다.
  // 삽입정렬 
let i; 
let j;
for(i=1; i<arr.length; i++){
  let key = arr[i]
  for(j=i-1; j>=0 && arr[j]>key ; j--){
    arr[j+1] = arr[j]
  }
  arr[j+1] = key
}
return arr;
};

크기를 한칸씩 늘려가면서 정렬되는 방식.

i로 현재 정렬된 어레이의 사이즈를 알수있다.

j = i-1부터시작 <= 이미 정렬된 어레이 속으로 파고들 준비를 시작하는것. 기준점을 잡고 그 밑에있는것부터 시작

 

마지막 arr[j+1] = key <= 자기자신을 찾아서 마지막 정렬된 모습이다. 

 

하나씩 잡고. 하나씩 정렬하는 방식.

 

arr[j+1] = key부분을 생각하는것이 조금 까다롭긴했다.

 

https://www.youtube.com/watch?v=iqf96rVQ8fY&t=26s