개발스토리

빠른 정렬(Quicksort) 분할 정복 알고리즘의 일종으로, 평균적으로 매우 빠른 수행 속도를 자랑한다. - 평균 시간복잡도: θ(n log⁡n) - 최악 시간복잡도: θ(n^2) 빠른 정렬의 진행 과정 아래의 배열이 있다. 여기서 pivot이라 불리는 기준 값을 하나 정한다. 보통 맨 앞이나 중앙을 선택한다. 나는 중앙을 pivot으로 두겠다. 그 다음, pivot을 제외한 나머지에서 가장 왼쪽은 left, 가장 오른쪽은 right로 둔다. left와 right는 pivot과 비교한다. left는 pivot보다 큰 수를 만나면, right는 pivot보다 작은 수를 만나면 대기한 뒤 서로 교환한다. 이렇게 left와 right가 움직이다가 left가 right 오른쪽에 위치하면 그만둔다. 단, piv..