AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen
Thema durchsuchen
Ansicht
Themen-Optionen

Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

Ein Thema von Nikolas · begonnen am 8. Sep 2007 · letzter Beitrag vom 8. Sep 2007
Antwort Antwort
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#1

Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

  Alt 8. Sep 2007, 11:25
Hallo

Ich bereite mich gerade auf meine Info2 Klausur vor und habe eine Frage gefunden, bei der ich erstmal keine Antwort habe:

Zitat:
Geben Sie drei unterschiedliche Zahlenfolgen der Länge 9 (mit den Elementen 1-9 ) an,
die bei der Sortierung mit Quicksort zu einer worst-case-Laufzeit f führen. (Als Pivotelement wird immer das Element am rechten Rand der Folge gewählt.)
Der Quicksort läuft um so schlechter, je ungleicher die beiden Teile nach einem Divide-Schritt sind. Im schlimmsten Fall habe ich also eine 'Hälfte' mit n-1 Elementen und eine mit einem Element. Das passiert sicher dann wenn ich eine sortierte Eingabe habe und Pivot wie angegeben wähle. Da es egal ist, ob die Folge aufsteigend oder absteigend sortiert ist, habe ich schon mal zwei Lösungen. (Jedenfalls, wenn man die Anzahl der Vergleiche zählt. Bei den Vertauschungen ist die in der richtige Reihenfolge sortierte Zahlenfolge deutlich besser).
Nur eine dritte fehlt mir.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#2

Re: Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

  Alt 8. Sep 2007, 15:15
Wenn das:
1 2 3 4 5 6 7 8 9
und das:
9 8 7 6 5 4 3 2 1
zu einer Worst-Case-Laufzeit führt, sollte das:
2 1 3 4 5 6 7 8 9
und das:
8 9 7 6 5 4 3 2 1
doch auch ein Worst-Case Verhalten provozieren, oder?

Edit: Oder eine dieser Folgen:

2 3 4 5 6 7 8 9 1

8 7 6 5 4 3 2 1 9

5 4 6 3 7 2 8 1 9

Ist doch gar nicht so schwer

Die Bedingung ist ja im Grunde, dass bei einer beliebigen jeder Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#3

Re: Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

  Alt 8. Sep 2007, 15:25
> Die Bedingung ist ja im Grunde, dass bei einer beliebigen Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind

Das hast du aber schön gesagt

Jetzt seh ichs auch. Danke schön. Ich habe einfach übersehen, dass ich nach der Wahl jedes Pivotelements neu entscheiden darf, ob die Zahlen links davon alle größer sind, oder kleiner und diese Wahl nicht für alle gilt, was dann ausschließlich auf meine Lösungen geführt hat.

Vielen Dank
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von jfheins
jfheins

Registriert seit: 10. Jun 2004
Ort: Garching (TUM)
4.579 Beiträge
 
#4

Re: Zahlenfolgen, die zu n^2 Laufzeit beim Quicksort führen

  Alt 8. Sep 2007, 19:11
Zitat von Nikolas:
> Die Bedingung ist ja im Grunde, dass bei einer beliebigen Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind

Das hast du aber schön gesagt

Jetzt seh ichs auch. Danke schön. Ich habe einfach übersehen, dass ich nach der Wahl jedes Pivotelements neu entscheiden darf, ob die Zahlen links davon alle größer sind, oder kleiner und diese Wahl nicht für alle gilt, was dann ausschließlich auf meine Lösungen geführt hat.

Vielen Dank
Freut mich, geholfen zu haben

Aber ich habe meine Aussage nochmal korrigiert, damit sie auch richtig ist

Diese Fragen, die immer eine Antwort mehr fordern als offensichtlich sind, mag ich auch nicht gerne
  Mit Zitat antworten Zitat
Antwort Antwort


Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 00:40 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz