삽입정렬(Insertion sort)

삽입정렬(Insertion sort)

• 손안의 카드를 정렬하는 방법과 유사하다
  • 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리에 찾아 삽입한다.
  • 새로 삽입될 카드의 수만큼 반복 하면 전체카드 정렬된다.
• 앞에서부터 순서대로 이미 정렬된 배열 부분과 비교하여 자신위 위치를 찾아 삽입
• 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 넣는다.
• 과정
  1. 두번째 부터 시작해서 자신의 왼쪽과 비교하여 삽입
  2. 오름차순 기준 현재  Key값보다 왼쪽 값이 크다면 왼쪽값을 오른쪽으로 한 칸 민다.

 

 

삽입정렬 장점

• 안정정렬
• 대부분의 원소가 정렬되어 있다면 매우 효율적

삽입정렬 단점

• 원소의 이동이 잦다.
• 양이 많다면 적합하지 않다.

삽입정렬 시간복잡도

• Best Case
  • 정렬이 되어 있는상태 O(n)
• Worst Case
  • 역순으로 되어있을 때 O(n^2)

 

참고

gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html