[ALGORITHMS]문제 08 선택정렬

문제 08

선택정렬

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

문제: 리스트 안에 있는 자료를 순서대로 배열하기

입력: 정렬할 리스트(예: [35,9,2,85,17])

출력: 순서대로 정렬된 리스트(예: [2,9,17,35,85])

선택정렬 -> 문제 08

삽입정렬 -> 문제 09

병합정렬 -> 문제 10

퀵 정렬  -> 문제 11

거품정렬 -> 연습 문제 11-1

이렇게 5가지 정렬을 다룰 예정입니다

1. 선택 정렬로 줄세우기

운동장에 모인 학생을 키 순서에 맞춰 일렬로 줄 세우는 방법을 한 번 생각해 보겠습니다.

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

2. 선생님은 학생들을 둘러보며 키가 가장 작은 사람을 찾습니다. 키가 가장 작은 학생으로 '선택'된 민준이가 불려 나와 맨 앞에 섭니다. 민준이가 나갔으므로 이제 학생은 아홉명 남았습니다

3. 이번에는 선생님이 학생 아홉 명 중 키가 가장 작은 성진이를 선택합니다.

선택된 성진이가 불려나와 민준이 뒤로 줄을 섭니다.

4. 이처럼 남아 있는 학생 중에서 키가 가장 작은 학생을 한명씩 뽑아 줄을 세우는 과정을 반복하면 모든 학생이 키 순서에 맞춰 줄을 서게 됩니다.

- 쉽게 설명한 정렬 알고리즘: 정렬 원리를 이해하기 위한 참고용 프로그램

- 일반적인 정렬 알고리즘: 정렬 알고리즘을 정식으로 구현한 프로그램

쉽게 설명한 정렬 알고리즘으로 각 정렬의 원리를 완전히 이해하고나서 

이어지는 일반적인 정렬 알고리즘 프로그램으로 각 정렬의 원리를 복습합니다.

2. 쉽게 설명한 선택 정렬 알고리즘

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

2. 남은 자료 중에서 최솟값의 위치를 찾아냅니다 -> min_idx= find_min_idx(a)

3. 찾은 최솟값을 리스트 a에서 빼내어 value에 저장합니다. -> value를 result 리스트의 맨 끝에 추가합니다. -> result.append(value)

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

3. 일반적인 선택 정렬 알고리즘

일반적인 선택 알고리즘은 주어진 리스트 a안에서 직접 자료의 위치를 바꾸면서 정렬시키는 프로그램입니다

4. 알고리즘 분석

선택 정렬의 비교 방법은 문제 3의 동명이인 찾기에서 살펴본, 리스트 안의 자료를 한 번씩 비교하는 방법과 거의 같습니다. 따라서 이 알고리즘은 비교를 총 n(n-1)/2번 해야 하는 계산 복잡도가 O(n^2)인 알고리즘입니다.

*연습문제

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

답: 

[1,4,5,2,3]

[1,2,5,4,3]

[1,2,4,5,3]

[1,2,3,4,5]

8-2 오름차순 정렬 말고 내림차순의 정렬로 바꾸려면 프로그램의 어느부분을 바꿔야 할까요?

답 : 대소부분

읽어주셔서 감사합니다