[2.2]연습문제 (introduction to algorithms 3rd edition)

2.2-2 

selection sort를 python으로 구현한 코드

import random

def selection_sort(A):
    for i in range(0,len(A)-1):
        min = A[i]
        min_index = i
        for j in range(i, len(A)):
            if A[j]<min:
                min = A[j]
                min_index = j
        A[min_index] = A[i]
        A[i]=min
    return A

a = list(range(0,1000))
random.shuffle(a)
print(a)
print(selection_sort(a))

loop invariant

Initialization : 첫번째 for loop은 i = 0 으로 시작한다. 두번째 for loop에서 j가 0부터 리스트의 마지막원소까지 확인하면서 제일 작은 원소와 index를 찾는다. 0~len(A) 범위 내의 가장작은 값과 A[0]을 교환하면서 첫번째 for loop이 종료된다. 따라서 A[0]은 가장 작은 원소로 정렬된 상태이다.

maintenance : i는 1씩 증가하고 두번째 for loop에서는 증가된 i로 시작해서 마지막 원소로 끝나는 범위 내에서 가장 작은 원소를 찾는다. A[0]~A[i-1] 까지는 가장 작은 원소 순서대로 정렬이 되어 있기때문에 두번째 for loop에서 찾은 값은 A[i-1] 다음으로 큰값이다. 이 값을 A[i]와 교체해주면 A[0]~A[i] 까지 정렬된 상태이다.

Termination : python에서는 리스트 인덱스가 0으로 시작하고 알고리즘 책에서는 1로 시작하기 때문에 조금 햇갈릴 수 있으나 어찌되었든 리스트의 뒤에서 두번째 원소를 마지막으로 첫번재 for loop이 끝난다. 마지막 케이스에서 두번째 for loop은 둘중에 가장 작은 원소를 찾고 이를 마지막에서 두번째 원소의 위치로 둔다. 따라서 n-1 개의 원소를 바꿀 때 까지만 loop을 반복해주면 마지막 원소는 자동으로 가장 큰 원소로 정렬된다. 

running time

insertion sort는 정렬된 n개의 원소가 있는 배열에 n+1번째 원소의 위치를 찾기 때문에 최적의 경우 맨 마지막 원소와 한번 비교하고 끝나게된다 따라서 시간 복잡도가 n이 될 수 있지만. selection sort의 경우는 n+1번째 원소를 나머지 모든 원소와 비교해서 남은 원소중에 가장 작은 원소임을 확인해야 하기 때문에 최적의 경우or 최악의 경우 모두 n^2의 시간 복잡도를 가진다.

2.2-3

평균적으로 n/2개의 값을 조사하면 된다. 최악의 경우는 찾는 값이 없는 경우고 이 때 n개의 값을 찾아야한다. 평균적인 경우나 최악의 경우 모두 n의 복잡도를 가진다.

2.2-4

insertion sort와 selection sort에서 알 수 있듯, maintenance 단계에서 최적의 경우부터 순서대로 확인을 하고 확인이 완료 될 경우 loop invariant를 유지한 채 해당 loop을 종료하고 다음단계로 넘어가도록 설계해야 최적의 경우 좋은 수행시간을 줄일 수 있다.