Created
October 28, 2017 15:46
-
-
Save kimamula/fa34190db624239111bbe0deba72a6ab to your computer and use it in GitHub Desktop.
JavaScript asynchronous sort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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)); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Can I say thank you? 🙇♂️