Diskussion:Quickselect

Vorteil gegenüber linearer Suche?

Letzter Kommentar: vor 4 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

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

Abschnitt hinzufügen