[CS/알고리즘] 거의 정렬된 List에서 어떤 정렬이 가장 효율적일까?

요약

삽입정렬이 미리 정렬되어있는 자료구조에서 가장 빠른 성능을 가진다.

 

왜?

버블정렬은 시간복잡도가 O(N^2)이고,

퀵, 머지소트는 분할-정복 과정을 거치기 때문에 느리다.

쉘 정렬은 간격이 k라고 했을 때, k가 1이될 때 까지 줄이면서 반복해야 하므로 이미 정렬된 자료구조에서는 삽입정렬보다 빠르지 않다.

 

** 이진 삽입 정렬이 일반적인 삽입정렬보다 더 빠르다고 말할 수 있다.
list내에서 어떤 원소의 위치를 찾을 때, 삽입정렬은 1~n번째 원소를 모두 돌아가면서 보지만,
이진 삽입정렬은 이 과정을 이진탐색으로 진행해서 O(logN)의 복잡도를 가지기 때문이다.

 

** 언어별 기본 제공 sorting 알고리즘
Java : Tim Sort, dual pivot quicksort
Python : Tim Sort
C++ : Quick Sort 변형

 

 

** 각 정렬 방식은 어떤 상황에 적합할까? (뇌피셜)
버블 : 거의 사용되지 않음
삽입 : 거의 정렬되어 있는 list에 대해 사용
합병 : 대부분의 경우에 O(NlogN)의 균일한 시간복잡도가 필요하며, 정렬에 필요한 추가 공간을 감당할 수 있을 때
퀵 : 평균적인 상황에서 최고의 정렬
쉘 : 정렬 중간 과정에서도 각 원소들이 대략적으로 정렬되어 있는 상태이기 때문에, 대략적인 위치만을 빠르게 알고싶을 때 사용
힙 : 힙을 만드는 추가 공간이 있으며, 최솟값, 최댓값에서 가까운 값을 찾고싶을 때 다른 정렬에비해 빠를 것 같다.
기수 : 기수테이블을 만들기 위한 추가 공간이 있으며, 실수보다는 정수들을 빠르게 정렬하고 싶을 때 유용

 

1. Bubble Sort 버블정렬

서로 인접한 원소를 차례로 검사해 나가면서 순서를 바꾸면서 정렬하는 방식이다.

1,2 / 2,3 / 3,4 ... n-1,n 순으로 비교하고 다시 2,3/3,4/... 순으로 비교해나가는 방식이다.

한 번 반복할 때 마다 마지막 한개가 정렬된다.

손쉽게 구현할 수 있지만, 비효율적인 방식이다

SWAP이 MOVE보다 더 복잡하기 때문에 거의 쓰이지 않는다.

시간복잡도 : O(N^2)

 

2. Insert Sort 삽입정렬

k번째 원소를 1~k-1번째의 숫자들과 비교해 적절한 위치에 끼워 넣고, 그 뒤의 자료를 한 칸씩 뒤로 밀어내는 방식이다.

자료구조에 따라 뒤로 밀어내는 과정에 시간이 많이 걸릴 수 있다.

역순으로 정렬되어 있을 경우에 시간이 매우 오래 걸린다.

반면에 이미 정렬되어 있는 자료구조에 하나씩 삽입/삭제하는 경우에는 최고의 정렬 알고리즘이 된다.

시간복잡도 : 최선O(N) / 평균,최악O(N^2)

• 번외 ) 이진 삽입 정렬
  • 새로운 원소가 위치할 곳을 이진 탐색으로 찾는 방식
  • 삽입방식에서는 원소가 위치할 곳을 찾는데 O(N)이 걸린다면, 이진 삽입 정렬을 통해 O(logN) 수준으로 줄여서 조금 더 빠르게 수행할 수 있다.

 

3. Merge Sort 합병정렬 (병합 방식)

여러개의 정렬된 집합을 병합하여 하나의 정렬된 집합으로 만드는 방식이다.

공간복잡도 : 정렬할 원소를 저장할 2n개의 추가 공간 필요

시간복잡도 : O(nlogn)

 

4. Quick Sort 퀵정렬 (교환 방식)

평균적인 상황에서 최고의 정렬이다.

거의 모든 언어에서 기본으로 제공하는 정렬 함수는 퀵정렬 혹은 이를 변형한 알고리즘을 사용한다.

적절한 원소를 피봇으로 정해서, 피봇보다 작은 것을 앞으로, 큰 것을 뒤로 보낸 후 다시 각각에서 피벗을 정해서 공간의 크기가 0이나 1이 될 때 까지 수행한다.

시간복잡도 : O(nlogn) / 최악 O(n^2)

머지 퀵 모두 분할정복 방식이다.

 

5. Shell Sort 쉘정렬

역순에 가까울수록 최악의 시간복잡도를 보이는 삽입정렬의 특징을 보완한 알고리즘이다.

이전의 원소를 모두 비교하고 교환하는 것이 아니라 일정 간격 주기로 띄엄띄엄 검사하며서 교환하면서 타겟 원소의 위치를 대략적으로 잡아주는 방식이다.

이 '간격'을 줄이면서 정렬해나가다보면 정렬기준에 가까워지게 되며, 최종적으로 간격이 1일 때 까지 진행한다면 정렬이 완료된다.

시간 복잡도 : O(N^(1.5))

삽입정렬을 이용하기 때문에, 삽입정렬과 동일한 복잡도O(N^2)를 가지지만, 실험결과 쉘 정렬의 시간 복잡도는 O(N^(1.5))를 따른다고 한다.

 

사진 출처

 

6. Heap Sort 힙정렬

Heap 자료구조를 이용해 정렬하는 방식이다.

Heap : 완전 이진 트리의 일종이며, 우선순위 큐를 위해서 만들어진 자료구조이다. 최댓값/최솟값을 쉽게 추출할 수 있다

사진 출처

내림차순 정렬 : 최대힙, 오름차순 정렬 : 최소힙 을 만들어 이용하면 된다.

정렬해야할 요소들로 힙을 만든 뒤, 힙에서 요소를 하나씩 꺼내서 배열에 순서대로 저장하면 된다.

 

7. Radix Sort 기수정렬

숫자들을 낮은 자리수(일의 자리)부터 비교해서 정렬해나가는 방식이다.

시간복잡도는 낮지만, 기수 테이블을 만들기 위한 공간이 추가로 필요하다.

시간복잡도 : O(dn) d: 숫자의 자리 수

자세한 내용 : https://lktprogrammer.tistory.com/48