[ALGORITHMS]문제 09 삽입정렬

문제 09

삽입정렬

리스트 안의 자료를 작은 수부터 큰 수로 배열하는 정렬 알고리즘을 만들어 보세요

1. 삽입정렬로 줄세우기

1. 학생이 열 명 모인 운동장에 선생님이 등장합니다.

2. 선생님은 열 명중에 제일 앞에 있던 승규에게 나와서 줄을 서라고 합니다.

승규가 나갔으니 이제 학생이 아홉명 남았습니다.

3. 이번에는 선생님이 준호에게 키를 맞춰 줄을 서라고 합니다. 준호는 이미 줄을 선 승규보다 자신이 키가 작은 것을 확인하고 승규 앞에 섭니다.

4. 남은 여덟 명 중 이번에는 민성이가 뽑혀 줄을 섭니다. 민성이는 준호보다 크고 승규보다는 작습니다. 그래서 준호와 승규사이에 공간을 만들어 줄을 섭니다(삽입)

5. 마찬가지로 남은 학생을 한 명씩 뽑아 이미 줄을 선 학생 사이사이에 키를 맞춰 끼워 넣는 일을 반복합니다. 마지막 남은 학생까지 뽑아서 줄을 세우면 모든 학생이 제자리에 줄을 서게 됩니다

2. 쉽게 설명한 삽입 정렬 알고리즘

*프로그램이 동작하는 원리

1. 리스트 a에 자료가 남아있다면 -> while a:

2. 남은 자료 중에 맨 앞의 값을 뽑아냅니다. -> value= a.pop(0)

3. 그 값이 result의 어느 위치에 들어가면 적당할지 알아냅니다.

-> ins_idx= find_ins_idx(res, value)

4. 3번 과정에서 찾아낸 위치에 뽑아낸 값을 삽입합니다.

-> res.insert(ins_idx, value)

5. 1번 과정으로 돌아가 자료가 없을때까지 반복합니다.

3. 일반적인 삽입 정렬 알고리즘

-입력 리스트 안에서 직접 위치를 바꿔 정렬하는 삽입 정렬 프로그램을 구현하도록 하겠습니다

4. 알고리즘 분석

삽입정렬 알고리즘 계산 복잡도는 특이한 케이스(입력이 [1,2,3,4,5])일 때에는 O(n)이지만 일반적인 입력일 떄 계산복잡도는 O(n^2)입니다

삽입정렬에 이어 문제 10과 11에서는 병합정렬과 퀵 정렬을 알아볼텐데 병합정렬과 퀵정렬은 삽입정렬과 선택정렬 보다 빠르게 정렬할 수 있는 효과적인 알고리즘입니다.

* 연습문제

9-1 일반적인 삽입 정렬 알고리즘을 사용해서 리스트 [2,4,5,1,3]을 정렬하는 과정을 적어보세요

답:

[2,4,5,1,3]

[1,2,4,5,3]

[1,2,3,4,5]

9-2 문제 9에서 설명한 정렬 알고리즘은 숫자를 작은 수에서 큰 수 순서로 나열하는 오름차순 정렬이었습니다. 이를 큰 수에서 작은 수 순서로 나열하는 내림차순 정렬로 바꾸려면 프로그램의 어느 부분을 바꿔야 할까요?

답: 대소비교

읽어주셔서 감사합니다