목록2025/01/31 (1)

Toolofv 님의 블로그

[Python] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)은 병합 정렬(Merge Sort)와 비슷하게 분할정복(Divide and Conqueror)의 방법으로 정렬되는 알고리즘이다. 퀵 정렬은 시간복잡도로는 복불복이다. 최선, 평균의 경우 $O(n\ log\ n)$이지만 최악의 피벗을 선택했을 경우 $O(n^{2})$이다. 공간복잡도는 추가적인 배열을 만들지 않는 In-Place 방식의 경우 추가배열이 만들어지지 않지만 재귀함수 호출로 인해 $O(log\ n)$이다. 추가적인 배열을 선언하는 Non-In-Place 방식은 $O(n)$이다. 퀵 정렬(Quick Sort)  1. pivot을 왼쪽으로 몰거나 오른쪽으로 몰아 하는 방식이 있다.(아래는 왼쪽 이동하는 방법이다.)2. pivot값을 지정한 후 l ,  r 을 pivot값..
Algorithm 2025. 1. 31. 00:29
이전 Prev 1 Next 다음