-
Selection Sort : 정렬할 데이터 N개가 배열 a[ ]에 저장되어 있을 때, 오름차순으로 정렬하려 함.
-0~N-1까지 loop을 돌면서(iterate) a[ ]의 일부에 대해 가장 작은 원소를 찾아 가장 왼쪽으로 보내는 것을 반복
-특히 iteration i때, a[i]~a[N-1] 중 가장 작은 원소를 찾아 a[i]와 위치를 바꿈(swap)
-가장 작은 원소를 찾기 위해서는 a[i]~a[N-1]을 하나씩 차례로 확인함
.
ex) a = {5,1,3,2}
i = 0일 때, {5,1,3,2} i[0]~i[3] 중 최소값: 1을 i[0]으로
=> {1,5,3,2}
i = 1일 때, {1,5,3,2} i[1]~i[3] 중 최소값: 2를 i[1]로
=> {1,2,5,3}
i = 2일 때, {1,2,5,3} i[2]~i[2] 중 최소값: 3을 i[2]로
=> {1,2,3,5}
i = 3일 때, {1,2,3,5} => 정렬 완료 -
Selection Sort 코드
def selectionSort(a):
for i in range(len(a)-1):
min_idx = i
for j in range(i+1,len(a)):
if a[j] < a[min_idx]:
min_idx = j
a[i], a[min_idx] = a[min_idx], a[i]-
Selection Sort의 성능
-비교 횟수 :
iteration i에서는 a[i]를 a[i+1]~a[N-1]과 차례로 비교하므로,
(N-1)-(i+1)+1 => N-1-i회 비교
i = 0 ~ N-2까지 진행하므로,
총 비교 횟수는 (N-1)+(N-2)+...+1 = (N-1)N/2 = ~N^2/2
=> 입력 데이터가 달라지더라도 변하지 않음.-swap 횟수 :
매 iteration마다 최솟값을 찾은 후 이 값을 a[i]와 swap하므로,
N에 비례한 횟수의 swap 수행 -
Insertion Sort
-Iteration i 때 a[i]를 왼쪽의 원소와 swap해 가는데, 특히 그보다 크지 않은 원소가 나오기 직전까지 swap
-그 결과, a[0]~a[i]가 정렬된 상태가 됨
.
ex) a = {5,1,3,2}
i = 0일 때, {5,1,3,2} a[0] = 5
i = 1일 때, {5,1,3,2} a[1] = 1, 5 > 1이므로 1과 5 swap
i = 2일 때, {1,5,3,2} a[2] = 3, 5 > 3이므로 3과 5 swap, 1 < 3이므로 swap X
i = 3일 때, {1,3,5,2} a[3] = 2, 5 > 2이므로 2와 5 swap, 3 > 2이므로 2와 3 swap, 1 < 2이므로 swap X
=> {1,2,3,5} (a[0]~a[3]이 정렬된 상태가 됨)
*매 iteration마다 정렬된 상태인 a[0]~a[i-1]에 새로운 한 원소 a[i]를 적절한 위치에 추가(insertion)하는 방식 => Insertion Sort
- Insertion Sort 코드
def insertionSort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j -= 1
a[j+1] = key- 입력 데이터의 상태에 따른 Insertion Sort의 성능 비교
-best case (이미 정렬된 상태, 원소 이동 필요 X) :
대소 비교 횟수 : N-1, swap 횟수 : 0
-worst case (반대로 정렬된 상태, 각 원소를 왼쪽 끝까지 이동해야 함) :
대소 비교 횟수 : ~N^2/2, swap 횟수 : ~N^2/2
-average case (각 원소를 절반 정도 이동시켜야 하는 상태) :
대소 비교 횟수 : ~N^2/4, swap 횟수 : ~N^2/4
*Insertion Sort의 수행 속도는 ~N^2, 입력이 거의 정렬된 경우(partially ordered)라면, ~N번의 비교, swap만 하면 되므로 다른 정렬 방법보다 유리함.
- 정렬은 대소 관계 비교 및 위치 변경을 수행함.
- 대소 관계가 명확하지 않은 객체 정렬 시, 필요한 대소 관계를 규칙에 따라 정의해야 함.
- Year, Month, Day 3개 필드로 이루어진 날짜 객체의 대소 관계를 정의한 예
ex) (Year -> Month -> Day 순으로 비교)
if a.year < b.year:
a < b
elif a.year > b.year:
a > b
else:
if a.month < b.month:
a < b
elif a.month > b.month:
a > b
else:
if a.day < b.day:
a < b
elif a.day > b.day:
a > b
else:
a == b #year, month, day가 모두 같은 경우-
대소 관계 정의 시 지켜야 할 규칙 (Total Order)
-Anti-Symmetry: a<=b이고 b<=a라면, a==b여야 한다.
-Transitivity: a<=b이고 b<=c라면, a<=c이다.
-Totality: a<b이거나 a>b이거나 a==b이다. (셋 중 하나는 반드시 참이어야 함)위 규칙을 따르는 예: 정수, 실수, 알파벳, 시간, 날짜 간의 대소 관계
Q. 이미 정렬된 입력 데이터를 받았을 때, Selection Sort는 몇 번의 대소 비교를 하는가?
A. ~N^2 (입력 데이터가 이미 정렬되었더라도, 비교 횟수는 항상 같음)
Q. Insertion Sort는 이미 정렬된 입력 데이터에 대해서는 몇 번의 대소 비교를 하는가?
A. ~N (iteration 0을 제외한 나머지 N-1번의 iteration에서는 a[i] 바로 왼쪽의 원소와 한 번만 비교한 후 더 이상 swap할 필요 없음을 판단하게 되므로, 총 N-1번의 비교와 0번의 swap을 함.)
Q. 아래는 입력 데이터를 정렬해가는 과정을 보여준다. 어떤 정렬 방법을 사용했는가?
-[7,2,4,1,9,0]
-[2,7,4,1,9,0]
-[2,4,7,1,9,0]
-[1,2,4,7,9,0]
-[1,2,4,7,9,0]
-[0,1,2,4,7,9]
A. Insertion Sort
Q. 아래는 입력 데이터를 정렬해가는 과정을 보여준다. 어떤 정렬 방법을 사용했는가?
-[7,2,4,1,9,0]
-[0,2,4,1,9,7]
-[0,1,4,2,9,7]
-[0,1,2,4,9,7]
-[0,1,2,4,9,7]
-[0,1,2,4,7,9]
A. Selection Sort
Q. 아래와 같은 대소 관계를 정의했다. 이 관계는 total order를 만족하는가?
if a < (b-ε): a < b elif a > (b+ε): a > b else: a == bA. No. Transitivity를 어긴다.
예시: ε=1.0, a=3.1, b=4.0, c=4.9라 할 때, a==b이고, a==c인데, a < c임.
풀이)
a와 b의 차이 = 0.9, b와 c의 차이 = 0.9
a와 c의 차이는 1.8 => 오차범위 보다 큼.
a=c 아님. (transitivity 위배)
