삽입 정렬 알고리즘

삽입정렬 

- 각 숫자를 적절한 위치에 삽입하는 방법 

- 필요한 때만 위치를 바꾼다. (선택 정렬과 버블정렬보다 더 빠름) 

- 시간 복잡도 O(N^2)

- 기본적으로 i이전의 값들이 정렬이 되어있다고 가정

- 특정한 경우에는 굉장히 빠르게 작동 

  - 거의 정렬된 상태에 한해서는 어떤 알고리즘보다 빠름

 

정리) 

시간복잡도 O(N^2)를 가지는 정렬 알고리즘 

: 선택 정렬, 버블 정렬, 삽입 정렬 

 

내가 작성한 코드 

function insertSort(arr){
    for(let i=1; i<arr.length; i++){
        let value = arr[i]
        let j=i-1
        while(arr[j] > value){
            let temp = arr[j]; 
            arr[j] = arr[j+1]; 
            arr[j+1] = temp; 
            j--
          }
        }
    return arr
    }

 

선생님이 작성한 코드 

function insertionSort(arr){
	for(var i=1; i<arr.length; i++){
    	var currentVal = arr[i]; 
        for(var j = i-1; j>=0 && arr[j] > currentVal; j--){
        	arr[j+1] = arr[j]
        }
        arr[j+1] = currentVal; 
    }
    return arr
}