Skip to content

Instantly share code, notes, and snippets.

@alpgul
Last active March 23, 2018 13:23
Show Gist options
  • Save alpgul/b9e3873c713710d64c0deed310d5430b to your computer and use it in GitHub Desktop.
Save alpgul/b9e3873c713710d64c0deed310d5430b to your computer and use it in GitHub Desktop.
Quick Sort with Javascript
/*
Best Case:n*logn
Average Case:n*logn
Worst Case:n^2
*/
(function(){
let comparison=0;
let arr2=[28, 31, 43, 97, 49, 11, 33, 71, 41, 80, 86, 38, 53, 54, 7, 67, 96, 52, 29, 25, 56, 77, 73, 42, 62, 84, 21, 68, 2, 44, 9, 94, 66, 78, 6, 57, 20, 89, 1, 55, 65, 85, 51, 23, 70, 32, 12, 27, 18, 90, 4, 82, 5, 35, 58, 69, 22, 83, 37, 61, 79, 34, 81, 30, 72, 95, 91, 48, 88, 46, 3, 26, 60, 39, 17, 24, 74, 99, 10, 16, 87, 98, 76, 13, 36, 45, 59, 100, 50, 93, 19, 75, 92, 40, 8, 47, 14, 15, 63, 64];
let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100];
function swap(items, firstIndex, secondIndex){
let temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
function partition(items, left, right) {
let pivot = items[Math.floor((right + left) / 2)],
i = left,
j = right;
while (i <= j) {
while (items[i] < pivot) {
comparison++;
i++;
}
while (items[j] > pivot) {
comparison++;
j--;
}
if (i <= j) {
comparison++;
swap(items, i, j);
i++;
j--;
}
}
return i;
}
function sort(items, left, right) {
comparison++;
let index;
if (items.length > 1) {
left = typeof left != "number" ? 0 : left;
right = typeof right != "number" ? items.length - 1 : right;
index = partition(items, left, right);
if (left < index - 1) {
sort(items, left, index - 1);
}
if (index < right) {
sort(items, index, right);
}
}
return items;
}
function quick_sort(array){
var start = Date.now();
array= sort(array);
var end = Date.now();
var elapsed = end - start;
console.log("Elapsed Time:"+elapsed);
console.log("Total comparison:"+comparison);
comparison=0;
return array
}
quick_sort(arr2);//Total comparison:894
console.log(quick_sort(arr));
})();
@alpgul
Copy link
Author

alpgul commented Mar 23, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment