[Data Structure] Insert Sorting

Stable sort

같은 요소들의 순서가 보장되는 정렬 

 

Time Complex

• Average time: n
• Worst time: n (important in ciritical systems)
• Space requirement: in-place sorts를 사용하면 최상의 케이스.

in-place sorts

정렬하기 위해 컬랙션을 복사하지 않는 방법, 다른 변수를 사용하지 않거나 아니면 거의 사용하지 않거나

 

Insertion sort

요소를 처음부터 끝까지 읽으면서 정렬시키는 방법

• 첫번쨰 요소는 이미 정렬된 리스트를 갖는다.
• 두번째 요소를 가져와 첫번째 요소와 비교 후 조건에 따라 서로 교환한다.
• 세번째 요소를 가져와 두번째 요소와 비교 후 조건에 따라 서로 교환한다.
• 계속 같은 방법으로 끝까지 진행

 

Time Complex

• Average time: quadratic in n
• Worst time: quadratic in n
• best-case: linear in n (이미 정렬되어 있을 때)

 

특징

• in-place sort
• worst space (n) is constant
• 컬렉션이 짧거나 거의 정렬되어 있는 컬렉션일 경우

function sorBytInsertion(nums: number[]) {
    for (let i = 1; i < nums.length; i++) {
        for (let j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
            const tmp = nums[j]
            nums[j] = nums[j - 1]
            nums[j - 1] = tmp
        }
    }
    console.log(nums) // [2, 3, 4, 5, 6] 
}

sortInsertion([6, 3, 2, 5, 4])