Algoritm för boksortering

Vi har ju en massa böcker som nu är i oordning. Oordningen är inte fullständig, men tillräcklig för att man ska ha svårt att hitta det man letar efter. Eftersom jag inte tror att det är genomförbart att göra en total sortering eftersom det skulle bli besvärligt att plocka ut allting och sedan sätta tillbaks allting. Eftersom vi inte kan ha högar liggande så måste det gå ganska snabbt också. Jag har därför funderat på hur man kan sortera lite i taget och i slutändan ha sorterat allt.

En förutsättning är att man har en sorteringsnyckel, men vilken man använder är inte viktig bara man använder samma hela tiden. Så här skulle algoritmen se ut:

  1. Plocka ut alla böcker på en hylla och sortera in dem enligt nyckeln på samma hylla.
  2. Om ett bokverk sträcker sig över mer än en hylla gör man samma sak med de hyllor som berörs.
  3. När alla hyllor är sorterade så tömmer man den hylla där man vill att samlingen ska börja och hämtar de böcker som ska in först enligt sorteringsnyckeln och sorterar in dem.

Så långt tycker jag att det verkar vara ett vettigt arbetssätt, men vad ska man göra med böckerna man plockar ut i steg 3? Kommer det att skapas högar då eftersom det bara  blir små luckor på de hyllor där man hämtar böckerna? Jag har funderat på om man efter att ha sorterat alla hyllor(=hyllplan) rätt ska sortera alla bokhyllor rätt på samma sätt, men jag tror inte det blir effektivare. Jag tror att man behöver en sorteringsbuffert(=tomma hyllor) i en bokhylla där man kan ställa upp de böcker som man har plockat ut. Den kommer att byggas på i början men allt eftersom hyllorna töms på böcker som sorterats in så ger det plats även där för att ställa de böcker som man plockar bort från en hylla. Det är förmodligen bara den första hyllan man tömmer som är full, sedan kommer man ha tagit en eller flera böcker från hyllan.

På det här sättet (med en buffert) kan man säkert lyckas sortera allt och dessutom kunna avbryta sorterandet utan att det finns högar som är i vägen. Det går säkert att räkna på hur stor buffert i hyllmeter som kan behövas genom att simulera sorteringen.

Bookmark and Share

En reaktion på “Algoritm för boksortering

  1. Pingback: B(l)o G Strömberg » Motböckerna

Kommentera

E-postadressen publiceras inte. Obligatoriska fält är märkta *

Följande HTML-taggar och attribut är tillåtna: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>