기본기)정렬)c#) 삽입 정렬(Insert Sort)

삽입 정렬(Insert Sort)

앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 매 순서마다 해당 노드를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

 

데이터를 하나씩 저장 이후에 순서를 넣는 방식이다.

 

public void SetInsertSort(List<int> _list){
        Logger.LogFormat("[Insert - Sort] Start ");
        int j, key;
        for(int i = 1; i < _list.Count;i++){
            key = _list[i];
            for(j = i-1; (j >=0 && _list[j]> key); j--){
                _list[j + 1] = _list[j];
            }

            _list[j + 1 ] =key;
            this.DebugText(_list);
        }
         Logger.LogFormat("[Insert - Sort] End ");
    }

삽입 정렬의 특징으로는 알고리즘 자체가 매우 간단하고 빠르고, 대부분의 노드가 이미 정렬되어있으면 매우 효율적이다. 노드가 많고 크기가 클경우에 적합하지 않다.

 

시간 복잡도 : O(n2)

공간 복잡도: O(n)

 ★★★☆☆