QuickSort is a method of a sorting algorithm that uses pivots and partitions to sort an array of information. It has an O(n log n) runtime but in a worst-case scenario an O(n²) runtime.
The main way QuickSort is seen implemented is using a recursive solution. The key is that is the algorithm will continually take smaller portions of the arr to create its pivots on. Each time a pivot is set the algorithm will check every element in that part of the array and shift it either to the left or right of the pivot. As time goes on the portions of the array that you are working on will get smaller till there is only one element left to deal with.
function quickSort(arr, low, high) { if (low<high) { pivot_i = partition(arr, low, high) quickSort(arr, low, pivot_i - 1) quickSort(arr, pivot_i + 1, high) } return arr}function partition(arr, low, high) { let pivot = arr[high] let p_index = low let i = low while (i<high) { if (arr[i] < pivot) { let temp1 = arr[i] arr[i] = arr[p_index] arr[p_index] = temp1 p_index++
} i++ } arr[high] = arr[p_index] arr[p_index] = pivot return p_index}
The reason their can be an O(n²) runtime is that the algorithm checks every element and partitions it. If the array is already ordered and you run the algorithm nothing will move and the partitions will be extremely uneven. One side will have every element, not including the pivot element. Thus you will keep creating uneven partitions thus checking every element n² times.
