1) 퀵정렬
- 피봇을 기준으로 해서(위치는 자유이나, 보통 맨 앞의 요소 혹은 중간 요소로 잡는다), 왼쪽과 오른쪽을 피봇과 비교하면서 위치를 이동시키고, 왼쪽과 오른쪽이 역전되었을 때, 분할하여 재귀적으로 정렬을 수행한다.
- 장점 : 평균 실행시간이 다른 알고리즘보다 빠르다. ('살아있는 전설'이라고 한다..)
- 단점 : 피봇에 따라서 성능차이가 심하다
- 시간복잡도 : 피봇이 중간에 가까운 값을 찾을 수록 성능이 좋다. → 최악 O(n^2) / 평균 O(NlogN)
⭐ 왜 퀵정렬이 많이 사용될까? ⭐
퀵소트는 평균적으로 가장 빠르고 효율적인 정렬 알고리즘이다.
이는 다음과 같은 이유 때문이라고 한다.1. 분할 정복 알고리즘의 사용
- 퀵소트는 분할 정복 알고리즘을 사용하여 작동한다.
- 이는 큰 문제를 작은 문제로 분할하여 해결하며, 이 작은 문제는 더 이상 분할할 수 없을 정도로 작아질 때까지 작업을 반복한다.
- 이를 통해 큰 문제를 해결할 수 있으며, 더 효율적인 알고리즘을 만들 수 있다.2. 메모리 절약
- 퀵소트는 피벗을 중심으로 분할하여 정렬한다.
- 이는 데이터를 복사하거나 새로운 배열을 만드는 등의 메모리 사용을 최소화할 수 있다.
- 이렇게 메모리를 절약하면 더 빠르고 효율적인 알고리즘을 만들 수 있다.3. 데이터의 무작위성
- 퀵소트는 데이터가 무작위로 분포되어 있을 때 가장 효율적이다.
- 이는 데이터를 임의로 선택하여 분할하기 때문에, 더욱 효율적인 알고리즘이 가능하다.
2) 삽입정렬
- 뒤에서부터 하나씩 삽입될 위치를 찾고, 해당 위치에서 뒤로 미뤄 삽입하여 정렬하는 방법
- 장점 : 시간복잡도 최선일 때는 O(n) → 이미 정렬되어 있을 때
- 단점 : 시간복잡도 최악일 때는 O(n^2)
3) 병합정렬
- 분할정복 → 알고리즘 디자인 기법
- 분할보다는 병합 과정에서 정렬이 이뤄짐
- 퀵정렬과 달리, 기준값을 두지 않고 반으로 계속 나누고 나중에 병합만 하면 된다.
- 장점 : 데이터 분포의 영향을 덜 받음
- 단덤 : 임시 배열이 필요
- 시간복잡도 : O(NlogN)
4) 힙정렬
- 이진트리 : 루트 노드 / 리프 노드
- 완전이진트리 : 중간에 비어 있지 않고 빽빽하게 차 있음(왼쪽부터 채워짐)
- 힙 → 최대값, 최소값 찾아내기 위해 완전 이진 트리 이용
- 힙 가장 위쪽에 있는 걸 빼서 맨 뒤로 보내주고 (값 교환) → 히피파이(’힙’의 조건을 충족) 해 주고 → 다시 위쪽에 있는 걸 빼서 그 다음 뒤로 보내주고 (값 교환) .. 반복
- 대신 뒤에 점차적으로 검사한 부분은 더 이상 들여다 보지 않는다.
- 시간복잡도 : Heapify (높이만큼만 하면 됨) logN * n (전체 노드) ⇒ NlogN
추가로, 잘 사용하지는 않지만 기본적인 정렬 알고리즘으로 버블과 선택 정렬이 있다.
5) 버블 정렬
- 앞 혹은 뒤에서부터 두 개씩 비교하면서, 원소 하나를 최종 위치로 정렬하는 방법
- 장점 : 구현이 간단함
- 단점 : 시간복잡도가 항상 O(n^2)이 나옴 (최선 O(n)이나, 그런 경우는 거의 없기에)
- 시간복잡도 : O(n^2)
6) 선택정렬
- 인덱스 1부터 n-1까지 이동하면서, 최솟값을 찾아 순차적인 인덱스에 저장하는 방법
- 장점 : 버블 정렬에 비해서는 효과적임(자료 이동 횟수가 제한되어 있다.)
- 단점 : 불안정성
- 시간복잡도 : O(n^2)
💡 안정적인(stable한) 알고리즘이란,
정렬되더라도, 애초에 값이 같은 원소는 순서가 바뀌지 않는 것. (즉, 값이 같은 원소는 정렬한 이후에도 순서가 바뀌지 않는 것)
💡 정렬 알고리즘 선택 기준
1. 안정성
- 안정성 O : 버블/삽입/병합
- 안정성 X : 선택/퀵(안정판이 존재는 함)/힙
※ 서로 이웃하는 원소를 교환한다면 안정성이 있다고 보고, 그렇지 않다면 없다고 보는 것 같다.
2. 공간복잡도
- 1 : 버블/선택/삽입/힙
- n : 병합
- logn : 퀵
그 외에도 지역성(캐시), 키 값들의 분포 상태, 데이터의 양 등등 상황에 맞게 선택할 수 있다.
하루살이 개발자