Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
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 inﬁnitesimala, 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.

2016.
Series
TRITA-MAT-E ; 2016:24
Mathematics
Identifiers
OAI: oai:DiVA.org:kth-188170DiVA, id: diva2:935354
Mathematics
Educational program
Master of Science - Mathematics
Examiners
Available from: 2016-06-10 Created: 2016-06-08 Last updated: 2016-06-10Bibliographically approved

Open Access in DiVA

File information
File name FULLTEXT01.pdfFile size 518 kBChecksum SHA-512
703fb45d21964f074aab8f5cf8bd49d9c41cb7803215096e7c89f20329bb9b682e96d6338d7089045e33d7a324edb451bbd2e7d89db4eb77bfdeaa9fddc45415
Type fulltextMimetype application/pdf
By organisation
Mathematics (Div.)
Mathematics

Search outside of DiVA

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
urn-nbn

Altmetric score

urn-nbn
Total: 393 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
v. 2.33.0
| | | |