삽입 정렬

삽입 정렬 (Insertion Sort)

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.

 

ex) 3 1 5 4 2 6

3 1 5 4 2 6    ( 3 )

1 3 5 4 2 6    ( 1 )

1 3 5 4 2 6    ( 5 )

1 3 4 5 2 6    ( 4 )

1 2 3 4 5 6    ( 2 )

1 2 3 4 5 6    ( 6 )

 

시간 복잡도 : O(n 제곱)