[Algorithm] 선택 정렬, 삽입 정렬 알고리즘(Swift 구현)

[Algorithm] 선택 정렬, 삽입 정렬 알고리즘(Swift 구현)

 

 

정렬 알고리즘. 최근 Swift로 프로그래머스 알고리즘 문제를 풀어보고 있던 중, 정렬에 대한 궁금증이 도졌다. Swift의 내장함수 sorted()가 바로 Tim sort 방식으로 정렬을 한다고 하는데, 제대로 이해를 하지 못했다. 그래서 예전에 정렬 알고리즘을 얄팍하게 공부해서 한 번 포스팅 한 적이 있었지만, 이번엔 더 자세하게, 이해가 될 수 있을 정도로 알고리즘을 파헤쳐 보기로 하였다.

 

 

1. 정렬 알고리즘이 필요한 이유?

 

정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것

 

우리가 일상생활에서도 많이 사용하는 알고리즘이다. 어떤 것들을 차례대로 배치해놓아야 일의 순서가 쉬워지는 것들이 있다. 예를 들어, 주방에서 음식을 한다고 할 때, 써야 하는 재료들을 차례대로 정리해놓는다던지, 1교시부터 6교시까지 보아야 할 책들을 차례로 정렬해서 책상 안에 넣어놓는다던지 할 때 사용한다.

 

무엇인가를 더 효율적으로 하기 위해서 우리는 정렬 알고리즘을 사용한다.

 

'효율적'

 

데이터를 효율적으로 활용하기 위해 가장 기본적으로 필요한 것이 '정렬'인 것이다. 정렬을 하고나면 '이진 탐색'이 가능해진다(이진 탐색은 빠르게 데이터의 위치를 찾기 위한 탐색 방법). 데이터를 빠르게 찾기 위해, 아니면 빠르게 삭제하기 위해, 업데이트 하기 위해 정렬을 우리는 사용한다. 10개, 20개가 아니라, 10억개, 20억개의 데이터를 처리한다면 정렬은 더욱더 필요해질 것이다.

 

 

2. 정렬의 방법

 

정렬은 '비교'로부터 시작된다. 이 데이터와 저 데이터를 비교해서 누가 더 숫자가 큰지, 알파벳 또는 한글 순으로 누가 더 위에 있는지를 비교하는 것부터 시작한다. 데이터를 비교한 후 작은 것부터 큰 것 순으로 배치한다던지, 큰 것에서 작은 것순으로 배치한다던지 하는 과정을 거치면 정렬이 되는 것이다.

 

 

그렇다면, 무엇과 무엇을 골라서 비교하고, 위치를 바꿔놓아야 할 까? 라는 의문이 들 것이다. 그리고 어떻게 해야 최소한의 횟수로 정렬을 시행할 수 있는지가 궁금할 것이다. 또한 정렬을 위해 새로운 공간이 필요할 수도 있다. 그 공간을 최소화하면서 시행할 수 있는 방법이 궁금할 것이다.

 

수많은 정렬 알고리즘은 위의 궁금증과 의문들의 여러 가지 답이라고 할 수 있을 것이다. 효율적인 비교, 효율적인 스와프, 효율적인 공간복잡도를 생각하면서 수많은 똑똑한 사람들이 만들어 낸 정렬 알고리즘을 순차적으로 살펴보자...!

 

 

3. 선택 정렬(Selection Sort)

 

1) 정의

배열 내에 원소 중 가장 작은 것을 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 배열 끝까지 반복하는 정렬

 

가장 원시적인 방법으로 매번 n번째 반복 때 인덱스 n - 1번부터 배열 끝까지의 원소 중, 가장 작은 원소를 n - 1번 인덱스로 보내는 정렬이다. 예를 들면 아래와 같다.

 

 

 

2) 설명

 

(1) 정렬의 과정

 

[3, 1, 6, 5] 배열이 있다고 하자.

1번째 반복 때는 0번 인덱스부터 3번 인덱스 수 중 가장 작은 수가 1이다. 그 수와 0번 인덱스에 있는 수를 바꿔준다.

그러면 배열은 [1, 3, 6, 5]가 된다.

2번째 반복 때는 1번 인덱스부터 3번 인덱스 원소 중 가장 작은 수가 3이다. 원소 3과 1번 인덱스에 있는 수를 바꿔준다. 동일한 수이기 때문에 변환은 일어나지 않는다. [1, 3, 6, 5]가 된다.

3번째 반복 때는 2번 인덱스부터 3번 인덱스 원소 중 가장 작은 수가 5이다. 원소 5와 2번 인덱스에 있는 수를 바꿔준다.

그러면 배열은 [1, 3, 5, 6]이 된다.

4번째 반복때는 3번 인덱스부터 3번 인덱스 원소 중 가장 작은 수가 6이다. 자기 자신이기 때문에 변환은 일어나지 않는다.

 

이렇게 되어 [1, 3, 5, 6]을 리턴받게 된다.

 

 

(2) 시간복잡도, 공간복잡도

 

큰 반복을 4번 했지만, 실제로 가장 작은 수를 찾기 위해서 전체 탐색을 한 번 더 해야 한다. 이중 반복문을 활용하는 것과 같으며 시간복잡도는 O(N^2)이다.

 

공간복잡도는 주어진 배열 안에서 Swap을 하면서 정렬을 진행하기 때문에 O(N)이다.

 

 

(3) IDE로 본 정렬과정

0, 1, 2, .... 차례로 정렬이 되는 것을 볼 수 있다.

 

3) 코드

직접 Swift 코드로 구현한 것은 아래와 같다.

func selectionSort() {
    for i in 0 ..< array.count {
        // 가장 작은 원소의 인덱스
        var minIndex = i
        for j in i + 1 ..< array.count {
            if array[minIndex] > array[j] {
                minIndex = j
            }
        }
        let temp = array[i]
        array[i] = array[minIndex]
        array[minIndex] = temp
        
        print(array)
    }
}

 

 

4. 삽입 정렬(Insertion Sort)

 

1) 정의

첫 번째 데이터는 정렬되어 있다고 가정하고, 그 다음 데이터부터 적절한 위치에 '삽입'하여 정렬하는 알고리즘

 

첫 번째 데이터가 정렬되어 있다고 가정하고, 그 다음 데이터와 첫 번째 데이터를 비교하여 앞, 뒤에 배치한다.

세 번째 데이터는 첫 번째, 두 번째 데이터 모두를 비교하여 적절한 위치에 삽입한다.

이런 식으로 데이터를 삽입하여 정렬하는 것이 삽입 정렬이다.

삽입정렬은 정렬이 된 원소는 항상 오름차순 또는 내림차순을 유지하고 있다. 

 

 

2) 설명

(1) IDE로 본 삽입정렬

주어진 배열은 1과 7을 바꾸면 23까지는 정렬되어 있다. 그래서 5번째 반복까지는 아무 변화가 없다.

6번째 반복부터 1을 적절한 위치에 끼워넣는데, 1과 7사이에 끼워넣어진 것이라고 볼 수 있다.

그 다음 반복도 이와 같은 변화를 거치면서 정렬이 이루어진다.

 

 

(2) 시간복잡도, 공간복잡도

 

최악의 경우(역으로 정렬되어 있을 경우) 선택정렬과 마찬가지로, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 즉, O(n^2) 이다.

하지만, 모두 정렬이 되어있는 경우(Optimal)한 경우, 한 번씩 밖에 비교를 안하므로 O(N) 의 시간복잡도를 가지게 된다.

 

또한, 이미 정렬되어 있는 배열에 자료를 하나씩 삽입/제거하는 경우에는, 현실적으로 최고의 정렬 알고리즘이 되는데, 탐색을 제외한 오버헤드가 매우 적기 때문이다.

 

최선의 경우는 O(N) 의 시간복잡도를 갖고, 평균과 최악의 경우 O(N^2) 의 시간복잡도를 갖게 된다.

 

공간복잡도의 경우 주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(N) 이다.

 

 

3) 코드

직접 Swift 코드로 구현한 것은 아래와 같다.

func insertionSort() {
    for i in 1 ..< array.count {
        for j in stride(from: i, to: 0, by: -1) {
            if array[j] < array[j - 1] {
                array.swapAt(j, j - 1)
            } else {
                break
            }
        }
        print(array)
    }
}

 

 

5. 정리

 

가장 기본적인 정렬 알고리즘을 다시 한 번 알아보았다.

다음에는 퀵 정렬과 병합 정렬을 알아볼 것이다.