6-1 Quick Sort 동작방식, Big-O

퀵소트에 동작방식과 big O에 대해서 알아보겠습니다.

 

퀵소트는 뭔가 이름만 들었을 때 굉장히 빠른 것 같습니다.

 

얘는 pivot이라는 좀 특이한 방식을 사용하고, 시간복잡도가 n log n ~ n^2 입니다.

 

어떻게 동작하는지, 한번 아래의 그림을 보겠습니다.

 

만약 맨 오른쪽 애를 pivot이라고 설정하면, pivot을 기준으로 작은애들은 왼쪽, 큰 애들은 오른쪽으로 옮겨줍니다.

 

이 과정을 다 쪼개질 때 까지 반복해줍니다.

 

 

자, 시간복잡도를 알아보겠습니다.

 

merge sort와 같이 n long n 이 나옵니다. (반으로 쪼개고 - log n , 정렬하기 n)

 

다만 조금 특이한 것이 worst case라는 것이 있습니다.

 

 

위와 같이 이미 정렬된 배열의 경우에는, 배열을 쪼개는 것이 의미가 없어지기 때문에 n^2의 시간복잡도를 가집니다.

 

자세한 부분 영상에서 같이 살펴보겠습니다 :)