퀵소트1 [알고리즘] 정렬 - quick sort 퀵소트 - 불안정정렬, 비교정렬 - divide and conquer 사용 이름이 퀵소트인지라 best case에선 가장 빠른 시간복잡도를 가지지만 worst case에선 한없이 느려지는....양날의 칼느낌이다. 그냥 머지소트를 쓰는 걸로 하자. 시간 복잡도 best case O(n log n) worst case O(n^2) worst case는 어떤 경우냐 하면 오름차순 정렬인데 5 4 3 2 1로 배열이 제시되었을 경우이다. 퀵 소트의 구현 과정을 살펴보면 이해 가능하다. 퀵소트는 1. pivot이 있고 (보통 배열 왼쪽 끝 혹은 오른쪽 끝 값) 2. 피벗을 중심으로 좌측엔 피벗보다 작은값, 우측엔 피벗보다 큰 값을 배치한다. 3. 작은값, 큰 값 교차 지점에 피벗을 놓는다. 4. 피벗을 중심으로 .. 2020. 11. 29. 이전 1 다음
