Invariante ; Hilfe!

[Amaninho]

hab hier mal ein problem komme garnicht vorran bitte um hilfe...

x=a[right];
i=left; j=right-1;
while (i<=j) {
while (a[i]<x) { ++i; }
while ((j>=left) && (a[j]>=x)) { --j; }
if (i<j) {swap(a, i, j); ++i; --j;}
}
swap(a, i, right);

Geben Sie für diesen Algorithmus eine Invariante an und begründen Sie mit ihrer Hilfe die
Korrektheit.

 

[Technoblade]

ZU allererst einmal, was soll der Algorithmus machen. Auf den ersten Blick ohne es mir genauer anzusehen würde ich auf Quicksort tippen, liege richtig?

 

[Amaninho]

Quicksort tippen, liege richtig?

Ja genau, liegst richtig

 

[Anime-Otaku]

Und wo hast du dabei ein Problem? Was ist dir unklar?

 

[vfl_freak]

Moin,

hast Du schon mal nach "Quicksort Invariante" gegoogled?
Da gibt es doch jede Menge Seiten (bspw. gleich der erste Link), die erklären, wie man die Korrektheit der Invariante beweisen kann ....

Gruß
Klaus

 

[Amaninho]

nach "Quicksort Invariante" gegoogled?

Wenn es so wäre bräuchten wir doch garnicht hier son Forum oder?
Soweit ich weiß, kann man ja mit der Vor und Nachbedingung die Invariante berechnen....
könnte es stimmen, dass die Vorbedingung

(i<=j)
(a[i]<x)((j>=left) && (a[j]>=x))

****?

 

[Amaninho]

Naja habs eben von selbst hinbekommen....danke trotzdem für die anstrengung

 

[vfl_freak]

Moin,

Wenn es so wäre bräuchten wir doch gar nicht hier so ein Forum oder?

ganz ehrlich, bevor ich hier (oder ähnlichen Foren) Fragen stelle, schaue immer erst mal im Web nach Lösungsansätzen!
Ein bisschen Eigeninitiative (oder zumindest der Versuch derselben) wird hier schon ganz gerne gesehen

Nix für ungut!
Gruß
Klaus

 

[genodeftest]

Moin,
ganz ehrlich, bevor ich hier (oder ähnlichen Foren) Fragen stelle, schaue immer erst mal im Web nach Lösungsansätzen!
Ein bisschen Eigeninitiative (oder zumindest der Versuch derselben) wird hier schon ganz gerne gesehen

Oder: bevor du hier etwas schreibst, solltest du schon mal versuchen, dein Problem mit Hilfe von
a) intelligentem Überlegen
b) Nutzung von Suchmaschinen
zu lösen, weil:
1.) sonst einige Menschen hier nicht oder stark gereizt antworten werden
2.) es erfahrungsgemäß einige Zeit dauert, bis dir hier jemand den entscheidenden Tipp gibt
3.) du sonst nicht weißt, welche ähnlichen Fehler die Nutzer hier (fälschlicher weise) vermuten könnten
4.) du lernst, Suchmaschinen zu nutzen (inklusive Eigenheiten, "versteckten" Funktionen, Parametern, ...)