The best way to understand complex data structures
is to see them in action. This project is developed
in an
interactive animations for a variety of data
structures and algorithms.
Delay Time :
10Array Size :
10
Defination :
Quick sort
t is a divide and conquer algorithm which relies on a
partition operation: to partition an array an element
called a pivot is selected. All elements smaller than
the pivot are moved before it and all greater elements
are moved after it. This can be done efficiently in
linear time and in-place. The lesser and greater
sublists are then recursively sorted. Efficient
implementations of quicksort (with in-place
partitioning) are typically unstable sorts and somewhat
complex, but are among the fastest sorting algorithms in
practice. Together with its modest O(log n) space usage,
quicksort is one of the most popular sorting algorithms
and is available in many standard programming libraries.
The most complex issue in quicksort is choosing a good
pivot element; consistently poor choices of pivots can
result in drastically slower O(n²) performance, if at
each step the median is chosen as the pivot then the
algorithm works in O(n log n). Finding the median
however, is an O(n) operation on unsorted lists and
therefore exacts its own penalty with sorting.
Performance
Best-case Time complexity:
O(nlogn)
Average-case Time complexity:
O(nlogn)
worst-case Time complexity:
O(n²)
Space complexity
worst-case Space complexity:
O(logn)
async function quickSort(arr){
await QS(0,len-1);
async function partition(pivot,left,right){
const pivotValue = arr[pivot];
var partitionIndex = left;
var i = left;
for(var i = left; i < right; i++){
if(arr[i] < pivotValue){
await swapIndex(arr, i, partitionIndex);
await drawArr(arr);
await sleep(time);
partitionIndex++;
}
}
await swapIndex(arr, right, partitionIndex);
await drawArr(arr);
await sleep(time);
return Promise.resolve(partitionIndex);
}
async function QS(left,right){
if(left < right){
const pivot = right;
const partitionIndex = await partition(pivot,left,right);
await QS(left,partitionIndex-1);
await QS(partitionIndex+1,right);
}
return Promise.resolve();
}
}
Designed and built with by The ThunderBolt