Swift로 알아보는 정렬알고리즘! 시간복잡도와 공간복잡도

Intro

이번 주제의 선택 이유는 면접때 질문을 받았다.

스위프트로 정렬알고리즘을 구현했을때의 시간복잡도와 공간복잡도가 어떻게 되는지?

알고리즘 준비를 안하고있던 나는 답이 생각나지 않았다.

우선 정렬알고리즘에 대해 알아보기 전에 빅오 표기법(big-O notation)에 대해 알아보자!

빅오 표기법 (big-O notation) 이란?

알고리즘 성능을 수학적으로 표기해주는 표기법이다.

알고리즘의 실행시간보다는 데이터나 사용자 증가률에 따른 알고리즘 성능을 예측하는게 목표이므로 중요하지 않은 부분인 상수와 같은 숫자는 모두 제거해서 계산한다.

즉 빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.

여기서 측정되는 복잡성에는 시간 복잡도와 공간 복잡도가 있다.

시간 복잡도

시간 복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.

따라서 시간 복잡도는 프로세스가 수행해야하는 연산을 수치화한 것이라고 볼 수 있다.

컴퓨터 성능에 따라 실행 시간은 달라질 수 있으므로 실제 실행 시간보다는 명령문의 실행 빈도수를 계산하여 실행 시간을 구하게 된다.

공간 복잡도

공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.

시간 복잡도 vs 공간 복잡도

시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.

시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 판단할 때는 시간 복잡도를 위주로 판단한다.

빅오 표기법의 특징

상수항 무시
빅오 표기법은 n이 충분히 크다고 가정하고 있고, 알고리즘의 효율성은 n의 크기에 영향을 받으므로 상수항과 같은 사소한 부분은 무시간다.
-> O(2n)은 O(n)으로 간주
영향력 없는 항 무시
빅오 표기법은 n의 크기에 영향을 받으므로 가장 영향력이 큰 항 이외에 영향력이 없는 항은 무시한다.
-> O(n^2 + 2n + 1) 은 O(n^2)로 간주

기본적인 정렬 알고리즘

그럼 정렬 알고리즘은 뭘까?

각 배열에서 값을 오름차순, 내림차순 등으로 정렬할 수 있는 알고리즘을 말한다.

사실 sort() 를 사용하면 가장 간단하지만 우리는 개발자니까 알아야겠죠?

버블정렬(Bubble sort)

전공 시간에 가장 먼저봤던 알고리즘 관련 영상이다.

버블정렬은 쉽게 말해서

배열의 처음부터 끝까지 인접한 두 원소를 비교하고 바꿔주는 방식이다.

동영상의 예제처럼 배열을 만들어서 구현해보자!

구현 코드

import Foundation

func bubbleSort(_ array: inout [Int]) {
    for i in 0..<array.count {
        for j in 0..<array.count - (i + 1) {
            if(array[j] > array[j + 1]) {
                array.swapAt(j, j + 1)
            }
        }
    }
}

var array = [3, 0, 1, 8, 7, 2, 5, 4, 6, 9]
bubbleSort(&array)

현재 요소와 다음 요소 비교 후 현재 요소의 숫자가 더 크면 다음 요소와 바꿔준다.
for문에 한번 끝나면 요소 하나의 최종위치가 확정된다.
1, 2 번을 배열의 길이 - 1 까지 반복해준다.

복잡도

시간 복잡도 : n번 loop가 중첩되어 있기 때문에 O(n^2)
공간 복잡도 : 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)

선택정렬(Selection Sort)

선택정렬은 쉽게 말해서

배열의 최소값과 배열의 첫번째 요소를 비교해서 교체한 후, 맨 처음 위치를 제외하고 다시 최소값을 찾아서 반복한다.

전공 시간에 가장 먼저봤던 알고리즘 관련 영상이다.

구현 코드

import Foundation

func selectionSort(_ array: inout [Int]) {
    var min: Int = 0

    for i in 0..<array.count {
        min = i
        for j in i + 1..<array.count {
            if(array[j] < array[min]) {
                min = j
            }
        }
        array.swapAt(min, i)
    }
}

var array = [3, 0, 1, 8, 7, 2, 4, 9, 6]
selectionSort(&array)

주어진 배열에서 최소 값을 찾는다
그 값을 맨 앞에 위치한 값과 바꾼다
맨 처음 위치를 뺀 나머지 데이터를 같은 방법으로 교체한다.

복잡도

시간 복잡도 : n번 loop가 중첩되어 있기 때문에 O(n^2)
공간 복잡도 : 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)

삽입정렬(Insertion Sort)

삽입정렬은 쉽게 말해서

배열의 2번째 원소부터 시작해서 그 앞의 원소들과 비교해서 순서에 맞는 취에서 삽입하는 정렬이다

구현 코드

import Foundation

func insertionSort(_ array: inout [Int]) {
    for index in 1..<array.count {
        var currentIndex = index
        while currentIndex > 0 && array[currentIndex] < array[currentIndex - 1] {
            array.swapAt(currentIndex - 1, currentIndex)
            currentIndex -= 1
        }
    }
}

var array = [3, 0, 1, 8, 7, 2, 5, 4, 9, 6]
insertionSort(&array)

반복문에서 현재 index를 부여 받는다.
반복문 조건에 현재 index가 0이 아니고, 현재 index의 요소가 현재 index 왼쪽에 있는 요소와 대소 비교 후 왼쪽에 위치한 요소가 더 크다면 위치를 바꿔주고 현재 index를 index - 1 로 업데이트 하여 배열의 왼쪽으로 이동한다.
만약 2번 조건을 충족하지 않으면 이미 정렬된 상태라 판정하고 반복문을 순회하지 않는다.

복잡도

시간 복잡도 : n번 loop가 중첩되어 있기 때문에 O(n^2)
공간 복잡도 : 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)

퀵정렬(Quick Sort)

퀵정렬은 쉽게 말해서

배열의 가운데서 하나의 원소를 고른다(pivot)
피벗 앞에는 피벗보다 값이 작은 모든 우너소들이 오고 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 나눈다.

분할된 두 개의 배열에 대해서 재귀적으로 이 과정을 반복한다.

구현 코드

import Foundation

func quickSort(array: [Int]) -> [Int] {
    guard let first = array.first, array.count > 1 else { return array }

    let pivot = first
    let left = array.filter { $0 < pivot }
    let right = array.filter { $0 > pivot }

    return quickSort(array: left) + [pivot] + quickSort(array: right)
}

배열에서 pivot을 정하고 배열을 작은 왼쪽과 큰 오른쪽으로 나눔
왼쪽에 대해서 재귀적으로 동일하게 반복
오른쪽에 대해서 재귀적으로 동일하게 반복
마지막에 합쳐줌

복잡도

시간 복잡도 : 우선 분할을 할 때 N개를 가지고 나눠야 하므로 logn, 합쳐치는 과정에서 모든 숫자를 비교하여 더 작은 숫자로 합치기 때문에 n, O(nlogn)
공간 복잡도 : 주어진 배열 안에서 swap을 통해 정렬이 수행되므로 O(n)

합병정렬(Merge Sort)

[##Image|kage@br8Lly/btsG11KlPPy/3WWhUdOxmXdAVAatEIYh60/img.png|CDM|1.3|{"originWidth":884,"originHeight":733,"style":"alignCenter"}##]

합병정렬은 쉽게 말해서

배열을 두개로 분할하여 정렬 한 후 이를 합치는 방법이다.

구현 코드

import Foundation

func mergeSort(unsorted: [Int]) -> [Int] {
    if unsorted.count <= 1 {
      return unsorted
    }
    let centerIndex = unsorted.count / 2
    let left = Array(unsorted[0..<centerIndex])
    let right = Array(unsorted[centerIndex..<unsorted.count])
    return merge(left: mergeSort(unsorted: left), right: mergeSort(unsorted: right))
}

func merge(left: [Int], right: [Int]) -> [Int] {
    var result: [Int] = []
    var leftIndex = 0
    var rightIndex = 0

    while leftIndex < left.count && rightIndex < right.count {
      if left[leftIndex] < right[rightIndex] {
        result.append(left[leftIndex])
        leftIndex += 1
      } else {
        result.append(right[rightIndex])
        rightIndex += 1
      }
    }

    if leftIndex == left.count {
      result += Array(right[rightIndex..<right.count])
    } else {
      result += Array(left[leftIndex..<left.count])
    }
    return result
}

반복문에서 현재 index를 부여 받는다.
반복문 조건에 현재 index가 0이 아니고, 현재 index의 요소가 현재 index 왼쪽에 있는 요소와 대소 비교 후 왼쪽에 위치한 요소가 더 크다면 위치를 바꿔주고 현재 index를 index - 1 로 업데이트 하여 배열의 왼쪽으로 이동한다.
만약 2번 조건을 충족하지 않으면 이미 정렬된 상태라 판정하고 반복문을 순회하지 않는다.

복잡도

시간 복잡도 : 우선 분할을 할 때 N개를 가지고 1개 씩 남을때 까지 나눠야 하므로 logn, 합쳐치는 과정에서 모든 숫자를 비교하여 더 작은 숫자로 합치기 때문에 n, O(nlogn)
공간 복잡도 : 주어진 배열과 병할할 곳의 새로운 배열을 만들어 줘야 하므로 O(2n)

4T2F / ThinkBig