Gegeben seien A[0, . . . , n − 1] und i ∈ N, 0 ≤ i ≤ n − 1. Beschreiben Sie einen Algo-
rithmus, der eine Abwandlung von Partition aus dem Skript ist, sodass rang(A, A)
in Laufzeit O(n) ausgegeben wird.
Partion sortiert ja alle Elemente die kleiner als das Pivotelement sind links davon und alle die größer sind rechts davon. Der Rang von A ist die Zahl, die angibt wie viele Elemnte in A kleiner sind als A. Könnte man nun nicht A als Pivotelement wählen und wenn Partition ausgeführt wurde, gibt der index i den Rang von A an, weil links davon nur kleinere Elemente stehen und Index 0 bis i-1 sind dann halt kleiner. Die Laufzeit beträgt doch dann O(n) weil es nie mehr als n Vertauschungen bei Partition geben kann ?
Kann mir jemand weiterhelfen ? Danke im vorraus
rithmus, der eine Abwandlung von Partition aus dem Skript ist, sodass rang(A, A)
in Laufzeit O(n) ausgegeben wird.
Partion sortiert ja alle Elemente die kleiner als das Pivotelement sind links davon und alle die größer sind rechts davon. Der Rang von A ist die Zahl, die angibt wie viele Elemnte in A kleiner sind als A. Könnte man nun nicht A als Pivotelement wählen und wenn Partition ausgeführt wurde, gibt der index i den Rang von A an, weil links davon nur kleinere Elemente stehen und Index 0 bis i-1 sind dann halt kleiner. Die Laufzeit beträgt doch dann O(n) weil es nie mehr als n Vertauschungen bei Partition geben kann ?
Kann mir jemand weiterhelfen ? Danke im vorraus
