Quick Sort

Og hov! Hvad er så forskellen på Quick Sort og Binary Tree Sort??
Er det ikke det samme?

Jeg forstår ikke helt din fremgangsmåde der.. :P
Quicksort bygger på funktionen Partition som deler en liste op i hvad der er større en pivot og hvad der er mindre end. Dette gøres ved at bruge en pointer der peger på det første element i listen der er større end pivot, og på det element vi er nået til at kigge på. Derefter kaldes Quicksort så på disse to dele, og på magisk rekursorisk vis sorteres listen :)

Partion fungere på denne måde, hvis vi tager dit eksempel:

5 3 8 1 2

Vi valgte 3 som pivot, så denne rykkes ned bagest i listen:

5 8 1 2 3

Vi kigger så på det første element. Dette er større end pivot, så derfor lader vi det være. Vi kigger så på det andet element, dette er også større, så derfor lader vi også det være.
Vi kigger nu på det næste tal (1). Dette er mindre end pivot, så derfor bytter vi det ud med det første tal i vores liste der er større end pivot, altså tallet 5. Dette ser så sådan ud:

1 8 5 2 3

Vi kigger så på det næste tal (2). Dette er også mindre end pivot, så vi bytter det ud med det første tal i listen der er større end pivot, denne gang er det tallet 8. Så har vi det sådan:

1 2 5 8 3

Vi har nu kigget på alle tal undtagen pivot, så derfor bytter vi nu pivot ud med det første tal i listen der er større end pivot, altså tallet 5:

1 2 3 8 5

Vi ved nu at tallet 3 står på sin rigtige plads i den sorterede liste, da altså under (eller lig med) ligger foran den, og alt større ligger efter den. Nu kaldes Quicksort så på listerne [1 2] og [8 5], og på denne måde sorteres listen..

Nej, disse er overhovedet ikke det samme!! :D
Når man sortere med Binary Tree Sort, så opbygger man først et binært søgetræ ud fra ens liste. Dette har den fine egenskab, at for alle knuder er alt nede i venstre ben mindre end knuden, og alt nede i højre ben større end knuden.

Derfor kan man så løbe træet igennem hvad at for hver knude at lave en liste som bliver til [ sort(venstre ben), knuden, sort(højre ben) ] ... Dette er meget kort fortalt :)

Hvorfor spørger du om disse søgealgoritmer?

1000 1000 1000 mange tak! :-D
Hvad skulle jeg dog gøre uden dette forum!
Nu har jeg forstået Quick Sorten meget meget bedre - og ja, den er overhoved ikke den samme som Binary Tree Sorting. Jeg kan godt se forskellen nu.
Grundet til jeg spørger er pga eksamen ;-)
Men jeg kan ikke gennemgå kode på tavlen for sorterings algoritmer da det tager for lang tid og derfor skal jeg have teorien på plads som disse eksempler.
På forhånd endnu engang mange tak for hjælpen!

Du skulle måske overveje at invistere i en bog, eller i det midste finde en hjemmeside der kan forklare det mest basale omkring sproget, istedet for at få andre folk til at lave dine lektier. Ellers lærer du det aldrig :)

Der findes f.eks mange gennemgange af quicksort på nettet.

Og du skulle måske bruge din tid lidt mere fornuftigt i stedet for at belære andre folk hvad de skal gøre. Jeg er ikke født med nørd-genet som dig og takket være Sorenlyn at der findes mennesker som ham som deler ud, i stedet for holde på det som visse andre....

Aufwiderschnitzel.

Tak tak :) Men som Kenneth siger, så hvis du skal vide mere om algoritmik så er http://mitpress.mit.edu/algorithms/ en super god bog!

Må jeg spørge hvad du skal til eksamen i? Er det universitet eller hvad?

Tak :)

Jeg skal til eksamen i grundlæggende C++
og ja, universitet - håber ikke du er min censor i morgen, haha...

Hehe, nej det er jeg ikke :P Jeg læser selv datalogi..

lifehacker, selv om du måske ikke kan lide det kenneth_gorking skriver har han helt ret.

Når jeg ser på alle de spørgsmål du har stillet i diverse fora den seneste tid, er jeg noget overrasket over at det er på universitets niveau du skal til eksamen.

Jeg kan kun anbefale Algorithms. En meget god bog som beskriver algoritmer til begynderen. Krydret med lidt matematik, hvilket kun er godt i mine øjne.