[ Algorithm ] Insertion Sort(삽입 정렬)

329 단어

2 분

[ Algorithm ] Insertion Sort(삽입 정렬)

2023-03-27

Insertion Sort#

작동 원리#

[^1] 삽입 정렬은 버블 정렬이나 선택 정렬에 비해 구현이 조금 더 복잡한 정렬 알고리즘이다. 이 알고리즘은 목록을 순차적으로 훑으면서 현재 위치의 요소를 선택하고, 이를 이전에 방문했던 요소들 중 적절한 위치에 삽입하는 방식으로 동작한다. 삽입 과정에서 다른 요소들을 오른쪽으로 이동(shift)시켜야 할 수 있다. [^2]

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)#

평균 수행 시간: $O(N^2)$
최악 수행 시간: $O(N^2)$
메모리(공간 복잡도): $O(1)$
안정성: O

시간 복잡도 측면에서는 평균과 최악의 경우 모두 $O(N²)$ 을 보이며, 공간 복잡도는 $O(1)$ 이다. 또한 이 알고리즘은 안정성이 보장된다.

코드#

public class InsertionSort implements Sort{  
    @Override  
    public int[] sort(int[] array) {  
        for(int i = 1; i< array.length; i++){  
            int index = i;  
            while(index != 0 && array[index] < array[index-1]){  
                int temp = array[index];  
                array[index] = array[index-1];  
                array[index-1] = temp;  
                index--;  
            }  
        }  
        return array;  
    }  
}