[자료구조] Selection Sort(선택정렬), Insersion Sort(삽입정렬)

이번에 소개할 알고리즘은 정렬 알고리즘인 Selection Sort와 Insersion Sort이다.

두 알고리즘은 모두 최악의 경우 O(N²)의 시간복잡도를 갖는 알고리즘이다.

 

Selection Sort란?

Selection Sort는 말 그대로 선택하면서 정렬하는 알고리즘이다.

과정은 아래와 같다.

1. 앞에서부터 순회하면서 가장 큰 수를 발견하면 맨 뒤로 보내고 고정

2. 다시 순회하면서 고정된 범위를 제외하고 가장 큰 수를 발견하면 고정 범위의 앞으로 보내고 고정

3. 1과 2의 방법을 반복하면서 고정범위 == 배열의 크기가 될 때까지 진행

아래는 정렬되는 예시이다.

Selection Sort의 시간복잡도

(n-1) 회 반복 * (각 반복마다 최소 요구되는 상수시간 + 적절한 인덱스를 찾는 시간)

== O(N²)의 시간 복잡도를 갖는다.

Selection Sort의 경우 정렬되어 있는 상태라고 하더라도 가장 큰 수를 찾는 시간이 소요되기 때문에 항상 N²의 시간이 걸린다

 

Selection Sort의 의사코드

SelectionSort(A[0..n-1])
    // 배열 A의 길이를 n이라 가정
    for i = n-1 down to 1 do
        // i까지 정렬이 완료된 상태가 되도록, 0..i 구간에서 최대값을 찾음
        maxIndex ← 0

        for j = 1 to i do
            if A[j] > A[maxIndex] then
                maxIndex ← j
            end if
        end for

        // 찾은 최대값(A[maxIndex])을 현재 i 위치로 교환
        if maxIndex ≠ i then
            swap A[i] and A[maxIndex]
        end if
    end for

    // A[0..n-1]이 오름차순으로 정렬

 

Insersion Sort란?

Insersion Sort는 해당 차례의 요소를 지금까지 정렬해온 배열에서

해당 요소가 들어갈 자리로 삽입하며 정렬해 나가는 알고리즘이다.

과정은 아래와 같다.

1. 앞에서부터 뒤로 진행되며 i번째 요소를 만나면 i-1번째 까지 정렬된 상태의 배열에서 해당 요소의 삽입 위치를 탐색한다.

    * 삽입 위치는 i-1~맨 앞 요소 순서로 탐색한다.

2. 위의 과정을 마지막 요소까지 반복한다.

위 과정을 거치면 이미 지나간 범위의 요소들이 정렬되어있음을 보장하기 때문에 정렬이 완료된다.

Insersion Sort의 시간복잡도

(n개의 element 순회) * (이미 정렬된 i-1 번째 요소에서 i 번째 요소가 들어가야 하는 자리를 찾는데 들어가는 시간)
== O(N²)의 시간복잡도를 갖는다

Insersion Sort의 경우 이미 정렬된 배열의 경우 순회만 진행하기 때문에 best case에는 O(N)의 시간복잡도를 갖는다.

 

Insersion Sort의 의사코드

InsertionSort(A[0..n-1])
    // 배열 A의 길이를 n이라고 가정

    //앞에서부터 뒤로 진행하며 i번째 요소를 처리
    for i = 1 to n-1 do
        key ← A[i]           // 현재 삽입할 값을 key에 저장
        j ← i - 1            // i-1번째 요소부터 삽입 위치를 탐색

        //* 삽입 위치는 i-1번째 요소에서 맨 앞 요소(인덱스 0) 방향으로 탐색
        while j ≥ 0 and A[j] > key do
            A[j + 1] ← A[j]  // key보다 큰 값이 있으면 오른쪽으로 한 칸씩 이동
            j ← j - 1        // 다음 비교를 위해 왼쪽으로 한 칸 이동
        end while

        //* 탐색이 끝난 위치(j+1)가 key의 최종 삽입 위치
        A[j + 1] ← key      // 빈 자리(j+1)에 key를 삽입
    end for

    //위 과정을 마지막 요소(i = n-1)까지 반복하면 A[0..n-1]이 오름차순으로 정렬됨