Quick3 sort,is similar to the Quick sort. However, its more efficient when there are lot of duplicate elements in the given array. The idea is to divide the array in three parts rather than two. Lets say P is the pivot index. The first part contains all the numbers which are less than P, the second part contains number equal to P and the last part contains numbers which are greater than P.
function quick3(arr,start,end) {
let i = end, j = end, high = start;
let pivot = arr[start];
while(high <= i) {
if(arr[i] == pivot) {
i--;
}
else if(arr[i] < pivot) {
let temp = arr[high];
arr[high] = arr[i];
arr[i] = temp;
high++;
}
else {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i--;j--;
}
}
if(start < high-1)
quick3(arr,start,high-1);
if(j+1 < end)
quick3(arr,j+1,end);
return;
}
function quick3Main(arr){
start = 0;
end = arr.length - 1;
quick3(arr,start,end);
return arr;
}
Best Case : Ω (n log(n))
Average Case : θ (n log(n))
Worst Case: O (n^2)
O(log(n))
** where n is the length of the array