KRAFTON JUNGLE/JUNGLE TIL
크래프톤 정글 6기 TIL - Day 9| Quick Sort
브이담곰
2024. 7. 10. 02:08
오늘은 일기를 생략하겠다 너무 졸립다..안뇽
Quick Sort
퀵 솔트는 매 단계마다 Pivot이라는 이름이 붙은 원소 하나를 차례로 보내는 정렬법이다.
장점
1. 추가적인 공간이 필요하지 않다.
2. 배열 안에서의 자리 바꿈으로 처리한다. → Cache Hit 비율이 높다! (속도가 빠르다)
In Place Sort
원소위치를 잘 바꿔주면 되기 떄문에 추가적인 공간이 필요 없다.
정렬 과정
시간 복잡도
평균 : O(N LgN)
최악: O(N^2)
Quick Sort VS Merge Sort
| Merge Sort | Quick Sort | |
| 시간복잡도 | O(NlgN) | 평균 O(NlogN) 최악 O(N^2) 평균적으로 Merge Sort 보다 빠르다. |
| 추가적으로 필요한 공간(overhead) | O(N) | O(1) |
| Stable Sort 여부 | O | X |