Skip to content

Instantly share code, notes, and snippets.

@kimamula
Created October 28, 2017 15:46
Show Gist options
  • Star 11 You must be signed in to star a gist
  • Fork 2 You must be signed in to fork a gist
  • Save kimamula/fa34190db624239111bbe0deba72a6ab to your computer and use it in GitHub Desktop.
Save kimamula/fa34190db624239111bbe0deba72a6ab to your computer and use it in GitHub Desktop.
JavaScript asynchronous sort
/**
* return the mid value among x, y, and z
* @param x
* @param y
* @param z
* @param compare
* @returns {Promise.<*>}
*/
async function getPivot(x, y, z, compare) {
if (await compare(x, y) < 0) {
if (await compare(y, z) < 0) {
return y;
} else if (await compare(z, x) < 0) {
return x;
} else {
return z;
}
} else if (await compare(y, z) > 0) {
return y;
} else if (await compare(z, x) > 0) {
return x;
} else {
return z;
}
}
/**
* asynchronous quick sort
* @param arr array to sort
* @param compare asynchronous comparing function
* @param left index where the range of elements to be sorted starts
* @param right index where the range of elements to be sorted ends
* @returns {Promise.<*>}
*/
async function quickSort(arr, compare, left = 0, right = arr.length - 1) {
if (left < right) {
let i = left, j = right, tmp;
const pivot = await getPivot(arr[i], arr[i + Math.floor((j - i) / 2)], arr[j], compare);
while (true) {
while (await compare(arr[i], pivot) < 0) {
i++;
}
while (await compare(pivot, arr[j]) < 0) {
j--;
}
if (i >= j) {
break;
}
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
await quickSort(arr, compare, left, i - 1);
await quickSort(arr, compare, j + 1, right);
}
return arr;
}
quickSort(array, (a, b) => Promise.resolve(a - b));
@ericmorand
Copy link

Can I say thank you? 🙇‍♂️

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