# Running selsort_study.js

➕︎ Aa ➖︎ |Dark 1Dark 2Light|HackFira Code|Back to  PT Mono
``````// CPCS 324 Algorithms & Data Structures 2
// Selection Sort Decision Study

// 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;
}
``````