일단 시간복잡도에 대해 이해하기 위해 이 글을 한번 정독하면 좋다.
네부캠을 준비하면서 정렬 알고리즘의 시간복잡도에 관한 문제가 몇 개 나왔는데 기존에 알고리즘들의 상한선은 알고 있었지만, 하한선에 대해서는 생각하지 않았기 때문에 정리해본다.
대표적인 정렬 알고리즘 몇 가지만 추려서 정리했다.
선택 정렬(Selection Sort)
선택 정렬은 주어진 배열에서 가장 작은 값을 찾아 첫 번째 원소와 교환한 후, 그 다음으로 작은 값을 두 번째 원소와 교환하는 방식을 반복하여 정렬을 수행한다.
시간 복잡도
선택 정렬의 시간 복잡도는 O(n^2)이며 최선, 평균, 최악의 경우 모두 동일하다.
모두 정렬된 배열이어도 배열의 길이만큼 배열의 처음부터 끝까지 순회해야 하기 때문이다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.
삽입 정렬(Insertion Sort)
삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분에 적절한 위치에 삽입하는 방식으로 정렬을 수행한다.
시간 복잡도
선택 정렬의 시간 복잡도는 O(n^2)이며 최악과 평균은 동일하다. 하지만, 모두 정렬이 되어 있는 경우, 한 번씩 밖에 비교를 안하므로 최선의 경우 O(n)의 시간 복잡도를 가지게 된다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.
선택 정렬과 삽입 정렬
삽입 정렬과 선택 정렬은 k번째 반복 이후, 첫 번째 k 요소가 정렬된 순서로 나온다는 점에서 유사하다. 하지만, 선택 정렬은 k+1번째 요소를 찾기 위해 나머지 모든 요소들을 탐색하지만 삽입 정렬은 k+1번째 요소를 배치하는 데 필요한 만큼의 요소만 탐색하기 때문에 월씬 효율적으로 실행된다는 차이가 있다.
버블 정렬(Bubble Sort)
버블 정렬은 인접한 두 원소를 비교하고 필요에 따라 위치를 교환하는 방식으로 정렬을 수행한다.
시간 복잡도
버블 정렬은 정렬이 돼있던 안돼있던, 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.
퀵 정렬(Quick Sort)
퀵 정렬은 분할 정복 방식을 사용하여 배열을 피벗(pivot)을 기준으로 두 부분으로 나눈 후 각 부분을 재귀적으로 정렬한다.
데이터 중 임의의 기준값을 정해서 두 부분 집합으로 나눈다. 이때의 기준 값을 피벗(Pivot)이라고 하고 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값을 배치하고 더 이상 집합을 나눌 수 없을 때까지 재귀적으로 실행된다.
시간 복잡도
퀵 정렬의 시간 복잡도는 O(n log n)이며 최선, 평균은 동일하고 최악의 경우 O(n^2)이다.
삽입 정렬과는 반대로 퀵 정렬은 이미 정렬된 데이터라면 매우 비효율적으로 작용한다.
공간 복잡도
주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n)이다.
병합 정렬(Merge Sort)
병합 정렬은 분할 정복(Divide and Conquer) 방식을 사용하여 배열을 반으로 나눈 후 각 부분을 재귀적으로 정렬하고, 나중에 병합하여 정렬된 배열을 생성한다.
비교 기반 알고리즘으로 "분할, 정렬, 병합"순으로 진행되는데 데이터 배열을 2개 이상의 부분 배열로 분할하고 부분 배열에서 정렬을 한 뒤 결합하여 다시 정렬을 진행한다. 데이터 배열 전체가 다시 결합되고 정렬되면서 마친다.
병합 정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList 정렬이 필요할 때 사용하면 효율적이다.
시간 복잡도
병합 정렬의 시간 복잡도는 O(n log n)이며, 최선, 평균, 최악의 경우 모두 동일하다.
데이터를 정확히 반으로 나누고 정렬하기 때문에 항상 일정한 시간 복잡도를 유지하므로 퀵 정렬의 한계점을 보완할 수 있는 장점이 있지만 다른 알고리즘과 비교했을 때 O(n) 수준의 메모리가 추가로 필요하다는 단점이 있다.
퀵 소트와의 차이점
-
퀵 정렬: 우선 피벗을 통해 정렬(partition) -> 영역을 쪼갬(quickSort)
-
병합 정렬: 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) -> 정렬(merge)
힙 정렬
힙 정렬은 힙 자료구조를 사용하여 정렬을 수행하는 방식으로, 주어진 배열을 최대 힙 또는 최소 힙으로 구성한 후 힙에서 원소를 하나씩 꺼내 정렬한다.
시간 복잡도
힙 정렬의 시간 복잡도는 O(n log n)이며, 최선, 평균, 최악의 경우 모두 동일하다.
완전 이진트리를 사용한다.
시간복잡도 비교
참고
정렬 알고리즘 특징/종류/시간 복잡도 [ 선택, 삽입, 버블, 합병, 힙, 퀵, 기수 ]
Tech Interview [Algorithm]
