Sorting animation using generators. Maintains history of all previous states.
Created
July 7, 2017 02:32
-
-
Save tafsiri/b12961508ef0f650ab670374dc0e630c to your computer and use it in GitHub Desktop.
Sorting with generators + history
This file contains 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
| license: mit | |
| height: 300 | |
| border: no |
This file contains 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
| <!DOCTYPE html> | |
| <head> | |
| <title>blockup</title> | |
| <style> | |
| body { | |
| font-family: Helvetica, sans-serif; | |
| } | |
| .history { | |
| margin-left:50px; | |
| vertical-align: top; | |
| } | |
| input { | |
| width: 0px; | |
| margin-left:10px; | |
| margin-top:8px; | |
| } | |
| </style> | |
| </head> | |
| <body style='width:720px'> | |
| <p style='text-align: center;'> | |
| <button id='start'>Start</button> | |
| <!-- <button id='shuffle'>Shuffle</button> --> | |
| <p> | |
| <div id=svg-container></div> | |
| <div class='history'> | |
| <label for="history-slider">History</label> | |
| <input id="history-slider" disabled type="range" min="0" max="10" step="1" value="0"/> | |
| </div> | |
| <script src='https://d3js.org/d3.v4.min.js'></script> | |
| <script src='script.js'></script> | |
| </body> |
This file contains 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
| // Some initial setup | |
| const margin = { top: 5, right: 50, bottom: 5, left: 50 } | |
| const width = 720 - margin.left - margin.right | |
| const height = 120 - margin.top - margin.bottom | |
| const svg = d3.select('#svg-container').append('svg') | |
| .attr('width', width + margin.left + margin.right) | |
| .attr('height', height + margin.top + margin.bottom) | |
| const g = svg.append('g') | |
| .attr('transform', `translate(${margin.left}, ${margin.top})`) | |
| // Set up our input data. | |
| const NUM_VALS = 40; | |
| let input = []; | |
| for (let i = 0; i < NUM_VALS; i++) { | |
| input[i] = i; | |
| } | |
| const x = d3.scaleBand() | |
| .domain(input.map((d, i) => i)) | |
| .range([0, width]) | |
| .padding([.2]); | |
| const minBarHeight = 10; | |
| const maxBarHeight = 100; | |
| const barHeight = d3.scaleLinear() | |
| .domain(d3.extent(input)) | |
| .range([minBarHeight, maxBarHeight]); | |
| // Render the randomized array. | |
| shuffle(input) | |
| renderArray(input); | |
| // Adapted from https://en.wikipedia.org/wiki/Insertion_sort#Algorithm_for_insertion_sort | |
| function* insertionSort(arr, comparator) { | |
| for (let i = 1; i < arr.length; i++) { | |
| let j = i; | |
| while (j > 0 && arr[j-1] > arr[j]) { | |
| let temp = arr[j]; | |
| arr[j] = arr[j-1]; | |
| arr[j-1] = temp; | |
| j = j - 1; | |
| yield arr; | |
| } | |
| } | |
| return arr; | |
| } | |
| /** | |
| * Render array of numbers using bar height for magnitude | |
| */ | |
| function renderArray(array, duration=100) { | |
| let rects = g.selectAll("rect") | |
| .data(array, d => d); | |
| const rEnter = rects.enter() | |
| .append('rect') | |
| .attr('x', (d, i) => x(i)) | |
| .attr('y', (d) => maxBarHeight - barHeight(d) ) | |
| .attr('width', x.bandwidth()) | |
| .attr('height', d => barHeight(d)); | |
| rects.merge(rEnter) | |
| .transition() | |
| .duration(duration) | |
| .attr('x', (d, i) => x(i)) | |
| .attr('fill', 'grey'); | |
| rects.exit().remove(); | |
| } | |
| // Fisher-yates shuffle via https://bost.ocks.org/mike/shuffle/compare.html | |
| function shuffle(array) { | |
| var m = array.length, t, i; | |
| while (m) { | |
| i = Math.floor(Math.random() * m--); | |
| t = array[m]; | |
| array[m] = array[i]; | |
| array[i] = t; | |
| } | |
| } | |
| function compareNumbers(a, b) { | |
| return a - b; | |
| } | |
| let states = []; | |
| let sorter; | |
| let historySlider = d3.select('#history-slider'); | |
| function start() { | |
| d3.select('#start').attr('disabled', true); | |
| // Render the sorting algorithm as it progresses | |
| sorter = insertionSort(input, compareNumbers); | |
| const interval = 1; // how quickly should the process go | |
| const timer = d3.interval(function(elapsed) { | |
| const current = sorter.next(); | |
| renderArray(current.value, interval); | |
| if (current.done) { | |
| console.log("Generator done") | |
| historySlider.attr('disabled', null); | |
| timer.stop(); | |
| } else { | |
| states.push(current.value.slice()); | |
| historySlider.attr('max', states.length-1) | |
| historySlider.attr('value', states.length-1) | |
| historySlider.style('width', Math.min(states.length, 500) + "px") | |
| } | |
| }, interval); | |
| } | |
| d3.select('#start') | |
| .on('click', () => { | |
| start(); | |
| }) | |
| d3.select('#history-slider') | |
| .on('input', function() { | |
| const state = states[this.value]; | |
| renderArray(state, 80) | |
| }) | |
| // Run an iterator to completion | |
| function complete(iterator) { | |
| let it = iterator.next(); | |
| while (!it.done) { | |
| it = iterator.next() | |
| } | |
| return it.value; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment