Beste sorteringsalgoritmer til forskjellig oppgaver

[Bjells]

Hey. Jeg ser over noen gamle eksamener, og lurte på om noen kunne hjelpe meg med et spørsmål.

 

Det handler om å sortere n antall heltall med beste algoritme.

 

Raskeste algoritme for å sortere tallene hvis:

a) ingen av tallene er større enn n

b) ingen av tallene har mer enn 10 sifre

c) har ikke noe informasjon om tallenes størrelse?

 

 

Mine tanker:

Bucketsort som er O(n) må være svaret på b. Jeg tenkte a kunne brukt bucketsort og, men går kanskje ikke med heltalls-tabell på så stor index ( int[1*10^9] )

 

Quicksort / flettesortering er vel de raskeste ellers. Men jeg aner ikke hvem som er best på a og b.

 

Quicksort har jo forventet kjøretid O(nlogn), verste O(n^2).

Flettesortering har alltid O(nlogn).

 

Noen som har tips eller ideer?

[torbjørn marø]

Synes oppgaven er litt rar Om man ikke kjenner n så er det ingen forskjell på a og c. Om n er <= 9999999999 så er det ingen forkjell på a og b.

 

"beste algoritme" er også relativt - algoritmene har ulike fordeler og ulemper. Det kan hende minnebruk er et issue, og da kan bucket sort være uaktuelt.

 

Det sies heller ikke om tallenes distribusjon er kjent.

 

Generelt er Heapsort en flott allgoritme, men det var kanskje ikke pensum?

 

På sånne oppgaver gjelder det først og fremst å tenke hva sensor/lærer er ute etter, ikke å finne det korrekte svaret

[Bjells]

Jeg synes også oppgaven er litt rar. Med beste så mener jeg kjøretid, og er nok i O-notasjon.. Og da blir de fleste like.

 

Og det er litt rart om svarene er like på a og c eller a og b. Da man skal beskrive /implementere de for hver oppgave.

 

Heapsort kan jeg, men den er litt mer stress å implementere enn bucket eller quicksort

 

Buckersort bruker O(n+r) plass? Ikke så ille. Og har mye bedre kjøretid enn quick og heap.

 

Akkurat nå ville jeg gått for bøtte på a og b, og heap på c

Men kan spørre foreleser.

[Gjest Slettet+9871234]

Buckersort bruker O(n+r) plass? Ikke så ille. Og har mye bedre kjøretid enn quick og heap.

Radix sort http://en.wikipedia.org/wiki/Radix%5Fsort og telle sortering http://en.wikipedia.org/wiki/Counting%5Fsort går vel også i lineær tid om de kan brukes.

 

Lenker:

 

http://stackoverflow.com/questions/749585/sorting-in-linear-time

 

http://drdobbs.com/architecture-and-design/184404062

 

Generelt søk ved slike algoritme problemer:

 

fastest sorting algorithm site:www.wolfram.com

Endret 16. november 2011 av Slettet+9871234

[torbjørn marø]

Og det er litt rart om svarene er like på a og c eller a og b. Da man skal beskrive /implementere de for hver oppgave.

Enig. Men du kan påpeke for foreleseren at selv om man ikke har noen informasjon om tallene ©, så vil ingen tall være større enn n (a). I prinsippet vil jeg påstå at det egentlig ikke er noen forskjell på case a, b, og c, annet enn hva som er praktisk med dagens hardware.

 

Og siden det er lenge siden studiene så er det praksis jeg er mest opptatt av. Og da er realitetene at CPU'en er rask, mens minne ofte kan bli en issue ved store datamendger. Det betyr at mengden data er mere avgjørende for valg av algoritme enn hvordan dataene ser ut. Å bruke en algoritme med forholdsvis høy minnekompleksitet (som bucket sort har i forhold til in-place algoritmer) blir uholdbart om dataene ikke får plass i primærminnet.

[Gjest Slettet+9871234]

Og siden det er lenge siden studiene så er det praksis jeg er mest opptatt av. Og da er realitetene at CPU'en er rask, mens minne ofte kan bli en issue ved store datamendger. Det betyr at mengden data er mere avgjørende for valg av algoritme enn hvordan dataene ser ut. Å bruke en algoritme med forholdsvis høy minnekompleksitet (som bucket sort har i forhold til in-place algoritmer) blir uholdbart om dataene ikke får plass i primærminnet.

Men der er stor forskjell i kjøretid på en algoritme som går i nLog(n) og en som går i kvadratisk, nxn tid som for eksempel boble sortering. Radix sortering og telle sortering går enda raskere siden de kjører i lineær n tid.

 

Om minne er et problem for gigantiske data strukturer, bør data leses inn i blokker (streaming) og ikke fullstendig. Da kan man muligens uten at jeg har sjekket det kombinere radix og telle sortering med en kvasi flette (merge) sortering. Man bruker altså radix eller telle sortering på datablokken som er lest inn. Når blokken er sortert, skrives den til fil og neste blokk sorteres og og skrives til fil. Til slutt er det bare og flette sammen de sorterte blokkene. Men med dagens maskiner med 6 Gb og mer som standard minne skal man ha store datastrukturer om denne metoden må benyttes. Merk at data må ha en viss struktur om telle eller radix sortering skal kunne benyttes.

 

Som så ofte en bok som underbygger det jeg sier (min peronlige PHP XML favoritt kilde): http://www.apress.com/9781590596333

 

(Selv om den opprinnelige posten er postet i Java forumet gjelder samme problemstilling i Java som i PHP). Derfor:

 

Kapittel 11 "Effective and Eficient Processing", spesielt avsnittet "Comparing Individual Parsers" som sammenligner effektiviteten til tre baserte og "streaming parsers". Se tabell 11-1 og 11-2. Tabell 11-2 sammenligner minne bruken til SimpleXML (trebasert) som brukte 85.6 Mb minne og XMLReader (streaming) som brukte 177 Kb minne i det rapporterte eksperimentet.

 

Se også:

http://www.sitepoint.com/forums/showthread.php?494734-Central-Book-reference-Robert-Richards-Pro-PHP-XML-and-Web-Sevices.

 

Ytterligere informasjon, Google:

 

pro php xml and web services "kgun site:www.sitepoint.com"

 

Mine tanker:

Bucketsort som er O(n) må være svaret på b.

Ja, kan hende siden bøttesortering også er en av de tre algoritmene jeg husker som går i lineær tid. Av to algoritmer

 

O(Kn) og O(kn) der k < K velges under ellers konstant forhold (ceteris paribus) den siste.

 

Når kjøretiden er redusert til et minimum, består ofte alogritmeutvikling i å finne en mindre konstant foran kjøretiden.

Endret 16. november 2011 av Slettet+9871234

[Kiff]

Vær oppmerksom på at det er en del parametere til JVMen som kan brukes til å angi hvor mye minne den skal bruke og til hva. Det er ikke sikkert den default bruker det ditt program "trenger" eller hva ditt system har tilgjengelig.

 

De nøyaktige innstillingene kan variere fra jvm til jvm, så du må nesten sjekke dokumentasjonen til din JVM.

[Bjells]

Svaret de forventet på eksamen :

a) bøttes-sortering

b) Radix-sort

c) Merge-sort

[g6wkFV6yfl_]

Hvis det er bøttesortering de mener så er det jo direkte feil. Om n er 1, så er minus uendelig fortsatt mindre enn n, men bøttesortering kan ikke sorte disse (forutsetter uendelig minne). Tipper de mener naturlige tall, da er det riktig..

 

 

Og det er litt rart om svarene er like på a og c eller a og b. Da man skal beskrive /implementere de for hver oppgave.

Enig. Men du kan påpeke for foreleseren at selv om man ikke har noen informasjon om tallene ©, så vil ingen tall være større enn n (a). I prinsippet vil jeg påstå at det egentlig ikke er noen forskjell på case a, b, og c, annet enn hva som er praktisk med dagens hardware.

Forskjellen er vel at A kan sorteres i O(n+N), og C i O(nlogn). Så lenge N < nlogn så vil O(n+N)-algoritmen være best. Som sagt, så kan bøttesortering uansett ikke sortere mengden av naturlige tall da dette forutsetter uendelig minne.

Endret 22. november 2011 av formkake

[ZeroS]

Forskjellige sorterings algoritmer, med forklaring Har kan man se forskjellige sorterings algoritmer, mens de jobber. Litt grei side for å forstå hvordan de jobber, pluss detaljert forklaring om de forskjellige,