Nada

LÖSNING TILL DATALOGIÖVNING 10

KÖNSSORTERING

Så här ser det ut (nionde siffran visas). 00001112222233344555666788888999 Sätt vänster pekfinger på första mannen och höger pekfinger på sista kvinnan. Byt dom! Resultat: 00008112222233344555666788881999. För vänster pekfinger åt höger tills det fastnar på en man och höger pekfinger åt vänster tills det fastnar på en kvinna. Byt osv. Håll på tills fingrarna korsas. I vårt exempel blir det då 00008882222288644665553733111999 och saken är klar. Hälften av alla kvinnor och hälften av alla män ligger i fel halva av filen och måste flyttas, så det blir drygt fyra miljoner flyttar.

LÖNAR SEJ SORTERING?

Lönar sej sortering? Ja, i osorterad vektor krävs cirka en halv miljon jämförelser för VARJE sökning, dvs totalt en halv miljard. Sortering med quicksort kräver drygt N log N jämförelser, dvs cirka 30 miljoner. Sedan tar varje binärsökning bara log N jämförelser, dvs tjugotusen totalt. Alla bör veta att log 1000 = 10 och log 1000000 = 20.

SNABBSORTERING

När N växte från tusen till tiotusen tog Tottes sortering 100 gånger så lång tid (urvalssorteringens komplexitet är proportionell mot N i kvadrat) men Tildas bara 13 gånger så lång tid. N log N växer ju från cirka 10000 till cirka 132000. (log 8000 = 13 och log 16000 = 14).

OSVENSK SORTERING

Insättningssortering är bäst när vektorn är nästan rätt sorterad. Quicksort kan bli extra dålig då.

HOPPFULL SORTERING

Alla höjdhopp har höjder från 100 till 250, så det bästa är att först räkna hur många klarade och rivna som finns av varje höjd. Sedan vet man var någonstans i vektorn dom klarade 187-hoppen ska börja (till exempel på index 25893). Det kan vara lämpligt att ha en vektor K så att K[187]=25893 och en vektor R sp att R[147]= 19 om det finns nitton rivna 147-hopp. Sen går man igenom filen en gång till och sätter in varje hopp på rätt plats i vektorn H (som har index från 0 till antalhopp-1). Den här sorteringsmetoden har komplexitet proportionell mot N, men den fungerar bara när det bara finns några stycken olika värden på sorterings- nyckeln. Javakod behövs väl inte, men man kan kanske antyda att det behövs några datastrukturer. En class Jump med plats för data om ett hopp. Och i main:
  final int hmax = 251;
  int[] K = new int[hmax];
  int[] R = new int[hmax];
  for (int h=100; h<hmax; h++) {K[h]=0; R[h]=0;}
  while inte end of file {läs h-hopp från filen, gör K[h]++ eller R[h]++} 
  Summan av alla K[h] och R[h] kallar vi antalhopp.
  Jump[] hopp= new Jump[antalhopp];
  int[] indexK = new int[hmax];
  int[] indexR = new int[hmax];
  indexK[hmax-1]=0; 
  for (int h=hmax-1; h>100; h--) indexK[h-1]=indexK[h]+K[h];
  osv för R. Sen läser man filen igen och om man läser ett klarat h-hopp så
  ska det in i Jump[indexK[h]] varefter man gör indexK[h]++.