Diskussion:Quickselect
Letzter Kommentar: vor 4 Jahren von Jonathan Haas in Abschnitt Vorteil gegenüber linearer Suche?
Vorteil gegenüber linearer Suche?
[Quelltext bearbeiten]Ich hab es bestimmt falsch verstanden. Aber eine unsortierte Liste linear zu durchsuchen hat ebenfalls eine Laufzeit von O(n). Inwiefern ist Quickselect dann besser? --HB Jepsen (Diskussion) 18:12, 28. Mär. 2020 (CET)
- Wie findest du denn mit einer normalen linearen suche das k-kleinste (also z. B. viert-kleinste, sechst-kleinste, hundertelft-kleinste usw.) Element? Oder z. B. den Median in einer unsortieren Liste von Zahlen? Intuitiv müsste man die Liste sortieren und das k-te Element nehmen, aber mit Quickselect geht das schneller. -- Jonathan 19:34, 29. Mär. 2020 (CEST)