Springen naar inhoud

Boeken sorteren


  • Log in om te kunnen reageren

#1

*_gast_PeterPan_*

  • Gast

Geplaatst op 15 augustus 2009 - 12:24

Bubblesort.

In het boekenschap staan naast elkaar 30 boeken van louter verschillende auteurs. Een bibliothecaris bekijkt het eerste en tweede boek van links en verwisselt ze precies dan als ze niet in alfabetische volgorde van auteur staan. Daarna doet hij hetzelfde met het tweede en derde boek van links, enz. Op deze manier doorloopt hij de rij boeken in totaal drie maal van links naar rechts. Wat is de kans dat de hele rij boeken dan alfabetisch geordend is?

Veranderd door PeterPan, 15 augustus 2009 - 12:28


Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Gesp

    Gesp


  • >250 berichten
  • 339 berichten
  • Ervaren gebruiker

Geplaatst op 17 augustus 2009 - 21:10

Klein. Als boek B1 op positie 5 (of hoger) staat komt het niet goed. Als B2 op positie 6 (of hoger) staat komt het niet goed. Etc. Want boeken kunnen per ronde sorteren slechts 1 positie naar links verschuiven. Dus bij 3 rondes maar 3 posities.

De kans dat initieel B1<5 Ťn B2<6 Ťn B3<7 ... etc, is in mijn snelle berekening 5.79742E-09 (want 4/30 * 5/30 * 6/30 ...). En dat is de bovengrens, want er zijn nog wel meer nietsorteerbare boekenschappen te bedenken.

(Het zou een stuk beter worden als je ook een keer de andere kant op sorteert).

#3

*_gast_PeterPan_*

  • Gast

Geplaatst op 18 augustus 2009 - 08:09

Als boek B1 op positie 5 (of hoger) staat komt het niet goed. Als B2 op positie 6 (of hoger) staat komt het niet goed. Etc. Want boeken kunnen per ronde sorteren slechts 1 positie naar links verschuiven. Dus bij 3 rondes maar 3 posities.

Dit is een belangrijke constatering.
Met behulp van deze constatering zou je een vermoeden kunnen krijgen over de voorwaarde waaraan de boekenrij moet voldoen om na 3 sorteerronden alfabetisch op orde te zijn.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures