JS 삽입정렬(Insertion Sort)

삽입 정렬은 왼쪽에서 오른쪽으로 가면서 각 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬방법이다. 
-항상 두번째 요소를 왼쪽 요소와 비교하면서 시작한다. 

-삽입 정렬은 항상 왼쪽에 비교 대상 데이터를 정렬되어있다는 가정하에 진행된다. 

-451이면 45와 비교하여 1을 왼쪽으로 넣어.

 

Big O 

worst Case: O(n^2): 정렬이 하나도 안되어 있는경우

best case : O(n):이미 정렬이 되어있는경우

 

장점: in place 알고리즘 이기 때문에 메모리가 절약된다.

-구현이 쉽고 이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되어있는지 안되었는지 테스트하는 용도로 사용할 수 있다. 

 

단점: 자료의 개수가 많아질수록 성능이 매우 떨어진다. 

 

stable: 중복된 데이터는 위치를 교환하지 않기 때문에 stable한 정렬이다. 

두번째 요소부터 선택해서 앞의 요소들이랑 비교해야하니깐 for문을 1부터 시작.

cur 변수에 현재 데이터를 저장하고 left 변수에 i-1을 넣는다.

while문을 돌려서 left가 0보다 크거나 같고, array[left]가 cur보다 큰경우 두 데이터를 교환하고  cur 변수에 array[left[를 담고 left -1을 해준다. 

array[left + 1]에 array[left] 값을 넣고 left 값을 하나씩 줄여가며 왼쪽과 비교하다가 교환이 끝나고 while문을 빠져나오면 맨 앞의 요소에 cur을 넣는다.