1선택 정렬로 줄 세우기

 

자료를 정렬하는 컴퓨터 알고리즘을 살펴보기에 앞서, 운동장에 모인 학생을 키 순서에 맞춰 일렬로 줄 세우는 방법을 한 번 생각해 보겠습니다. 학교생활을 하면서 여러 번 경험해 봤을 법한 상황입니다. 머릿속으로 장면을 떠올려 보면서 다음 방법을 생각해 봅시다.

 

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

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

3 | 이번에는 선생님이 학생 아홉 명 중 키가 가장 작은 성진이를 선택합니다. 선택된 성진이가 불려 나와 민준이 뒤로 줄을 섭니다.

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

 

그림 8-1 선택 정렬

 

‘키 순서로 줄 세우기’는 대표적인 정렬 문제의 예입니다. 왜냐하면, 이 문제는 ‘학생의 키라는 자료 값을 작은 것부터 큰 순서로 나열하라’는 문제와 같은 말이기 때문입니다.