1
첫 번째 요소에서 항상 피벗하는 표준 양방향 파티션 QuickSort 알고리즘이 있다고 가정합니다. 그러나 QuickSort의이 작은 변형에서 먼저 첫 번째 요소와 중간 요소를 교환 한 다음 '새로운'첫 번째 요소를 피벗합니다. 내 질문은 이것이 최악의 실행 시간을 바꿀 것인가하는 것입니다.각 파티션의 가운데와 첫 번째 요소를 바꿔 넣은 퀵 포트
초기 생각은 각각의 하위 배열에서와 마찬가지로 요소가 서로 상대적으로 임의의 순서로 유지되므로 첫 번째 요소와 중간 요소를 전환해도 전반적인 런타임은 변경되지 않습니다. 그러나 최악의 시나리오를 찾는 데 관심이 있으므로이 약간의 변형으로 인해 원래 알고리즘의 최악의 런타임을 변경하는 특수 배열이 있는지 확실하지 않습니다.