QuickSelect

Sometimes we do not need to fully sort our data; we are not going to search for many things so perfectly ordering the data is wasteful. While we may not need the data in order, we still may be interested in finding a particular element (Eg: who came third in that last race?). This is trivial with pre-sorted data - the 3rd smallest element will be element number 3. It is harder when the data is not sorted, and it is impractical to sort 100,000 elements if all we want to know is who came 3rd.

Enter QuickSelect. It is very similar to quicksort, and if you are not already familiar with this algorithm, please read the tutorial for it before continuing with this page. Quickselect works by sorting only the areas it needs to find the desired element. After a quickselect, the data will be roughly sorted and the desired element will be in its correct position. Additionally, all items larger than the target will be to its right, and all items less than the target will be to its left.

To implement a quickselect we just modify a quicksort algorithm. (Changes to the quicksort algorithm are shown in bold)

  1. If the area you're searching has only one element in it, you have found the element you are looking for, so stop searching.
  2. Choose a pivot element (see Selecting a pivot)
  3. Swap the pivot element with the last element
  4. First, the program looks at pointer L and moves it right, checking each element in turn. As soon as it finds an element whose value is greater or equal to the pivot, it stops. It also stops if it passes pointer R.
  5. Now the program moves pointer R left until it finds an element whose value is less than or equal to the pivot, or it has passed pointer L.
  6. If pointers L and R have not met, swap the 2 elements they point to, and continue from step 3. Otherwise, swap the last element (which is the pivot because of step 1) with the element that pointer L is at.
  7. If the pivot is the element you're looking for, stop searching. If the pivot is to the right (or larger) than the element you're searching for, repeat the quickselect on the left group only, otherwise repeat the quickselect on the right group only.