Running selsort_study.js

// CPCS 324 Algorithms & Data Structures 2
// Selection Sort Decision Study
// 2020, Dr. Muhammad Al-Hashimi


// Exercise: generate a decision tree for lists of length n=4. Note tree height,
// compare to #comps expected for selection sort.


// input positions (name 1st a, 2nd b, etc.)
var p = ["a","b","c"];

// sorted position permutations (assign values to force position)
// same order as textbook left-to-right

var a = [
   [1,2,3],  // a<b<c, 1st input sorted first (list a before etc.)
   [1,3,2],  // a<c<b
   [2,3,1],  // c<a<b, ...sorted second (a before b)
   [2,1,3],  // b<a<c
   [3,1,2],  // b<c<a, ...sorted last (b before c)
   [3,2,1]   // c<b<a
   ];

// test input lists, trace decisions
// (even though the binary tree will have 2^3=8 leaves, sorting will go through
// 6 unique decision paths, each corresponding to a permutation of 3 elements)

var m = a.length;
for (var i=0; i<m; i++)
{
   document.write(`<p>${a[i]}</p>`);
   selsort(a[i]);
   // document.write(`<p>post ${a[i]}</p>`);
}


// --------------------
// selection sort (Levitin, 3rd ed)
// track pseudocode decisions, note position comp direction
// still a valid decision tree but different
// input list permutations in any order will also work

function selsort(a)
{
   var d, n = a.length;

   for (var i=0; i<n-1; i++)
   {
      var i_min = i;
      for (var j = i+1; j<n; j++)
      {
         document.write(`${j} ${i_min} `);
         if ( d = (a[j] < a[i_min]) )   // note position comp direction
         {
            i_min = j;
         }
         document.write(`${d?"yes":"no"}<br>`);
      }
      swap (a,i,i_min);
   }

}

// --------------------
// selection sort (Levitin, 3rd ed)
// track Fig 11.2 decisions, note flip decision outcome to match
// desired comp direction to match figure tree
// selection sort logic remains the same though, i.e., same positions compared as above

function selsort2(a)
{
   var d, n = a.length;

   for (var i=0; i<n-1; i++)
   {
      var i_min = i;
      for (var j = i+1; j<n; j++)
      {
         if ( d = (a[j] < a[i_min]) )
         {
            i_min = j;
         }
         document.write(`${p[i]}<${p[j]}: ${!d?"yes":"no"}<br>`);   // note flip decision outcome
      }
      swap (a,i,i_min);
   }

}

// --- helper functions ----------------------------------------
function swap(a,i,j)
{
   var temp = a[i];
   a[i] = a[j];
   a[j] = temp;
}