삽입 정렬은 첫 숫자는 놔두고, 두 번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣습니다. 

세 번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣습니다. 

이렇게 끝까지 계속하면 정렬됩니다.

코드로 보면 어려우니까 배열이 움직이는 과정을 쉽게 예를 하나 들어서 순서대로 봅시다. 

크게 두 가지 과정이 있습니다. 

첫째는 다음 숫자를 선택하는 과정이고, 둘째는 선택한 숫자를 이미 정렬된 숫자들과 비교해 알맞은 위치에 넣는 과정입니다.

[5, 6, 1, 2, 4, 3]과 같은 배열이 있습니다.

첫 번째는 넘어가고 두 번째부터 시작합니다. 숫자 6을 선택하고

앞의 5와 비교하는데 5보다 크기 때문에 그냥 그 자리에 둡니다. 다음 숫자 1을 선택합니다.

1은 앞의 5, 6보다 작기 때문에 5, 6 앞에 넣어줍니다. 다음 숫자 2를 선택합니다.

2는 1보다는 크고, 5와 6보다는 작기 때문에 그 사이에 넣어줍니다. 다음 숫자 4를 선택합니다.

마찬가지 과정으로 1,2와 5,6 사이에 넣어줍니다. 다음 숫자 3을 선택합니다.

마지막으로 1,2와 4,5,6 사이에 3을 넣고, 다음 숫자가 없으므로 종료합니다.

const unorganizedArray = [5, 6, 1, 2, 4, 3];

for (i; i < unorganizedArray.length; i++) {

  temp = unorganizedArray[i]; //  선택 숫자 => 2  i =3

  // 선택한 숫자가 정렬된 숫자보다 작으면 뒤로 한칸씩 밀어냄

  for (j = i - 1; j >= 0 && temp < unorganizedArray[j]; j--) {

    unorganizedArray[j + 1] = unorganizedArray[j];

  // j 값이 감소한다면, 감소된 만큼의 숫자를 반영하여 선택된 숫자를 정해진 위치에 넣음

선택한 숫자보다 큰 숫자들은 오른쪽으로 한 칸씩 밀어내고 빈 자리에 선택한 숫자를 넣는 겁니다.

삽입 정렬은 성능이 뛰어난 정렬은 아닙니다. 

작은 수에서만 효과적인 경우가 많습니다. 

첫 번째로 배우는 이유는 간단하기 때문입니다. 

또한 이미 정렬되어 있는 배열에 새로운 원소를 집어넣어 다시 정렬할 때는 매우 효과적입니다. 

새 원소를 처음부터 한번씩만 기존의 원소들과 비교하면 되니까요.

보통 반복문을 두 번 중첩해서 돌면 성능이 그리 좋지 않습니다. 정렬이 효과적인지 아닌지 판단하려면 복잡도라는 개념을 알아야합니다. 

삽입 정렬은 다른 정렬에 비해 복잡도가 높기 때문에 효과적이지 못하다고 평가받습니다.

시간 복잡도는 보통 Worst Case를 기준으로 측정하므로 O(n²)이 된다.

공간 복잡도는 O(1)로 측정되며, 메모리를 거의 차지하지 않는다.

https://www.zerocho.com/category/Algorithm/post/57e39fca76a7850015e6944a

삽입 정렬

Body Parser란?