정렬 알고리즘 비교
개요
•
정말 바쁘게 달려온 정렬 알고리즘 정리… 이제 마지막 장을 남겨 두고 있다.
•
정렬 알고리즘들을 한 눈에 비교하는 시리즈. 반드시 알아야하는 주요한 사항들도 한 번 같이 정리해보도록 한다.
정렬 알고리즘 비교 표
정렬 알고리즘 | 시간 복잡도 (최선) | 시간 복잡도 (평균) | 시간 복잡도 (최악) | 공간 복잡도 | 안정성 | 내부/외부 정렬 |
선택 정렬 (Selection Sort) | O(n^2) | O(n^2) | O(n^2) | O(1) | 비안정 정렬 | 내부 정렬 |
버블 정렬 (Bubble Sort) | O(n) | O(n^2) | O(n^2) | O(1) | 안정 정렬 | 내부 정렬 |
삽입 정렬 (Insertion Sort) | O(n) | O(n^2) | O(n^2) | O(1) | 안정 정렬 | 내부 정렬 |
쉘 정렬 (Shell Sort) | O(n log n) | O(n log^2 n) | O(n log^2 n) | O(1) | 비안정 정렬 | 내부 정렬 |
병합 정렬 (Merge Sort) | O(n log n) | O(n log n) | O(n log n) | O(n) | 안정 정렬 | 외부 정렬 |
퀵 정렬 (Quick Sort) | O(n log n) | O(n log n) | O(n^2) | O(log n) | 비안정 정렬 | 내부 정렬 |
외..외부 정렬?
외부 정렬은 간단하게 생각하면 된다. 메모리 내에서 직접 데이터를 정렬하느냐 마느냐의 여부이다. 다른 알고리즘에 비해서, 안정형이자 배열을 분할하여 정복하는 Merge Sort (합병/병합정렬)은 외부 정렬이 가능하여 큰 데이터를 외부 저장 장치에서 정렬할 때 유용하다고 한다.
다시 표로 돌아와서.
•
주요 차이점:
1.
시간 복잡도:
•
선택 정렬, 버블 정렬, 삽입 정렬은 모두 O(n^2)의 시간 복잡도를 가지고 있어 데이터가 많아질수록 성능이 떨어진다. 그러나 최선의 경우 삽입 정렬과 버블 정렬은 O(n)으로 성능이 좋아진다.
•
쉘 정렬, 병합 정렬, 퀵 정렬은 시간 복잡도에서 더 좋은 성능을 보인다. 특히 병합 정렬과 퀵 정렬은 O(n log n)의 평균 시간 복잡도를 가집니다.
2.
공간 복잡도:
•
선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬은 모두 O(1)의 추가 공간을 사용하여 메모리 효율이 좋다. 즉, 오직 들어온 입력 배열만을 사용한다.
•
병합 정렬은 O(n)의 추가 공간을 사용하므로 상대적으로 공간 사용이 크다.
◦
이는 쪼갠 배열을 붙이는 과정에서 임시 저장공간이 필요하기 때문이다.
3.
안정성:
•
버블 정렬, 삽입 정렬, 병합 정렬은 안정 정렬이므로 동일한 값의 요소들이 입력 순서를 유지합니다.
•
선택 정렬, 쉘 정렬, 퀵 정렬은 비안정 정렬로, 동일한 값의 요소들이 정렬 후 입력 순서가 변경될 수 있다.
4.
내부/외부 정렬:
•
대부분의 알고리즘은 내부 정렬입니다. 즉, 메모리 내에서 직접 데이터를 정렬한다.
•
병합 정렬은 외부 정렬이 가능하여 큰 데이터를 외부 저장 장치에서 정렬할 때 유용하다.
뭣이 안정한데?
안정성에 대해 잠깐만 더 살펴보도록 하자.
알고리즘의 안정성은 정렬 알고리즘이 동일한 값을 가진 요소들의 상대적인 순서를 유지하는지 여부를 나타낸다. 즉, 데이터 내에서 같은 값을 가진 두 요소가 있을 때, 정렬 후에도 그들의 원래 순서가 유지되면 그 알고리즘은 안정적이라고 한다.
하지만 알고리즘을 공부하는 입장에서 보통은 숫자로만 알고리즘을 풀기 때문에 이게 애매한 개념일 수가 있다.
•
예시:
다음과 같은 데이터가 있다고 가정하자.
[(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')]
CSS
복사
여기서 첫 번째 값(정수)이 기준이 되고, 두 번째 값(문자)은 참고용이다. 이 데이터를 정렬할 때 두 개의 값이 같은 경우(예를 들어, (3, 'a')와 (3, 'c')) 원래 순서가 유지된다면 그 정렬 알고리즘은 안정적이다.
만약 정렬 후 결과가:
[(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')]
CSS
복사
이와 같다면 안정적인 정렬이다. 동일한 값 3에 대해 'a'가 'c'보다 먼저 있었고, 정렬 후에도 그 순서가 유지되었기 때문이다.
반면, 결과가:
[(1, 'b'), (2, 'd'), (3, 'c'), (3, 'a')]
CSS
복사
와 같이 나오면, 이것은 비안정적인 정렬이다. 값이 같은 (3, 'a')와 (3, 'c')의 상대적인 순서가 바뀌었기 때문이다.
정렬 알고리즘 끝
•
약 7개의 포스팅으로 정렬 알고리즘의 기초들을 정리해보았다. 각 알고리즘의 특성을 잘 알고 있으면 추후 큰 도움이 되지 않을까 싶다.
Written by Changyu Lee