Skip to content

Instantly share code, notes, and snippets.

@stevethedev
Created April 13, 2018 16:26
Show Gist options
  • Save stevethedev/81be7d4990f617b80c9c6599bc4586a2 to your computer and use it in GitHub Desktop.
Save stevethedev/81be7d4990f617b80c9c6599bc4586a2 to your computer and use it in GitHub Desktop.
A Variety-Sort in ES6
function varietySort(array) {
// 1. Cut the list in half
const [ left, right ] = varietySort.split(array);
varietySort.rejoin(
array,
varietySort.left(left),
varietySort.right(right)
);
return array;
}
varietySort.split = function(array) {
const left = array.splice(0, array.length / 2);
const right = array.splice(0);
return [ left, right ];
}
varietySort.rejoin = function(array, left, right) {
while(left.length && right.length) {
if (left[0] < right[0]) {
array.push(left.shift());
} else if (right[0] < left[0]) {
array.push(right.shift());
}
}
if (left.length) {
[].push.apply(array, left);
}
if (right.length) {
[].push.apply(array, right);
}
return array;
}
// Bubble-sort until the right-half of this array is sorted
varietySort.left = function(array) {
for (let j = array.length; j > (array.length / 2) + 1; --j) {
for (let i = 1; i < array.length; ++i) {
if (array[i] < array[i - 1]) {
[ array[i], array[i - 1] ] = [ array[i - 1], array[i] ];
}
}
}
const [ left, right ] = varietySort.split(array);
return varietySort.rejoin(
array,
varietySort.left.left(left),
varietySort.left.right(right),
);
};
varietySort.left.left = function(array) {
const from = array.splice(0, array.length);
for (let i = 0; i < from.length; ++i) {
let j = 0;
while (j < array.length && from[i] > array[j]) {
j++;
}
array.splice(j, 0, from[i]);
}
return array;
}
varietySort.left.right = function(array) {
return array;
}
// Cut this half in half
varietySort.right = function(array) {
const [ left, right ] = varietySort.split(array);
return varietySort.rejoin(
array,
varietySort.right.left(left),
varietySort.right.right(right),
);
}
varietySort.right.left = function(array) {
const shuffle = () => {
for (let i = array.length - 1; i > 0; --i) {
const j = Math.floor(Math.random() * (i + 1));
[ array[i], array[j] ] = [ array[j], array[i] ];
}
};
for (let i = 1; i < array.length; ++i) {
if (array[i] < array[i - 1]) {
i = 0;
shuffle();
}
}
return array;
}
varietySort.right.right = function quickSort(array, low = 0, high = array.length - 1) {
const partition = (low, high) => {
let pivot = array[high];
let i = low - 1;
for (let j = low; j <= high - 1; ++j) {
if (array[j] <= pivot) {
++i;
[ array[j], array[i] ] = [ array[i], array[j] ];
}
}
[ array[i + 1], array[high] ] = [ array[high], array[i + 1] ];
return i + 1;
};
if (low < high) {
const pi = partition(low, high);
quickSort(array, low, pi - 1);
quickSort(array, pi, high);
}
return array;
}
const array = [1, 10, 12, 3, 8, 11, 4, 9, 13, 16, 6, 2, 7, 15, 14, 5];
console.log(array);
console.log(varietySort(array));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment