[알고리즘c++] 삽입 정렬(Insertion Sort)

삽입 정렬 요약

• 카드를 정렬하는 방법과 유사하다
  • 새로운 카드를 기존의 정렬된 카드 사이 올바른 자리를 찾아서 삽입하는 방식이다.
  • 새로 삽입될 카드의 수 만큼 반복하여 정렬
• 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하며, 자신의 위치를 찾아서 삽입하여 정렬을 완성하는 알고리즘
• 매 순서 마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.

삽입 정렬 알고리즘 

• 두 번째 자료부터 시작하여 앞의 자료들과 비교하여 삽입할 위치를 지정한 후 삽입
• 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째,  번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킨다.

 

삽입 정렬의 특징

• 배열 내에서 교환하는 방식이므로 공간복잡도는 O(1)이다. 기껏해야 원소를 교환할 때 쓰일 임시변수 정도의 추가공간만 필요하므로 in-place 정렬이다.
• 평균과 최악의 시간복잡도는 O(n^2)이다. 
• 삽입 정렬은 중복된 키 값의 순서가 정렬 후에도 유지되므로 stable 정렬이다.
• 선택 정렬이나 버블 정렬에 비해 상대적으로 빠르다.

소스 코드

 

실행 결과

 

그림으로 이해하면 훨씬 더 편하게 이해할 수 있는데 잘 정리 해놓은 그림이 있어 링크를 첨부합니다.

https://code-lab1.tistory.com/22

[알고리즘] 삽입정렬(insertion sort)이란? | c언어 삽입정렬 구현