Diskussion:Quickselect

Letzter Kommentar: vor 4 Jahren von Jonathan Haas in Abschnitt Vorteil gegenüber linearer Suche?

Vorteil gegenüber linearer Suche?

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)Beantworten

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)Beantworten