최상의 답변
피벗 찾기, 현재 배열 분할 및 다시 수행과 같은 빠른 정렬 작동 방식에 대한 충분한 지식이있는 경우 각 하위 배열에 대해 반복적으로 동일하므로 다음 사항을 고려하여 시간 복잡성을 쉽게 분석 할 수 있습니다.
최악의 경우 :
각 재귀에서 배열을 분할하기위한 다음 피벗이 배열의 끝에있을 때 최악의 경우가 발생합니다.
N이면 는 배열의 길이이며 배열의 시작 위치에 현재 피벗이있는 경우
마지막 인덱스에서 피벗은 시작에서 끝까지 배열을 순회하는 것만 식별됩니다. 피벗을 수정하고 결과 하위 배열을 분할하면 (N-1), 1 이됩니다.
다시 (N-1) 하위 배열은 길이가 (N-2), 1 .
이 과정은 최종 하위 배열 길이가 둘 다 1,1 이 될 때까지 반복됩니다.
그래서, 이것은 N 요소를 사용하여
1 단계에서 수학적으로 종이에 그릴 수 있습니다.이 파티션의 시간 복잡도는 다음과 같습니다.
T (N) = N + T (N-1)
T (N-1)은 파티션의 시간 복잡도입니다. 반복적으로 처리되고 N은 N 요소를 고정 피벗과 비교하는 데 필요한 시간입니다.
2 단계 : N-1 요소 사용 ,
T (N-1) = (N-1) + T (N-2)
T (N-2) = (N-2) + T (N-3)
…
T (3) = 3 + T (2)
T (2) = 2 + T (1)
T ( 1) = 0, 길이가 1인 배열을 분할하는 시간은 분할이없는 0입니다.
따라서
T (N) = N + (N-1) + (N-2) … + 3 + 2 ≈ N * (N + 1) / 2
= (N ^ 2) / 2
= O (N ^ 2)
평균 사례 :
평균적인 경우 다음 피벗은 비교를 통해 배열을 두 개의 동일한 길이로 분할합니다 (N / 2) 시간 복잡성을 초래하는 모든 요소 N.
T (N) = 2 * T (N / 2) + N
양변을 N으로 나누기
T (N) / N = 2 * (T (N / 2) / N) + N / N
T (N) / N = 2 * (T (N / 2) / N) + 1
따라서 T (N) / N = (T (N / 2) / (N / 2)) + 1
T (N / 2) / (N / 2) = T (N / 4) / (N / 4) + 1
…
T (2) / 2 = T (1) / 1 + 1
T (1) = 0으로
T (2) / 2 = 1
T (4) / 4 = T (2) + T (1)
T (8) / 8 = T (4) + T (2) + T (1) ## log (n) 항
따라서 T (N) / N = log N
T (N) = NlogN
Answer
QuickSort는 Divide and Conquer 알고리즘입니다. 요소를 피벗으로 선택하고 선택한 피벗을 중심으로 주어진 배열을 분할합니다. 다양한 방법으로 피벗을 선택하는 다양한 버전의 quickSort가 있습니다.
- 항상 첫 번째 요소를 피벗으로 선택합니다.
- 항상 마지막 요소를 피벗으로 선택 (구현 됨) 아래)
- 무작위 요소를 피벗으로 선택합니다.
- 중앙값을 피벗으로 선택합니다.
quickSort의 핵심 프로세스는 파티션 ( ). 파티션의 대상은 배열과 배열의 요소 x가 피벗으로 주어지고 x를 정렬 된 배열의 올바른 위치에 놓고 x보다 작은 모든 요소 (x보다 작음)를 x 앞에 놓고 더 큰 요소 (더 큰 요소)를 모두 넣는 것입니다. x보다) x 뒤에. 이 모든 것은 선형 시간에 이루어져야합니다.
퀵 정렬 단계는 다음과 같습니다.
Step 1 − Choose the highest index value has a pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at the right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is the new pivot
퀵 정렬 구현 :
Quicksort(A,p,r) {
if (p < r) {
q <- Partition(A,p,r)
Quicksort(A,p,q)
Quicksort(A,q+1,r)
}
}
Partition(A,p,r)
x <- A[p]
i <- p-1
j <- r+1
while (True) {
repeat
j <- j-1
until (A[j] <= x)
i <- i+1
until (A[i] >= x)
if (i A[j]
else
return(j)
}
}
퀵 정렬의 시간 복잡성 :
최악 사례 : 최악의 경우는 파티션 프로세스가 항상 가장 큰 요소 또는 가장 작은 요소를 피벗으로 선택할 때 발생합니다. 마지막 요소가 항상 피벗으로 선택되는 위의 파티션 전략을 고려하면 배열이 이미 증가 또는 감소하는 순서로 정렬 된 경우 최악의 경우가 발생합니다. 다음은 최악의 경우의 반복입니다.
T(n) = T(0) + T(n-1) + (n)
which is equivalent to
T(n) = T(n-1) + (n)
위 반복의 복잡성은 n 제곱
최상의 사례 : 최상의 경우는 파티션 프로세스가 항상 선택하는 경우 발생합니다. 피벗으로 중간 요소. 다음은 최상의 경우에 대한 반복입니다.
T(n) = 2T(n/2) + (n)
위 반복의 복잡성은 nLogn
평균 사례 : 평균 사례 분석을 수행하려면 배열의 가능한 모든 순열을 고려하고 쉽지 않은 모든 순열에 걸리는 시간을 계산해야합니다. 파티션이 한 세트에 O (n / 9) 요소를 배치하고 다른 세트에 O (9n / 10) 요소를 배치하는 경우를 고려하여 평균 케이스에 대한 아이디어를 얻을 수 있습니다. 다음은이 사례에 대한 반복입니다.
T(n) = T(n/9) + T(9n/10) + (n)
위 반복의 복잡성은 nLogn
퀵 정렬의 공간 복잡성 :
퀵 정렬이 사용하는 공간은 사용 된 버전에 따라 다릅니다.
퀵 정렬의 인플레 이스 버전은 공간 복잡성이 O (log n)입니다. 최악의 경우, 다음 전략을 사용하여 신중하게 구현하는 경우 :
- 인플레 이스 파티셔닝이 사용됩니다. 이 불안정한 파티션에는 O (1) 공간이 필요합니다.
- 파티션 후 가장 적은 요소가있는 파티션이 먼저 (재귀 적으로) 정렬되어 최대 O (log n) 공간이 필요합니다. 그런 다음 다른 파티션은 호출 스택에 추가되지 않는 꼬리 재귀 또는 반복을 사용하여 정렬됩니다. 위에서 설명한 것처럼이 아이디어는 R. Sedgewick이 설명했으며 스택 깊이를 O (log n)로 제한합니다.