Skip to content

Instantly share code, notes, and snippets.

@Nimdoc

Nimdoc/async_merge_sort.html Secret

Last active Feb 16, 2020
Embed
What would you like to do?
Async Merge Sort
<!doctype html>
<html lang="en">
<head>
<link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="sha384-ggOyR0iXCbMQv3Xipma34MD+dH/1fQ784/j6cY/iJTQUOhcWr7x9JvoRxT2MZw1T" crossorigin="anonymous">
<!-- Scripts -->
<script src="https://cdn.jsdelivr.net/npm/vue/dist/vue.js"></script>
<script src="https://code.jquery.com/jquery-3.3.1.slim.min.js" integrity="sha384-q8i/X+965DzO0rT7abK41JStQIAqVgRVzpbzo5smXKp4YfRvH+8abtTE1Pi6jizo" crossorigin="anonymous"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/popper.js/1.14.7/umd/popper.min.js" integrity="sha384-UO2eT0CpHqdSJQ6hJty5KVphtPhzWj9WO1clHTMGa3JDZwrnQq4sF86dIHNDz0W1" crossorigin="anonymous"></script>
<script src="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/js/bootstrap.min.js" integrity="sha384-JjSmVgyd0p3pXB1rRibZUAYoIIy6OrQ6VrjIEaFf/nJGzIxFDsf4x0xIM+B07jRM" crossorigin="anonymous"></script>
<meta charset="utf-8">
<title>Sort</title>
<meta name="description" content="Sort">
<meta name="author" content="Sort">
<!--
Code taken from here:
https://github.com/yeb9925/sorting-algorithms-javascript/blob/master/src/merge_sort/merge_sort_recursion.js
-->
<style>
.full-width-btn {
width: 100%;
height: 300px;
font-size: 48px;
}
@media (max-width: 576px) {
.full-width-btn {
height: 100px;
}
}
</style>
</head>
<body>
<div id="app">
<div v-if="stage === 0" class="container">
<div class="row">
<div class="col text-center">
<h1>Insert a list of stuff</h1>
<p>Seperate the items on to new lines.</p>
<textarea v-model="unformattedValues" rows="15" cols="40"></textarea>
</div>
</div>
<div class="row mt-3">
<div class="col text-center">
<button @click="submitArrayString" class="btn btn-primary">Submit</button>
</div>
</div>
</div>
<div v-else-if="stage === 1" class="container">
<div class="row">
<div class="col text-center">
<h1>Which one is better?</h1>
</div>
</div>
<div class="row">
<div class="col-xs-12 col-sm-6 my-2">
<button @click="makeDecision(false)" class="btn btn-primary full-width-btn">{{ valueA }}</button>
</div>
<div class="col-xs-12 col-sm-6 my-2">
<button @click="makeDecision(true)" class="btn btn-primary full-width-btn">{{ valueB }}</button>
</div>
</div>
<div class="row">
<div class="col">
<h3>Verdict</h3>
<ul>
<li v-for="item in verdict">{{ item }}</li>
</ul>
</div>
<div class="col text-right">
<h4>Number of comparisons so far: </h4>
<p>{{ comparisonCount }}</p>
</div>
</div>
</div>
</div>
<script>
var app = new Vue({
el: '#app',
data: {
stage: 0,
unformattedValues: "",
arr: [],
valueA: null,
valueB: null,
decision: false,
comparisonCount: 0,
userInput: false,
verdict: ["Waiting..."]
},
methods: {
submitArrayString: function(){
this.arr = this.unformattedValues.split("\n");
this.stage = 1;
this.doMergeSort();
},
makeDecision: function(decision){
this.decision = decision;
this.userInput = true;
},
compare: async function(a, b){
this.valueA = a;
this.valueB = b;
let result = await this.getUserInput();
this.comparisonCount++;
return (this.decision);
},
getUserInput: async function() {
this.userInput = false;
while(this.userInput === false)
{
await this.timeout(50);
}
},
timeout: function(ms){
return new Promise(res => setTimeout(res, ms));
},
doMergeSort: async function(){
result = await this.mergeSort(this.arr);
this.verdict = result;
},
mergeSort: async function(unsortedArray) {
// No need to sort the array if the array only has one element or empty
if (unsortedArray.length <= 1) {
return unsortedArray;
}
// In order to divide the array in half, we need to figure out the middle
const middle = Math.floor(unsortedArray.length / 2);
// This is where we will be dividing the array into left and right
const left = unsortedArray.slice(0, middle);
const right = unsortedArray.slice(middle);
// Using recursion to combine the left and right
result = await this.merge(
await this.mergeSort(left), await this.mergeSort(right)
);
return result;
},
merge: async function(left, right) {
let resultArray = [], leftIndex = 0, rightIndex = 0;
// We will concatenate values into the resultArray in order
while (leftIndex < left.length && rightIndex < right.length) {
let comparison = await this.compare(left[leftIndex], right[rightIndex]);
if (comparison) {
resultArray.push(left[leftIndex]);
leftIndex++; // move left array cursor
} else {
resultArray.push(right[rightIndex]);
rightIndex++; // move right array cursor
}
}
// We need to concat to the resultArray because there will be one element left over after the while loop
return resultArray
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
}
});
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment