크래프톤 정글 6기 TIL - Day 9| Quick Sort

오늘은 일기를 생략하겠다 너무 졸립다..안뇽

Quick Sort

 

퀵 솔트는 매 단계마다 Pivot이라는 이름이 붙은 원소 하나를 차례로 보내는 정렬법이다.

 

정렬 과정

 

장점

1. 추가적인 공간이 필요하지 않다.

2. 배열 안에서의 자리 바꿈으로 처리한다. → Cache Hit 비율이 높다! (속도가 빠르다)

In Place Sort
원소위치를 잘 바꿔주면 되기 떄문에 추가적인 공간이 필요 없다.

 

 

정렬 과정

 

시간 복잡도

 

평균 : O(N LgN)

최악: O(N^2)

https://blog.encrypted.gg/955

https://blog.encrypted.gg/955

 

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