28

I've asked this before HERE, however I wish to have the explanation of quickselect (based on quicksort) simplified further. The previous question I asked included some example code (so you know what I'm on about).

I was wondering if anyone anywhere at any point had summarised the rules and guidelines of quickselect as a game, where one can learn how the algorithm works by following easily understood rules that can be applied to let's say a deck of cards or numbers on bits of paper.

I think a simplified explanation of the quickselect algorithm would be paramount to me understanding how it works, as still the tutorials and explanations I've received are difficult to grasp and visualise. Even the videos on youtube that turns quicksort into a dance haven't helped greatly.

Thanks in advance Stack, you've been a great help so far.

Community
  • 1
  • 1
Edge
  • 2,456
  • 6
  • 32
  • 57
  • What *exactly* don’t you understand? – Gumbo Jun 02 '12 at 10:01
  • The concept of a pivot, and how it's repeatedly chosen throughout the recursion, and how lists are therefore split and how each sublist is manipulated. – Edge Jun 02 '12 at 10:04
  • The pivot is just a point in the list you select to help your recursion (say the first item in your unsorted list). This provides randomness to the two halves of the list you will get, so it is more likely you get an even distribution between the two halves. – josh shadowfax Jun 02 '12 at 10:06
  • But is the pivot the point where the list splits? – Edge Jun 02 '12 at 10:07
  • Are you familiar with the [divide and conquer algorithm principle](http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm)? Because quick sort/select does nothing else. – Gumbo Jun 02 '12 at 10:08
  • I'd be curious if anyone ever summarised quicksort into a simple game you can play with a card deck though. I wonder... Anyway, I'll take another look at that principle – Edge Jun 02 '12 at 10:09
  • Your quick select algorithm is actually better known as [binary search algorithm](http://en.wikipedia.org/wiki/Binary_search_algorithm). Maybe that will help you. – Gumbo Jun 02 '12 at 10:15
  • I was under the impression quickselect and binary search were two seperate and different algorithms. – Edge Jun 02 '12 at 10:30
  • From what I've read, quickselect and binary search differ in that binary uses a midpoint as the 'pivot', while quickselect uses another function to calculate a pivot. Am I on the right track? – Edge Jun 02 '12 at 10:50
  • You are correct, quickselect and binary search are two different algorithms. Binary search looks for a target value in an ordered collection by repeatedly dividing the search range in half. Quickselect reorders (modifies) a collection to place _one element_ into a specific position (index) as if the entire collection were sorted. It very quickly finds the nth element. – Blastfurnace Jun 02 '12 at 15:57

1 Answers1

160

You walk into a gymnasium containing 200 children. It is September 8th, so you have a burning desire to find the 98th shortest child. You know that you could line them all up from shortest to tallest, but that would take forever. "I know", you think, "I could use QUICKSELECT!"

You walk out into the crowd, close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at one of the children, Peter Pivot. You say, "Quickly! Everybody shorter than Peter, come stand over here. And everybody taller than Peter, go stand over there. If you're the same height as Peter, you can go into either group."

The children shuffle around, and soon they are standing in the two groups. You count and find 120 children in the shorter group, and 79 children in the taller group. You know the 98th shortest child must be in the shorter group, so you tell Peter and the 79 taller children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Peter's sister, Paula Pivot. You say, "Quickly! Those of you who are still standing. If you're shorter than Paula, come stand over here. If you're taller than Paula, go stand over there. If you're the same height, you can go into either group."

The children shuffle around, and soon they are standing in the two groups. You count and find 59 children in the shorter group, and 60 children in the taller group. You know the 98th shortest child must be in the taller group, so you tell Paula and the 59 shorter children to sit in the bleachers.

You again close your eyes, stick out your finger, and spin around three times. When you open your eyes, you are pointing directly at Paula's cousin, Prudence Pivot. You say, "Quickly! Those of you who are still standing. If you're shorter than Prudence, come stand over here. If you're taller than Prudence, go stand over there. If you're the same height, you can go into either group."

The children shuffle around, and soon they are standing in the two groups. You count and find 37 children in the shorter group, and 22 children in the taller group. You know that Paula and 59 other shorter children are sitting on the bleachers. Along with the 37 shorter children still standing, you know that a total of 97 children are shorter than Prudence. Therefore, Prudence is the 98th shortest child!

Quickselect FTW!

Chris Okasaki
  • 4,875
  • 1
  • 20
  • 19
  • 19
    I'm not sure which I am more of right now - Laughing or feeling informed. That was quite possibly the most amazing story I've ever read, and absolutely the best and most easily understood explanation of the algorithm. You sir, deserve a very shiny medal. :D – Edge Jun 02 '12 at 14:07
  • 1
    So this tactic would assume that the children (data list) is unsorted? So each child must compare him/herself to the pivot before moving to their group? – Edge Jun 02 '12 at 14:22
  • 15
    Yes. For QuickSelect, you always assume the data is unsorted, because if it was already sorted, you could just go directly to the desired slot. – Chris Okasaki Jun 02 '12 at 14:50
  • Whats the complexity of quickselect? – LoveMeow Apr 05 '17 at 13:09
  • 1
    @LoveMeow Average of O(n) but a worst case of O(n^2) – Pier-Alexandre Bouchard Apr 11 '17 at 15:22