이진 배열 빠른 할당

Question

최악의 경우 Quicksort가 얼마나 많은 이진 배열을 크기 n으로 정렬해야하는지 알고 싶습니다.
이 문제의 최악의 사례를 찾을 수 없습니다. [0 1 0 1 0 1..]?
건배,
EO

Answer 1

아니 정확히 퀵,하지만 당신은 당신이 O (N)에서 할 수있는 바이너리 배열을 정렬하려는 경우. 얼마나 많은 1과 0을 당신이 원하는 순서대로 쓰는지 계산하십시오. 다음 배열에 대한 예를 들어

:

[0 1 0 1 0 1 1] 

당신은 O에서 (n)이, 믿을 수있는 세 개의 0과 사 1의 있습니다. 그런 다음 배열을 먼저 3 개의 0과 4 개의 1로 다시 작성합니다.

Answer 2

실제로 소수의 고유 키로 구성된 배열을 정렬하는 것이 일반적입니다. 고유 키 수가 O (1) 일 때 O (n) 시간에 적응하는 알고리즘을 원합니다. 귀하의 경우 두 가지 고유 키가 있습니다.

이것은 QuickSort 내가이 배열 [ 0 1 1 0 1 0 1 0 0 0 1 0 1 ]에 퀵 알고리즘을 테스트 한 사건에 대한 최악의 경우에 O (nlogn) 평균 그러나 O (N^2)이며, 배열의 아이폰에이 13 요소이며, 알고리즘은 n^2 인 배열을 정렬하기 위해 170 반복을 사용합니다.

그리고 O (n)이 알고리즘이 의사 코드 :

는

let n0 <- 0; 
for i=0 to lenght(A) 
    if A[i] == 0 
     A[n0] = 0; 
     ++n0 

for i=n0 to lenght(A) 
    A[i] = 1