---

Hej Gruppe

Jeg sidder og skal sortere et array bestående af 23 fodboldspillerobjekter.
Der skal sorteres på deres x-koordinat, sådan at mindste x-koordinat får
plads 0.

Pt. har jeg implementeret det vha. en quicksort, og jeg opnår tider på
omkring 0,2 - 0,3 milisekunder. Det der undrer mig er at tiderne ikke bliver
mindre efter de er sorteret første gang (det skal siges at efter den første
sortering ændres der ikke på koordinaterne).

Da det er rimeligt tidskritisk er jeg ude efter den hurtigste sortering, til
disse 23 objekter.

Er der nogen der har erfaringer med en hurtigere metode end quicksort og
nogen der kan forklare hvorfor tiderne ikke bliver mindre efter første
sortering?

Mvh
Søren T. Hansen

---

Søren Thestrup Hansen skrev:

>Pt. har jeg implementeret det vha. en quicksort, og jeg opnår tider på
>omkring 0,2 - 0,3 milisekunder. Det der undrer mig er at tiderne ikke bliver
>mindre efter de er sorteret første gang

Quicksort er ligeglad med om den får sorterede data.

>Er der nogen der har erfaringer med en hurtigere metode end quicksort

Ikke en det kan svare sig at implementere, men man kan kombinere
QS med insertsort som skal tage over hvis intervallet er på cirka
15 elementer. Det går ca. 20 % hurtigere.

Hvis du vil have en rutine der er hurtig til sorterede data, skal
du bruge bubblesort eller insertsort, men de er desværre
langsomme til usorterede data.

>og nogen der kan forklare hvorfor tiderne ikke bliver mindre efter første sortering?

QS blander elementerne alligevel.

Jeg har lavet et program som jeg selv har haft meget fornøjelse
af. Jeg ved ikke hvor godt det er for andre at bruge. Det er
kompileret til Windows/DOS og ligger her:
http://lundhansen.dk/bertel/programmer/programmer.php
og hedder "Sortdemo" (cirka midt på siden).

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

> Hvis du vil have en rutine der er hurtig til sorterede data, skal
> du bruge bubblesort eller insertsort, men de er desværre
> langsomme til usorterede data.

Data er kun usorterede første gang de bliver modtaget, derefter er det
sjældent at de bytter plads (1000 samples i sekundet og det er positionsdata
fra en alm. fodboldkamp).
Så det ville måske være en fordel at bruge en bubblesort i stedet? Evt
kombineret med en quicksort til den første gang.

Mvh
Søren T. Hansen

---

Søren Thestrup Hansen skrev:

>Så det ville måske være en fordel at bruge en bubblesort i stedet? Evt
>kombineret med en quicksort til den første gang.

Det kunne godt lyde sådan.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

[ Søren Thestrup Hansen ]

[ ... ]

> Så det ville måske være en fordel at bruge en bubblesort i stedet?


Bubble sort er _aldri_ raskere enn insertion sort. Ej heller er den
intuitiv.

[ ... ]





ivr
--
My compiler compiled yours
            - Visual C++ .Net 2003 motto

---

> Jeg har lavet et program som jeg selv har haft meget fornøjelse
> af. Jeg ved ikke hvor godt det er for andre at bruge. Det er
> kompileret til Windows/DOS og ligger her:
> http://lundhansen.dk/bertel/programmer/programmer.php
> og hedder "Sortdemo" (cirka midt på siden).

Rigtig godt program for øvrigt - Har dog lige 2 spørgsmål til det.
1) Hvor mange elementer bliver der sorteret
2) Vises tiderne i sekunder?

Og faktisk lige et lille bonusspørgsmål
Må vi henvise til dit program i vores opgave?

Mvh
Søren T. Hansen

---

Søren Thestrup Hansen skrev:

>Rigtig godt program for øvrigt - Har dog lige 2 spørgsmål til det.
>1) Hvor mange elementer bliver der sorteret

Så mange som der er plads til på en skærm, normalt 50 linjer
(4000 tegn).

>2) Vises tiderne i sekunder?

Ja.

>Og faktisk lige et lille bonusspørgsmål
>Må vi henvise til dit program i vores opgave?

Ja, det må I gerne, og det er til fri afbenyttelse.

Resultatere kan ikke tages som et endegyldigt mål for hvad der er
den hurtigste algoritme. Hvis man f.eks. er nødt til at sortere
på disk, kan det ske at de opfører sig anderledes.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

> Quicksort er ligeglad med om den får sorterede data.

For at være lidt pernitten og for at rette en fejlforståelse fra Søren, så
lad mig påpege at quicksort-algoritmen bestemt ikke er ligeglad. Den er
hurtigere på usorterede data end på data som er sorteret i forvejen.
En undtagelse fra den regel er en randomized implementation af quicksort med
random pivot, men quicksort som sådan er ikke ligeglad.
Derfor skal Søren snare være glad for at han ikke måler en forlængelse af
tiden.

Lad mig også lige indskyde at 23 x-koordinater som sorteres ikke er ret
meget. En tidsmåling skal være pokkers præcis for at give noget meningsfuldt
resultat på en sortering.

Til sidst. Når vi taler om så små mængder data som 23, så er quicksort næppe
den hurtigste metode. En insert sort eller ligende vil nok være hurtigere,
da implementationenen er simplere og der er væsentligt mindre overhead i
algoritmen end i quicksort.

---

[ Jakob Nielsen ]

[ ... ]

> For at være lidt pernitten og for at rette en fejlforståelse fra Søren, så
> lad mig påpege at quicksort-algoritmen bestemt ikke er ligeglad. Den er
> hurtigere på usorterede data end på data som er sorteret i forvejen.


Det avhenger vel av pivotstrategien?

En klassisk median-of-3 framgangsmåte vil faktisk gi den optimale
kjøretiden både på sortert og "omvendt sortert" rekkefølge.

En annen kuriøsitet relatert til quicksort er et lite skriv av Doug McIlroy:

<URL: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf>

Men uansett, siden det er så få elementer, kan man kanskje utnytte
det? Eller, om mulig, utnytte at intervallet til x-verdier er relativt
lite (slik som radix sort gjør).

[ ... ]





ivr
--
My compiler compiled yours
            - Visual C++ .Net 2003 motto

---

> Det avhenger vel av pivotstrategien?

Ja, som jeg blandt andet skrev "En undtagelse fra den regel er en randomized
implementation af quicksort med
random pivot". Quicksort som sådan har en pivot omkring sidste element. Der
er så varianter der gør tingene anderledes. Som du siger så vil valget af
medianen give optimal køretid, da man faktisk deler data i to lige store
dele hver gang.
Et valg af medianen vil dog ikke "være ligeglad" med om data er sorteret.
Det vil random pivot til gengæld.

> Men uansett, siden det er så få elementer, kan man kanskje utnytte
> det? Eller, om mulig, utnytte at intervallet til x-verdier er relativt
> lite (slik som radix sort gjør).

Jeg tror at simple metode vil give bedste tid på så få data. Jeg tror også
at snart sagt ethvert valg af sortering vil give et ok resultat for de 26
elementer. Man skal nok måle på det, eller køre sorteringen meget ofte, for
at opdage tidsforskellen selv.

---

Jakob Nielsen skrev:

>random pivot". Quicksort som sådan har en pivot omkring sidste element.

Jeg har altid bugt en version med pivot omkring medianen. Det var
først for noget tid siden at jeg fandt ud af at det ikke var den
'helt rigtige' QS. Jeg har også prøvet at splitte op i tre dele,
men det gav ingen fordel som jeg kunne konstatere.

>Et valg af medianen vil dog ikke "være ligeglad" med om data er sorteret.

I mit testprogram får jeg cirka samme sorteringstid ved blandede
data og sorterede data - faktisk går det en anelse hurtigere ved
sorterede data (0,03 contra 0,05 sek.), men tiderne er nok så små
at det er svært at stole på dem.

>Jeg tror at simple metode vil give bedste tid på så få data. Jeg tror også
>at snart sagt ethvert valg af sortering vil give et ok resultat for de 26
>elementer.

Især da hvis de kun er blandede første gang.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

> Jeg har altid bugt en version med pivot omkring medianen. Det var
> først for noget tid siden at jeg fandt ud af at det ikke var den
> 'helt rigtige' QS. Jeg har også prøvet at splitte op i tre dele,
> men det gav ingen fordel som jeg kunne konstatere.

Nu var det som sagt bare for at være "pernitten" at jeg overhovedet
bemærkede at quick sort bruger sidste element som pivot.

Jeg vil tro at det overhead en deling i tre giver dræber den gavn man har af
lavere rekursionsdybde. Uanset så er grænseværdien for køretid den samme, da
log2 og log3 er lineært afhængige.

> I mit testprogram får jeg cirka samme sorteringstid ved blandede
> data og sorterede data - faktisk går det en anelse hurtigere ved
> sorterede data (0,03 contra 0,05 sek.), men tiderne er nok så små
> at det er svært at stole på dem.

Hvordan måler du den tid?

> Især da hvis de kun er blandede første gang.

Ya Man kan jo også lave ens sortering så den først ser om data ER
sorterede. Hvis de er, så returnerer funktionen bare.

---

Jakob Nielsen skrev:

>> I mit testprogram får jeg cirka samme sorteringstid ved blandede
>> data og sorterede data - faktisk går det en anelse hurtigere ved
>> sorterede data (0,03 contra 0,05 sek.), men tiderne er nok så små
>> at det er svært at stole på dem.

>Hvordan måler du den tid?

Programmet er skrevet i TurboPascal, og jeg inkluderede et eller
andet bibliotek der havde timerfunktioner. Jeg har glemt hvor jeg
har det fra, men modulet hedder tp_timer.

Det blev udviklet på en 233 MHz-maskine.

Tiderne er kun til orientering. Der er jo f.eks. lavet tjek på om
man trykker på en tast og om der skal laves en forsinkelse, og
begge dele tager tid.

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

> Programmet er skrevet i TurboPascal, og jeg inkluderede et eller
> andet bibliotek der havde timerfunktioner. Jeg har glemt hvor jeg
> har det fra, men modulet hedder tp_timer.
>
> Det blev udviklet på en 233 MHz-maskine.

Ok. Det er altså ikke en decideret profiler. Jeg vil tro at man skal over i
den slags værktøj før man kan sige bare lidt om tiden for sortering af så
små datamængder. Hm.. næ hvor små var dine datamængder egentlig? Var det en
test du lavede nu med 26, eller hvorledes?

---

Jakob Nielsen skrev:

>Ok. Det er altså ikke en decideret profiler.

Nej, absolut ikke.

>Hm.. næ hvor små var dine datamængder egentlig?

En skærmfuld tilfældige tegn, normalt 4000 (afhænger af skærmens
størrelse).

>Var det en test du lavede nu med 26, eller hvorledes?

Det var et program til at illustrere hvordan
sorteringsalgoritmerne virker, og jeg synes selv at det er ret
godt. Man kan nedsætte tempoet til det ulidelige så man kan se
hvert tegn blive lagt på plads. Der sorteres nemlig 'live' på
skærmen. Det hjalp mig til at forstå algoritmernes virkemåde. Det
ligger her og er til fri afbenyttelse:

http://lundhansen.dk/bertel/programmer/programmer.php

Det hedder "Sortdemo" og linket er ca. midt på siden. Det
indeholder 10 algoritmer og man kan vælge tilfældige data eller
præsorterede data. Data initialiseres én gang så hver rutine
bearbejder præcis samme sæt data (inden for samme opstart af
programmet).

A) Bubblesort
B) Insertsort
C) Selectsort
D) Radixsort
E) Shell(Bubble)sort
F) Heapsort
G) Shell(insert)sort
H) Mergesort
I) Quicksort
J) Quick+Insertsort

--
Bertel
http://bertel.lundhansen.dk/   FIDUSO: http://fiduso.dk/

---

> > Især da hvis de kun er blandede første gang.
>
> Ya Man kan jo også lave ens sortering så den først ser om data ER
> sorterede. Hvis de er, så returnerer funktionen bare.

Hvordan vil du kontrollere om de ER sorterede? Vil det ikke kræve en
sortering for at garantere det?
Eller vil du have et flag som bliver sat efter sortering og derefter resat
hvis data bliver ændret?

Mvh
-Søren Thestrup Hansen

---

> Hvordan vil du kontrollere om de ER sorterede? Vil det ikke kræve en
> sortering for at garantere det?
> Eller vil du have et flag som bliver sat efter sortering og derefter resat
> hvis data bliver ændret?

for hvert element er det da større end eller lig med det foregående.
Det tager naturligvis tid, men lineær tid i forhold til mængden af data. En
sammenlignings-sortering tager O(n * log n), og et check er derfor
asymptotisk hurtigere end enhver sammenligningssortering. Den reelt tid er
også væsentligt mindre da man dårligt kan lave noget mere simpelt end denne
test.

---

"Søren Thestrup Hansen" <bluesboys@-remove-this-hotmail.com> wrote in
news:cmvub1$thm$1@news.net.uni-c.dk:

> Hej Gruppe
>
> Jeg sidder og skal sortere et array bestående af 23
> fodboldspillerobjekter. Der skal sorteres på deres x-koordinat, sådan
> at mindste x-koordinat får plads 0.
>
> Pt. har jeg implementeret det vha. en quicksort, og jeg opnår tider på
> omkring 0,2 - 0,3 milisekunder. Det der undrer mig er at tiderne ikke
> bliver mindre efter de er sorteret første gang (det skal siges at
> efter den første sortering ændres der ikke på koordinaterne).
>
> Da det er rimeligt tidskritisk er jeg ude efter den hurtigste
> sortering, til disse 23 objekter.

Hvis der ikke ændres på koordinaterne efter første sortering, hvorfor
sorterer du så flere gange, når det netop er tidskritisk? Skal det forstås
sådan, at koordinaterne ikke ændres særlig ofte? I så fald, kan det måske
være en mulighed at benytte et flag, som sættes når koordinaterne ændres,
så en ny sortering tvinges igennem. Dette hjælper selvfølgelig ikke, hvis
koordinaterne ændres hele tiden, og fodboldspillerne samtidig holder den
samme indbyrdes rækkefølge.

Venlig hilsen
Christian Larsen

---

> Hvis der ikke ændres på koordinaterne efter første sortering, hvorfor
> sorterer du så flere gange, når det netop er tidskritisk? Skal det forstås
> sådan, at koordinaterne ikke ændres særlig ofte? I så fald, kan det måske
> være en mulighed at benytte et flag, som sættes når koordinaterne ændres,
> så en ny sortering tvinges igennem. Dette hjælper selvfølgelig ikke, hvis
> koordinaterne ændres hele tiden, og fodboldspillerne samtidig holder den
> samme indbyrdes rækkefølge.

Det er korrekt forstået at koordinaterne ikke vil skifte særligt tit, og den
med flaget lyder ikke dumt
I denne test får spillerne ikke nye positioner overhovedet, men det var kun
for at teste effektiviteten af sorteringsmetoden.

-Søren