Skip to content

Instantly share code, notes, and snippets.

@ionox0
Last active August 29, 2015 14:20
Show Gist options
  • Save ionox0/f82ec6f49bc9560cbec2 to your computer and use it in GitHub Desktop.
Save ionox0/f82ec6f49bc9560cbec2 to your computer and use it in GitHub Desktop.
insertion sort vs quicksort
var items = [1, 2, 5, 134, 234, 324, 234, 324, 23, 234, 23, 234, 234, 523, 523, 235, 235, 23, 235, 2354, 2354, 23, 45, 23, 4, 2, 7, 4, 67, 3];
console.time('insertionsort');
console.log(insertionsort(items));
console.timeEnd('insertionsort');
console.time('quicksort');
console.log(quicksort(items, 0, items.length-1));
console.timeEnd('quicksort');
function insertionsort(cards){
var sorted = [];
for (var i = 0; i < cards.length; i++){
for (var j = 0; j <= sorted.length; j++){
if (cards[i] < sorted[j]) {
sorted.splice(j, 0, cards[i]);
break;
}
else if (j === sorted.length) {
sorted.push(cards[i]);
break;
}
}
}
return sorted;
}
///////////
function quicksort(items, left, right) {
var index;
if (items.length > 1) {
index = partition(items, left, right);
if (left < index - 1) {
quicksort(items, left, index - 1);
}
if (index < right) {
quicksort(items, index, right);
}
}
return items;
}
function partition(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)],
i = left,
j = right;
while (i <= j) {
while (items[i] < pivot) i++;
while (items[j] > pivot) j--;
if (i <= j) {
swap(items, i, j);
i++;
j--;
}
}
return i;
}
function swap(items, firstIndex, secondIndex){
var temp = items[firstIndex];
items[firstIndex] = items[secondIndex];
items[secondIndex] = temp;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment