Change search
ReferencesLink to record
Permanent link

Direct link
The Quicksort Game
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2016 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Quicksort-spelet (Swedish)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
TRITA-MAT-E, 2016:24
National Category
URN: urn:nbn:se:kth:diva-188170OAI: diva2:935354
Subject / course
Educational program
Master of Science - Mathematics
Available from: 2016-06-10 Created: 2016-06-08 Last updated: 2016-06-10Bibliographically approved

Open Access in DiVA

fulltext(518 kB)24 downloads
File information
File name FULLTEXT01.pdfFile size 518 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)

Search outside of DiVA

GoogleGoogle Scholar
Total: 24 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 306 hits
ReferencesLink to record
Permanent link

Direct link