Algorithm - sorting - insertion/selection/exchange sort

Bomin Seo·2022년 8월 4일

insertion sort

이미 정렬된 배열에 항목을 끼워넣음으로써 정렬하는 알고리즘

pseudo code

python

def insertion_sort(values):
    numvalues = len(values)
    count = 0
    while count < numvalues:
        finished = False
        current = count
        moretosearch = current != 0
        while moretosearch and not finished:
            if values[current] < values[current - 1]:
                temp = values[current]
                values[current] = values[current - 1]
                values[current - 1] = temp
                current -= 1
                moretosearch = current != 0
            else:
                finished = True
        count += 1

시간복잡도 분석 - 최악의 경우

단위 연산 : S[j]와 x를 비교하는 횟수
최악의 경우에는 i가 주어졌을 때 while루프에서 최대한 i-1번의 비교가 이루어진다.
따라서 최대 비교 횟수를 가지는 최악의 경우 시간복잡도는

시간복잡도 분석 - 평균의 경우

단위 연산 : S[j]와 x를 비교하는 횟수
i가 주어졌을 때 x가 삽입될 수 있는 장소는 i개가 있다.
x를 삽입하는데 필요한 비교 횟수는
따라서 정렬하는데 필요한 평균 비교 횟수는

공간복잡도 분석

in-place sorting 알고리즘이다 - 저장장소가 추가로 필요하지 않다.

레코드 지정 횟수 기준으로의 시간복잡도 분석

최악의 경우
평균의 경우

Selection sort

정렬된 부분과 정렬되지 않은 부분으로 나눈다.
정렬되지 않은 부분에서 가장 작은 값을 정렬되지 않은 부분의 가장 왼쪽 요소와 swap함으로써 정렬한다.

pseudo code

python

def selection_sort(values):
    endIndex = len(values) - 1
    current = 0
    while current < endIndex:
        minval = min(values[current:])
        minindex = values.index(minval, current)
        temp = values[current]
        values[current] = values[minindex]
        values[minindex] = temp
        current += 1

시간복잡도 분석

단위연산 : 비교하는 횟수
모든 경우 시간복잡도 분석 : i가 1일때 비교 횟수는 n-1, i가 2일 때 비교횟수는 n-2, ... i가 n-1일 때 비교횟수는 1이 된다.

단위연산 : 지정하는 횟수
1번 교환함에 있어 3번의 지정이 발생하므로 T(n) = 3(n-1)

Exchange sort

순차적으로 뒤의 부분과 비교하여 가장 작은 값과 swap함으로써 정렬한다.

pseudo code

python

def exchange_sort(S):
    n = len(S)
    for i in range(n-1):
        for j in range(i+1,n):
            if S[i] > S[j]:
                S[i], S[j] = S[j], S[i]
    return S


exchange_sort(S)
print("정렬된 리스트 : ", S)