연습 문제

 

11-1 지금까지 배운 네 가지 정렬 알고리즘 말고도 훨씬 많은 정렬 알고리즘이 있습니다. 그 중 하나인 거품 정렬(Bubble sort)을 줄 서기로 비유하면 다음과 같습니다. 다음 과정을 읽고 리스트 [2, 4, 5, 1, 3]이 정렬되는 과정을 알고리즘으로 적어 보세요.

 

1 | 일단 학생들을 아무렇게나 일렬로 줄을 세웁니다.

2 | 선생님이 맨 앞에서부터 뒤로 이동하면서 이웃한 앞뒤 학생의 키를 서로 비교합니다. 앞에 있는 학생의 키가 바로 뒤에 있는 학생보다 크면 두 학생의 자리를 서로 바꿉니다.

3 | 선생님은 계속 뒤로 이동하면서 이웃한 앞뒤 학생의 키를 비교해서 필요하면 앞뒤 학생의 위치를 서로 바꿉니다.

4 | 모든 학생이 키 순서대로 줄을 설 때까지 이 과정을 반복합니다(줄의 끝까지 확인하는 동안 자리를 바꾼 적이 한 번도 없으면 모든 학생이 순서대로 줄을 선 것입니다).

 

그림 11-4 거품 정렬