Devon and Cornwall GNU/Linux Users Group

Network Sort
Algorithm Animation





Introduction

The animation displayed above shows how we can sort 8 values into order by comparing 2 adjacent values in a series of steps in each of 9 rows. We start with numbered counters from 1 to 8 placed in the top row in a random order. By the end of the routine or algorithm the counters should appear in the bottom row in sorted order (1 to 8).The sort is depicted sequentially as individual comparison steps in each row so that we can understand how it works, however because all the comparisons in a row can be carried out independently we could use parallel processing techniques at the row level to speed up the sorting.

How it works!


A Decision Symbol
“Empty Decision Box”
“True Decision Box”
“False Decision Box”

“Copy Through Symbol (before copy)”

Each decision that needs to be made is depicted in the animation as a “Decision Symbol” (see left panel). The decision symbol is at the center of a 3 x 3 matrix (box), with each corner potentially having a counter in it. When the “box” is empty it looks like the “Empty Decision Box” image shown in the left panel. When the top left and right corners are “populated” with counters then the left counter is either less than the right counter in which case we have a “True Decision Box” or the left counter is not less than the right counter in which case we have a “False Decision Box” (see panel on left). When the result of the decision is true the decision symbol turns green (to indicate a “true” result) and the values in the counters at the top left and right are copied to the lower left and right corners (again please refer to the “True Decision Box” example in the left panel. However if the left counter value is not less than the right then the decision symbol turns red to indicate a “false” result and the top left corner counter value is copied to the bottom right corner and the top right corner value is copied to the bottom left. In other word the two counters swap positions in the next row.

On alterative rows you get two “Copy Through” symbols at the left most and right most columns in the row. “Copy Through” simply copies the counter above the symbol to the cell directly below. Note that before a copy takes place the symbol is red, however after a copy has taken place the symbol changes to green.

By repeating this pattern of decisions and “copy throughs”, the lowest value counters slowly migrate to the left while the highest value migrates to the right.

Downloads!

For those that are interested the downloadable javascript code that is used to display the animation above is shown below:


var step = 0; // step counter in sort network.
var slots = []; // slots are where counters are added.
var decisions = []; // the decsision blocks go here!
var edges = []; // edge slots that progress directly.
var intervalID; // Used as handle for interval used in tickerStep.
 
// initialise numbers array for sorting
 
var numbers = [ [0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0]];
 
// actions to be taken format: type 0 - decision 1 - copy through
// followed by: decision index, input1,input2,output1,output2...
// or: edge index, input1, output1
 
var actions = [[0, 0,0,0,0,1,1,0,1,1],
               [0, 1,0,2,0,3,1,2,1,3],
               [0, 2,0,4,0,5,1,4,1,5],
               [0, 3,0,6,0,7,1,6,1,7],
               [1, 0,1,0,2,0],
               [0, 4,1,1,1,2,2,1,2,2],
               [0, 5,1,3,1,4,2,3,2,4],
               [0, 6,1,5,1,6,2,5,2,6],
               [1, 1,1,7,2,7],
               [0, 7,2,0,2,1,3,0,3,1],
               [0, 8,2,2,2,3,3,2,3,3],
               [0, 9,2,4,2,5,3,4,3,5],
               [0,10,2,6,2,7,3,6,3,7],
               [1, 2,3,0,4,0],
               [0,11,3,1,3,2,4,1,4,2],
               [0,12,3,3,3,4,4,3,4,4],
               [0,13,3,5,3,6,4,5,4,6],
               [1, 3,3,7,4,7],
               [0,14,4,0,4,1,5,0,5,1],
               [0,15,4,2,4,3,5,2,5,3],
               [0,16,4,4,4,5,5,4,5,5],
               [0,17,4,6,4,7,5,6,5,7],
               [1, 4,5,0,6,0],
               [0,18,5,1,5,2,6,1,6,2],
               [0,19,5,3,5,4,6,3,6,4],
               [0,20,5,5,5,6,6,5,6,6],
               [1, 5,5,7,6,7],
               [0,21,6,0,6,1,7,0,7,1],
               [0,22,6,2,6,3,7,2,7,3],
               [0,23,6,4,6,5,7,4,7,5],
               [0,24,6,6,6,7,7,6,7,7],
               [1, 6,7,0,8,0],
               [0,25,7,1,7,2,8,1,8,2],
               [0,26,7,3,7,4,8,3,8,4],
               [0,27,7,5,7,6,8,5,8,6],
               [1, 7,7,7,8,7]
               ];
 
function start()
    {
    var rows = 0;
 
    for(rows=0;rows < 17;rows++)
        {
        row(rows);
        }
 
    step = 0; // reset step counter;
    firstRow();
 
    itervalID = setInterval(function(){tickerStep()}, 3000);
    }
 
function row(row)
    {
    var div = document.createElement("div");
    var sortDiv = document.getElementById("sort");
 
    div.style.width = "760px";
    div.style.height = "50px";
    div.style.background = "#F0F0E0";
    div.style.color = "white";
    div.innerHTML = "";
    div.className = "rowItem"
    div.id="row_"+ row;
 
    sortDiv.appendChild(div);
 
    var cols = 0;
    for(cols = 0;cols < 15;cols++)
        {
        columns(row,cols);
        }
    }
 
function columns(row,column)
    {
    var div = document.createElement("div");
 
    div.style.width = "40px";
    div.style.height = "40px";
    div.style.background = "white";
    div.style.color = "black";
    div.style.cssFloat = "left";
    div.style.styleFloat = "left";
    div.style.position = "relative";
    div.style.top = "10px";
    div.style.left = "" + (column + 1) * 10 +"px";
 
    div.className = "rowItem"
    div.id = "column_"+ row + "_" + column;
 
    // Add Places
 
    if(row % 2 == 0 && column % 2 == 0)
        {
        slots.push(document.createElement("img"));
 
        slots[slots.length - 1].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/empty_place.png";
        slots[slots.length - 1].style.position = "relative";
 
        div.appendChild(slots[slots.length - 1]);
        }
 
    // Add Decisions
 
    if((row % 4 == 1 && column % 4 == 1) || (row % 4 ==3 && column % 4 == 3))
        {
        decisions.push(document.createElement("img"));
 
        decisions[decisions.length - 1].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/empty_decision.png";
        decisions[decisions.length - 1].style.position = "relative";
 
        div.appendChild(decisions[decisions.length - 1]);
        }
 
    // Add Verticals
 
    if(row == 3 || row == 7 || row == 11 || row == 15)
        {
        if(column == 0 || column == 14)
            {
            edges.push(document.createElement("img"));
 
            edges[edges.length - 1].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/red_vertical.png";
            edges[edges.length - 1].style.position = "relative";
 
            div.appendChild(edges[edges.length - 1]);
            }
        }
 
    var item = document.getElementById("row_" + row);
    item.appendChild(div);
    }
 
function firstRow()
    {
    var i = 0; // outer loop (rows)
    var j = 0; // inner loop (columns)
    var r = 0; // random number
 
    // Reset numbers array
 
    for(i = 0; i < 8; i++)
        {
        for(j=0;j<8;j++)
            {
            numbers[i][j] == 0;
            }
        }
 
    // Setup Initial Numbers
    for(i = 0; i < 8;i++)
        {
        r = Math.round(Math.random() * 8);
 
        while(numbers[0][r] != 0)
            {
            r = Math.round(Math.random() * 8);
            }
 
        numbers[0][r] = i + 1;
        putCounter(r,i+1);
        }
    }
 
function nextStep(s)
    {
    var explain = document.getElementById("explain_text");
    if(actions[s][0] == 0)
        {
        // its a decision !
        if(numbers[actions[s][2]][actions[s][3]] < numbers[actions[s][4]][actions[s][5]])
            {
            // all is well
            numbers[actions[s][6]][actions[s][7]] = numbers[actions[s][2]][actions[s][3]];
            numbers[actions[s][8]][actions[s][9]] = numbers[actions[s][4]][actions[s][5]];
            setDecisionState(actions[s][1],1);
            }
        else
            {
            // swap required
            numbers[actions[s][6]][actions[s][7]] = numbers[actions[s][4]][actions[s][5]];
            numbers[actions[s][8]][actions[s][9]] = numbers[actions[s][2]][actions[s][3]];
            setDecisionState(actions[s][1],2);
            }
 
        // update the (output) slots....
        putCounter((actions[s][6] * 8) + actions[s][7],numbers[actions[s][6]][actions[s][7]]);
        putCounter((actions[s][8] * 8) + actions[s][9],numbers[actions[s][8]][actions[s][9]]);
        }
 
    if(actions[s][0] == 1)
        {
        // its a copy through!
        numbers[actions[s][4]][actions[s][5]] = numbers[actions[s][2]][actions[s][3]];
        putCounter((actions[s][4] * 8) + actions[s][5],numbers[actions[s][4]][actions[s][5]]);
        setCopyThroughState(actions[s][1],1);
        }
    }
 
function tickerStep()
    {
    if(step < actions.length)
        {
        nextStep(step);
        step = step + 1;
        }
    else
        {
        clearInterval(intervalID)
        }
    }
 
function putCounter(place,number)
    {
    slots[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/counter_" + number + ".png";
    }
 
function setDecisionState(place,state)
    {
    switch(state)
        {
        case 0: decisions[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/empty_decision.png";
                break;
        case 1: decisions[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/green_decision.png";
                break;
        case 2: decisions[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/red_decision.png";
                break;
        }
    }
 
function setCopyThroughState(place,state)
    {
    switch(state)
        {
        case 0: edges[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/empty_vertical.png";
                break;
        case 1: edges[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/green_vertical.png";
                break;
        case 2: edges[place].src = "http://www.dcglug.org.uk/wp-content/uploads/2014/10/red_vertical.png";
                break;
        }
    }


2 thoughts on “Network Sort
Algorithm Animation”

  2. Pingback: October 2014 Pi jam | Devon and Cornwall GNU/Linux Users Group

Leave a comment

Your email address will not be published. Required fields are marked *