Quicksort Rang ausgeben

[Mariexshhx]

Gegeben seien A[0, . . . , n − 1] und i ∈ N, 0 ≤ i ≤ n − 1. Beschreiben Sie einen Algo-
rithmus, der eine Abwandlung von QuickSort ist, sodass das Element
x mit rang(A, x) = i ausgegeben wird, ohne dabei A vollständig zu sortieren.

Heißt das x muss nicht in A sein und ich muss das Elemnent in A finden das dem Rang von x entspricht ?

 

[Mariexshhx]

Gegeben seien A[0, . . . , n − 1] und i ∈ N, 0 ≤ i ≤ n − 1. Beschreiben Sie einen Algo-
rithmus, der eine Abwandlung von QuickSort ist, sodass das Element
x mit rang(A, x) = i ausgegeben wird, ohne dabei A vollständig zu sortieren.

Heißt das x muss nicht in A sein und ich muss das Elemnent in A finden das dem Rang von x entspricht ?

bzw der Index der dem Rang entspricht.

 

[Blender3D]

Heißt das x muss nicht in A sein und ich muss das Elemnent in A finden das dem Rang von x entspricht ?

Bei einem unsortiertem Array kann es zwar vorkommen, dass ein Element x aus A zufällig die Bedingung rang(A,x) = i erfüllt.
Das ist aber nicht zwingend. Sobald aber diese Bedingung für x erfüllt ist --> x ist sortiert.
Falls x nicht in A ist --> rang(A,x)= i kann nicht erfüllt werden. Also x muss sich in A befinden.