# Quick Sort Visualization

Iteration: 0
Indexes diapason: 0 - 9
Pivot index: 4.5

## What is Quick Sort Algorithm?

Quicksort is an in-place sorting algorithm. Developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be somewhat faster than merge sort and about two or three times faster than heapsort.

Quicksort is a divide-and-conquer algorithm. It works by selecting a ‘pivot’ element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort. The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.

Quicksort is a comparison sort, meaning that it can sort items of any type for which a “less-than” relation (formally, a total order) is defined. Efficient implementations of Quicksort are not a stable sort, meaning that the relative order of equal sort items is not preserved.

Mathematical analysis of quicksort shows that, on average, the algorithm takes {\displaystyle O(n\log {n})}O(n\log {n}) comparisons to sort n items. In the worst case, it makes {\displaystyle O(n^{2})}O(n^{2}) comparisons.

Source: Wikipedia

## JavaScript implementation

``` function quickSort(arr, left, right) {
var i = left;
var j = right;
var tmp;
var pivotidx = (left + right) / 2;
var pivot = parseInt(arr[pivotidx.toFixed()]);
/* partition */
while (i <= j)
{
while (parseInt(arr[i]) < pivot)
i++;
while (parseInt(arr[j]) > pivot)
j--;
if (i <= j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
}

/* recursion */
if (left < j)
this.quickSort(arr, left, j);
if (i < right)
this.quickSort(arr, i, right);

return arr;
} ```