선택 정렬

지난 글: [알고리즘] - 버블 정렬

 

선택 정렬(selection sort)에서는 '수열 중에서 최솟값을 검색해서 왼쪽 끝에 있는 숫자와 교체'하는 작업을 반복한다. 수열 중에서 최솟값을 찾을 때는 선형 탐색을 사용한다.

 

1

6	1	7	8	9	3	5	4	2

여기에서 1부터 9까지 숫자를 정렬하도록 한다. 

 

2

수열을 선형 탐색해서 최솟값을 찾는다.

6	1	7	8	9	3	5	4	2
	--

최솟값 1을 찾았다. 최솟값인 1을 왼쪽 끝에 있는 6과 교체하고 1은 정렬이 끝난 것으로 간주한다. (최솟값이 이미 왼쪽 끝에 있는 경우는 아무런 작업을 하지 않는다.)

1	6	7	8	9	3	5	4	2

1라운드 종료.

 

3

남은 숫자를 선형 탐색해서 최솟값을 찾는다. 이번에는 최솟값 2를 발견했다.

1	6	7	8	9	3	5	4	2
								--

2를 왼쪽에서 두 번째에 있는 6과 교체하고 정렬을 마친다.

1	2	7	8	9	3	5	4	6

 

4

같은 작업을 모든 숫자가 정렬을 마칠 때까지 반복한다.

 

5

정렬을 완료했다.

1	2	3	4	5	6	7	8	9

 

알고리즘 재밌다

 

참고 서적: