Quicksort-spelet

In this thesis, we introduce a new combinatorial game called the Quicksort game. This game is played on a sequence of numbers, and players move by pivoting around a number in the manner of the familiar Quicksort algorithm. We also examine a variation on the Quicksort game called Pseudo-Quicksort. These games have some very interesting properties: Quicksort games are all-small, while Pseudo-Quicksort games are numbers. We solve Quicksort for a particular family of sequences, and describe an algorithm for converting certain Pseudo-Quicksort games into Hackenbush graphs.I detta examensarbete introduceras ett nytt kombinatoriskt spel, Quicksort-spelet. Spelet spelas på en sekvens av tal, där spelarna gör drag genom att välja ett pivotelement och sedan omordna sekvensen på samma vis som i Quicksortalgoritmen. Vi undersöker även Pseudo-Quicksort, en variant av Quicksortspelet. Dessa två spel har en del intressanta egenskaper: Quicksortspel är infinitesimala, men Pseudo-Quicksortspel är tal. Vi löser Quicksort för en viss mängd sekvenser, samt beskriver en algoritm som omvandlar vissa Pseudo-Quicksortspel till Hackenbush-grafer