Quicksort
Learn about quicksort, an efficient recursive algorithm for sorting arrays or lists of values.
Start
Key Concepts
Review core concepts you need to learn to master this subject
Quick Sort General
Quick Sort General
Quicksort is a method for sorting an array by repeatedly partitioning it into sub-arrays by:
- Selecting an element from the current array. This element is called the pivot element, and in our implementation we used the mid element.
- Comparing every element in the array to the pivot element, swap the elements into sides greater than and less than. The partition point in the array is where we guarantee everything before is less and everything after is greater than.
- Repeating this process on the sub-arrays separated by the partition point. Do this until a sub-array contains a single element. When the partitioning and swapping are done, the arrays are sorted from smallest to largest.
The worst case runtime for quicksort is O(N^2) and the average runtime for quicksort is O(N logN). The worst case runtime is so unusual that the quicksort algorithm is typically referred to as O(N logN)“
Quicksort: Conceptual
Lesson 1 of 2
- 1Quicksort is an efficient recursive algorithm for sorting arrays or lists of values. The algorithm is a comparison sort, where values are ordered by a comparison operation such as > or <. Quick…
- 2The key to Quicksort’s runtime efficiency is the division of the array. The array is partitioned according to comparisons with the pivot element, so which pivot is the optimal choice to produce su…
- 3Quicksort is an efficient algorithm for sorting values in a list. A single element, the pivot, is chosen from the list. All the remaining values are partitioned into two sub-lists containing the v…
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory
