AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Quicksort mit Median of Three

Ein Thema von 3_of_8 · begonnen am 10. Apr 2006 · letzter Beitrag vom 10. Apr 2006
Antwort Antwort
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#1

Re: Quicksort mit Median of Three

  Alt 10. Apr 2006, 20:25
http://de.wikipedia.org/wiki/Quicksort

da steht bei Laufzeit:

Zitat:
Ein Ansatz, um worst-case-Laufzeiten zu verhindern, ist, als Pivotelement ein zufällig bestimmtes Element zu wählen. Bei diesem randomisierten Quicksort ist die Wahrscheinlichkeit, dass das Pivotelement in jedem Teilungsschritt so gewählt wird, dass sich die worst case-Laufzeit ergibt, extrem gering, so dass man praktisch von einer Komplexität von O(n·log(n)) ausgehen kann. Eine andere Möglichkeit ist die Verwendung des Medians von z.B. drei zufällig gewählten Elementen. Durch geschickte Wahl des Pivotelementes kann man aber nur das mittlere schlechteste Verhalten verbessern. Vollständig verhindern kann man das Eintreten des Worst Cases jedoch nicht.
Über google solltest du vom prinzip bis zu vollständigen Implementierungen alles finden
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
Antwort Antwort

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

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 16:06 Uhr.
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024-2025 by Thomas Breitkreuz