Gammel eksamensoppgave - bucket sort

[Gjest]

Hei,

 

Jeg prøver å gjøre en gammel eksamensoppgave i faget Programutvikling ved UiB, men trenger litt input. Dette er en oppgave som ligger litt utenfor det vi har hatt som pensum, så jeg tror den i utgangspunktet prøver å teste for refleksjon og generell forståelse av algoritmisk analyse.

 

Oppgaveteksten er:

 

Under finner du en metode for å sortere String-objekt med eksakt 10 tegn som alle er hentet fra de 26 tegnene i det engelske alfabetet for store bokstaver (’A’..’Z’). En slik sorteringsmetode blir kalt bøtte-sortering (bucket-sort på engelsk). Prinsippet er at en først ser på det siste tegnet til hvert ord (her String-objekt med 10 tegn), dvs i = 9 i metoden. Man legger så hvert av ordene inn til slutt i den bøtten av 26 som tilsvarer verdien til tegnet (dette blir gjort ved LinkedList.add()-metoden som har kompleksitet O(1)). Når dette er gjort tar vi bøttene en for en og legger tilbake i String-arrayen vår. Arrayen er nå sortert etter siste tegn i String-objektene, dvs si at alle strenger som slutter på ’A’ kommer før alle strenger som slutter på ’B’ etc. Når vi gjentar prosessen, men nå med nest siste tegn (i = 8) som kriterium for valg av bøtte, vil vi få sortert dataene etter de to siste tegnene. Neste iterasjon vil vi har sortert på tre tegn, så fire tegn, etc. Vi gjentar helt til i = 0. Da vil vi fordele dataene i bøtter etter tegnet som står i første posisjon i hvert ord. Resultatet er at arrayen help til slutt blir sortert.

 

 

Kode:

public static String[] bucketSort(String[] data) {
//kopier dataene
 String[] help = data.clone();
 for (int i = 9; i &--#62;= 0; i--) {
  // løkke for hver tegnposisjon i streng-objektene
  // opprett 26 tomme bøtter representert ved LinkedList
  LinkedList&--#60;String&--#62;[] buckets = (LinkedList&--#60;String&--#62;[])new LinkedList[26];
  for (int j = 0; j &--#60; 26; j++)
buckets[j] = new LinkedList&--#60;String&--#62;();
  // finn bøtteIndeks og plasser streng i riktig bøtte
  for (int k = 0; k &--#60; help.length; k++) {
// Finn bøtte-indeks. Ja! det er lov å bruke minus på char-verdier i Java.
int bucketIndex = (int)(help[k].charAt(i)-'A');
buckets[bucketIndex].add(help[k]);
  }
  // flytt dataene fra bøttene og tilbake til arrayen
  // av strenger.
  int helpIndex = 0;
  for (int j = 0; j &--#60; 26; j++)
for (String el : buckets[j]) {
 help[helpIndex] = el;
 helpIndex++;
}
 }
 return help;
}

 

 

Spørsmål:

 

Hva er, i O-notasjon, den algoritmiske kompleksiteten til bucketSort uttrykt ved N der N er tallet på element i data-arrayen? Argumenter for svaret ditt. I hvilke situasjoner tror du at det passer best å bruke bøtte-sortering?

 

 

Foreløpig svar (veldig foreløpig):

 

Når jeg leser koden ser jeg at den første for løkken utføres 10 ganger.

 

For hver iterasjon flyttes strenger fra Array til Array av LinkedList, for så å bli flyttet tilbake til Array (dvs. 2N).

 

Etter 10 ganger er alle strengene fullstendig iterert over char for char. Dvs. N.

 

Altså, i denne koden: O(21N) (dvs. 10*2N+1N)...

 

På Wikipedia står følgende om Bucket Sort

Worst case performance O(n^2)

Average case performance O(n+k)

Worst case space complexity O(n*k)

 

Kan det være slik her at kompleksiteten er O(n*k) der k = iterasjonene i den første for-loopen? Eller er det noe annet her som jeg har misforstått?

 

Ellers så ser jeg vel ikke helt hva som er fordelen med BucketSort vs. O(n log n) sorteringsalgoritmer som TreeSort og MergeSort. Har dere noen tanker om når det faktisk passer seg å bruke BucketSort?

 

 

På forhånd takk.

Endret 20. september 2012 av Gjest

[Persn]

Kan det være slik her at kompleksiteten er O(n*k) der k = iterasjonene i den første for-loopen? Eller er det noe annet her som jeg har misforstått?

 

k er en konstant for alle linjer kode som skjer utenfor ei for-løkke, for hver linje kode som skjer en gang i ei algoritme får du k = k + 1

F.eks

public int algoritme(){
 int tall = 0;// k++
 for(int i=0/*k++*/;i<tall.length/*k++*/;i++/*n++*/){
 tall++;//n++
 }
 return tall;//Mener å huske at return-setninger ikke er med i kompleksitet, men husker ikke sikkert. Om jeg tar feil blir det isåfall k++ her også.
}

På samme måte ser vi at alt som skjer innafor for-løkka blir n = kode i iterasjone i for-loopen.

Eksempelkoden gir da kompleksiteten: n + k = 2n + 3

 

Jeg er bare en noob selv på kompleksitet, så tror ikke jeg kan hjelpe så mye mer enn det, men håper jeg fikk forklart hva k er for noe ivertfall

[jonny]

Den ytre løkka har 10 iterasjoner.

Inne i denne løkka har du først en løkke som kreerer 26 LinkedList-objekter (26 iterasjoner).

Etter dette kommer en løkke som itererer N ganger.

Til sist kommer en løkke med en ny indre løkke, totalt antall iterasjoner er her N.

 

Til sammen blir dette 10 * (26 + N + N) = 260 + 20*N operasjoner.

 

Så selv om du har ingen eller svært få elementer i lista som skal sorteres, gjøres minst 260 operasjoner. Faktisk så kreerer du 260 LinkedList-objekter, som nok er relativt "dyrt" mtp. tidsbruk...

Endret 20. september 2012 av jonny

[Gjest]

k er en konstant for alle linjer kode som skjer utenfor ei for-løkke, for hver linje kode som skjer en gang i ei algoritme får du k = k + 1

F.eks

 

Takk for svar. Da vet jeg hva k er og kan (heldigvis) justere mitt resonnement deretter

[Gjest]

Til sammen blir dette 10 * (26 + N + N) = 260 + 20*N operasjoner.

 

Så selv om du har ingen eller svært få elementer i lista som skal sorteres, gjøres minst 260 operasjoner. Faktisk så kreerer du 260 LinkedList-objekter, som nok er relativt "dyrt" mtp. tidsbruk...

 

Takk Ja, du har helt rett i at det er mange operasjoner for å opprette disse LinkedList objektene. Slik jeg forstår det blir det litt utenfor scopet for svaret i O-notasjon (gi beskjed hvis jeg tar feil:)), men det er sikkert lurt å nevne som en bakdel med å bruke denne strukturen.

 

Jeg slet litt med å generalisere svaret mitt i O notasjon (vi har fått beskjed om å se bort fra konstanter i dette kurset), men etter å ha lest linken under tenker jeg at det er en O(n) operasjon. Veksten vil jo alltid være lineær.

 

http://stackoverflow...-is-linear-time

 

Men jeg skjønner fortsatt ikke poenget med å bruke denne sorteringsalgoritmen framfor O(log n) sorteringsalgoritmene. En forutsetning er at den må brukes på objekter av en gitt størrelse (her: et streng objekt med 10 char).

[Persn]

Har ett lite inntrykk av du henger deg opp i kompleksiteten til de forskellige alogritmene, her er det ikke viktig å tenke på hvor effektiv og rask en algoritme er, men heller hva de faktisk gjør for noe. La oss sammenligne merge-sort og bucket-sort

 

Du har tidligere nevnt f.eks merge-sort som funker slik at den tar to samlinger av en lik forekomst og sorterer de etter ett kriterie, si vi har to int-tabeller med ulike tall, og vi vil ha tallene i rekkefølge på ett fra begge tabellene. Da gir det mening å bruke merge-sort.

 

La oss ta ett eksempel hvor vi kan bruke bucket-sort, men jeg bruker ett eksempel fra dagliglivet istedet. Du jobber på ett lager og har en pall som er full av frukt, sjefen din vil at du skal telle alle bananer, epler, osv. for å sjekke at dere har mottatt riktig antall. Gir det ikke da mening å sortere hver frukt hver for seg og telle dem etterpå? Dette er sånn bucket-sort funker i veldig grove trekk, men hvordan ville du da anvendt den samme sorteringa med merge-sort?