highschool/Grade 10/Computer Science/ICS4U1/Sorting Methods/Quick Sort.md

Quick Sort

What exactly is quicksort

• take an element as a pivot, move all greater elements than pivot to one side and the lesser elements to the other side. Keep partioning until array is sorted. It is a divide and conquer algorithm
• Known as the queen of all sorts.

What are the steps of the quicksort algorithm

• Pick a pivot point
• Partion the list by using the pivot point, move lesser elements to the left and greater elements to the right
• Repeat until list is sorted

What is the partiion method?

• Given ana array and an element \(`x`\), put elements \(`\gt x`\) to the right and \(`\le x`\) to the left. This should be done in linear time
• You can either pick the last, first, middle or random element as the pivot

Pros and Cons

• Pros
  • Inplace \(`O(1)`\) memory
  • Relative fast time complexity most of the time \(`O(n \log n)`\)
• Cons
  • Can result in \(`O(n^2)`\) worst time complexity
  • Hard to implement