10-2 (정렬 알고리즘 알아보기)

선택 정렬: 리스트에서 가장 작은 숫자를 선택해서 앞쪽으로 옮기는 방법. 전체 숫자들은 아직 정렬되지 않은 오른쪽 리스트와 정렬이 완료된 왼쪽 리스트로 나뉨.

맨 처음에는 모든 숫자가 오른쪽 리스트에 들어있고 그 중 가장 작은 숫자를 선택하여 왼쪽 리스트의 맨 뒤로 이동하는 작업을 반복하는 것임.

선택정렬의 매커니즘

 

ex)

왼쪽 리스트 (정렬O)	오른쪽 리스트 (정렬X)	설명
[ ]	[5,3,8,4,9,1,6,2,7]	초기상태
[1]	[5,3,8,4,9,6,2,7]	1 선택 및 이동
[1,2]	[5,3,8,4,9,6,7]	2 선택 및 이동
...	...	...
[1,2,3,4,5,6,7,8,9]	[ ]	9 선택 및 이동

 

---

 

삽입정렬: 카드를 정렬하는 방법과 유사함. 손 안에 정렬된 카드가 있고, 카드를 추가로 한 장씩 더 받을 때 마다 그 카드를 순서대로 끼워 넣는 것임. 삽입 후 전체 카드는 정렬되어 있어야 함. 모든 과정 후 새로 받는 모든 카드에 대해 수행하면 전체 카드가 정렬됨.

정렬이 안 된 부분의 숫자를 하나씩 정렬된 부분의 적절한 위치를 찾아 끼워 넣는 과정을 반복한다.

복잡도의 경우 입력 자료의 구성에 따라 달라지고, 입력 자료가 이미 정렬되어 있는 겨우는 가장 빠르다. 이 경우에는 시간 복잡도는 O(n)이다.

최악의 경우는 입력 자료가 역으로 정렬된 경우로 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동해야 함. 그래서 O(n^2)이 걸린다.

삽입정렬의 매커니즘

 

---

 

버블정렬: 인접한 2개의 레코드를 비교하여 크기가 순서대로가 아니면 서로 교환하는 방법을 사용한다. 비교-교환 과정은 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이 과정은 더 이상 교환이 일어나지 않을 때까지 계속된다.

(이 과정이 물 속의 거품이 보글보글 떠오르는 것과 유사하여 버블정렬이라 명명됨.)

버블정렬의 매커니즘