[Algorithm log] InsertionSort

삽입 정렬은 가장 처음 요소는 정렬이 되어있다고 생각하고

다음 요소부터 하나씩 비교하면서 정렬하는 방법이다.

.....

이걸 또 정렬될 때까지 하면 된다.

---

삽입 정렬에서 중요한 것은 위치를 찾아 들어갈 때 요소들을 한 칸씩 뒤로 밀어줘야 한다.  swap의 방식이 아니기 때문이다. 

그래서 정렬된 요소들에 대해 뒤에서 부터 비교를 해준 후 한 칸씩 당기면서 찾아들어간다.

반복해서 들어갈 위치를 찾는다.

전체 사이클은 첫 번째 요소를 제외한(첫 번째 요소는 정렬된요소로 간주하니까!) 전체요소의 길이만큼 돌 것이고 한 사이클당 요소는 앞에 정렬된 요소의 길이만큼 돌아야 할것이다.

code

function insertionSort(array){
  for(let i=1; i<array.length; i++){ // 전체 사이클
    let element = array[i];
    for(let j=i-1; j>=0; j--){  // 한 사이클
      // 정렬된 요소가 더 크면 한 칸 뒤로 땡긴다.
      if(array[j] > element){
        array[j+1] = array[j];
      }else{
        // 순서가 맞으면 그냥 끝내면 된다.
        break;
      }
      // 땡겨진 상태이므로 바로 넣어주면 된다.
      array[j] = element;
    }
  }
  return array;
}

두 번째 반복문을 보게 되면 for문을 역으로 사용한 것을 볼 수 있다. 뒤에서부터 비교하여 하나씩 당기기 위함이다.

한 개씩 당겼으니까 바로 넣어주면 된다.

for문 연습을 잘하자.!!