정렬-삽입 정렬(insertion sort)

*정렬-삽입 정렬(insertion sort)

-수열의 왼쪽부터 순서대로 정렬하는 방식

-우측의 미탐색 영역 숫자를 하나 꺼내 정렬이 끝난 영역의 적절한 위치에 삽입하는 방식

-각 라운드의 첫 숫자를 그 왼쪽에 있는 숫자와 비교, 만약 왼쪽 숫자가 작다면 라운드 종료

-꺼낸 숫자가 정렬 완료 영역의 숫자보다 작을 때 그 숫자가 가장 왼쪽에 도착할 때까지 비교 및 교체작업

-최악의 입력 데이터는 역순(큰 순)으로 나열된 경우

 

*삽입 정렬의 예

-1부터 9까지의 숫자 정렬(5-3-4-7-2-8-6-9-1)

-첫 라운드는 왼쪽 끝의 숫자(5)를 정렬이 끝났다고 간주

-5만 정렬된 상태(5-3-4-7-2-8-6-9-1)

-미탐색 영역 숫자 중 왼쪽 끝 숫자(3)를 꺼내 작업이 끝난 왼쪽 숫자(5)와 비교

-왼쪽의 숫자가 크면 두 개의 숫자 교체(3-5-4-7-2-8-6-9-1)

-자신보다 작은 숫자가 나타날 때까지 왼쪽으로 이동함

-정렬 반복

-(3-4-5-7-2-8-6-9-1)

-(3-4-5-7-2-8-6-9-1)

-(2-3-4-5-7-8-6-9-1)

-(2-3-4-5-7-8-6-9-1)

-(2-3-4-5-6-7-8-9-1)

-(2-3-4-5-6-7-8-9-1)

-(1-2-3-4-5-6-7-8-9)

-정렬 완료

 

 

 

 

---

이 포스팅에 작성한 내용은 이시다 모리테루, 미야자키 쇼이치, ⌜알고리즘 도감⌟, 김완섭 옮김, (주)제이펍, 2020 에서 발췌하였습니다.