Algorithm. 삽입정렬

Algorithm 삽입(Insertion)정렬

알고리즘 공부를 위해 자바스크립트로 손코딩을 해보면서 알고리즘을 공부합니다.

대상 배열 숫자들을 오름차순으로 배열한다는 조건으로 설명합니다.

삽입정렬은 대상 숫자가 바로 앞에 숫자와 비교하여 작다면 앞으로 이동합니다.

첫번째 숫자는 비교대상이 없으므로 패스.

ex) [8, 2, 1, 5 ,9]

두번째 숫자는 첫번째 숫자와 비교해서 작으면 앞으로 이동합니다.

ex) [8, 2, 1, 5 ,9] → [2, 8, 1, 5, 9]

세번째 숫자는 두번째 숫자와 먼저 비교해서 작다면 위치가 전환, 그리고 또다시 첫번째 숫자와 비교해서 작다면 다시 앞으로 이동.

ex) [2, 8, 1, 5 ,9] → [2, 1, 8, 5, 9] → [1, 2, 8, 5, 9]

그리고 만약 세번째 숫자가 두번째 숫자보다는 작지만 첫번째 숫자보다 크다면 위치는 두번째에서 멈추게 됩니다.

ex) [1, 8, 2, 5 ,9] → [1, 2, 8, 5, 9] → [1, 2, 8, 5, 9]

이런 식으로 뒤에 있는 숫자가 바로 앞의 숫자와 계속 비교해가며 앞자리로 옮기게 됩니다.

자바스크립트 코드

단순하게 순환하는 것이 하나라고 생각하였습니다.

하지만 곰곰히 생각해보시면 순환사이클은 둘 입니다.

옆에 추가로 for문을 추가하게 됩니다.

두번째 작성에서 실수한 것은 내부 포문의 길이를 생각하지 않았다는 겁니다.

내부 for문의 길이는 회전할 때의 비교 횟수입니다.

외부 for문의 반복 횟수는 배열의 길이 만큼. 

i는 정렬할 대상 숫자의 위치,

j는 비교 대상 숫자의 위치입니다.

정렬 대상 숫자의 위치는 갈수록 증가합니다.(첫번째 for문의 역할)

비교 대상 숫자의 위치는 갈수록 감소합니다.(두번째 for문의 역할)

마지막 자바스크립트 코딩의 결과 입니다.

인터넷 브라우저 콘솔에서 값이 정상적으로 출력됩니다.

참고사이트: www.zerocho.com/category/Algorithm