1. Welcome to Quicksort Interactive Tutorial.
    Input your own values:
  2. Explore the content of the diagram: move mouse over / tap on the text.
  3. (1) Introduction.
  4. At the top of the diagram, an initial list contains random values (not sorted).
  5. At the bottom of the diagram, a sorted list is the result of the algorithm.
  6. Quicksort uses the concept of pivots to split each list near the middle.
  7. This procedure is repeated until each list has only one value (as described in the next steps).
  8. (2) Details of Quicksort.
  9. For didactic purposes, the pivot is defined as average (of values of a list). For example: the first pivot is the average of the initial list.
  10. Usually, the average is not able to split the list exactly in the middle, but it gets something near that.
  11. At the first level, the initial list is splitted (around the pivot) which results in two lists.
  12. Compared to pivot those two lists have: values smaller than the pivot, and values larger than the pivot.
  13. At the second level, those two lists require their own pivots (that means: two pivots). The split procedure results in four lists.
  14. The list at the left side has the smallest values, the list at the right side has the largest values, and everything else in between.
  15. The algorithm repeats this procedure until each list has the size of only one value. Those values are the result of the sort algorithm.
  16. "Recursive Algorithm" is the name of this kind of repetitive procedure.
  17. (3) Advanced concepts: in-place.
  18. Quicksort is an efficient sort algorithm, and one of the few in-place algorithms (in this category).
  19. In-place means: the algorithm does not require additional storage memory. Given two memory positions, Quicksort exchanges its values.
  20. A naive approach would create (at the split procedure) two lists with the same order of previous iteration.
  21. As a matter of fact, Quicksort does not create any new list, it reuses the same storage space.
  22. So, usually (at the split procedure) the order of equal values is not the same as the previous iteration.
  23. That makes Quicksort an unstable sort algorithm.
  24. (4) Advanced concepts: stable / unstable sort algorithm.
  25. When a list contains two or more values that are exactly the same, how do you compare those values?
  26. In some applications, data with the same value may use additional information (what results in equal values not being the same).
  27. So, a stable / unstable sort algorithm may be relevant, for some applications.
  28. Quicksort can be implemented as a stable sort algorithm, but with some additional storage space.
  29. (5) Advanced concepts: Median.
  30. This tutorial uses average as pivot. But the pivot could have another definition.
  31. The choice of pivot defines the size of each sublist. This can result in undesired unbalanced lists.
  32. The perfect pivot would be the median of a list.
  33. But the effort to calculate the median would make Quicksort slower.
  34. So, in practice, some other value is defined as pivot: as near to the median as possible, and fast to calculate.
  35. Originally in 1959, Tony Hoare implemented Quicksort using the first (or last) element of a list as pivot. The algorithm usually works fine with this choice.
  36. The end.
    Also, visit Mergesort Interactive Tutorial.

This software is open source.

Download pdf slide (not interactive).