User Tools

Site Tools


λ Is sorted?

======= Algorithm ======= <syntax js> function isSorted(a) { // From back to front. for (var i=a.length-1; i>0; i--) { // If any two items are out of order, then not sorted. if (a[i] < a[i-1]) { return false; } } return true; } </syntax> ======= Support ======= <syntax js> function run(a) { result = isSorted(a); } </syntax> ======= Tests ======= <syntax js> function testSorted() { assert(isSorted([1,2,3,4,5,6,10,45,100])); assert(isSorted([1,1,1,2,2,3,5,6,7,7])); } function testNotSorted() { assert(!isSorted([1,2,7,4,5,6,10,45,100])); assert(!isSorted([5,4,3,2,1])); }</syntax> ======= Options ======= <syntax js> { "title":"Is sorted?", "height": "270px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <link rel="stylesheet" type="text/css" href="algorithms-lib/graph.css"/> <style> .chart rect.sorted { fill: green; } .chart rect.unsorted { fill: red; } </style> <script src="http://d3js.org/d3.v2.js"></script> <script src="algorithms-lib/graph.js"></script> <script type="text/javascript"> var graph = new Graph(20); window.onload = function() { chart = graph.createGraph(d3.select("#chart")); graph.almostSorted(); } function globals() { return {result:undefined}; } function args(forCloning) { return forCloning? graph.getClonableArray() : graph.array; } var oldI; function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { graph.drawGraph(duration); var sortedN = x.lookupInScope("sortedN"); var idx = x.lookupInScope("i"); var result = x.lookupInScope("result"); var bars = chart.selectAll("rect.data").data(graph.array, function(d) {return d.hash;}); // Increase the sorted section when we have an index being moved down. if (typeof idx !== "undefined") { sortedN++; } if (idx !== oldI) { bars.classed("index", function(d, i) {return i===idx || i===idx-1;}); oldI = idx; } bars.classed("sorted", function() {return result === true;}); bars.classed("unsorted", function() {return result === false;}); } } </script> </head> <body> <div style="position:absolute;padding:2px"> <button onclick="graph.randomise(200)">Random</button> <button onclick="graph.almostSorted()">Almost sorted</button> <button onclick="graph.sorted()">Sorted</button> </div> <div id="chart"></div> </body> </html> </syntax>

algorithm/is_sorted.txt · Last modified: 2015/02/02 08:28 (external edit)