[알고리즘] 정렬 - 삽입 정렬(Insertion Sort) (자바스크립트/node.js/javascript/알고리즘)

삽입 정렬 삽입 정렬이란? 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 배열의 왼쪽의 정렬된 부분으로 이동시킨다. 동작 과정 예를 들어 [3, 7, 2, 5, 1, 4]의 배열을 오름차순으로 정리한다고 하면 첫번째 숫자는 놔두고 두번째 자리 숫자부터 뽑아서 그 숫자가 첫 숫자보다 크면 첫 숫자 오른쪽에, 작으면 왼쪽에 넣는다. 세번째 자리 숫자를 뽑아서 앞의 두 숫자와 크기를 비교해서 알맞은 자리에 넣는다. 이렇게 끝까지 계속 한다. 시간 복잡도 Worst Case: O(n^2): 정렬이 하나도 안되어있는 경우 Best Case: O(n): 이미 정렬이 되어있는 경우 공간 복잡도 O(1) 장점 메모리가 절약된다. (배열을 새로 만들 필요 없이 주어진 배열 안에서 정렬시키면 되기 때문, in pla..

2021.05.03