Types of sorting algorithms; decrement vs increment; recursion.

sortAlgorithms.js

// Fisher-Yates Shuffle sort fron javascript.info
// https://javascript.info/array-methods#shuffle-an-array

function shuffle(array) {
  // loop 2x array backwards switching 2 rando indexes e.g. [2, 1, 3]
  for (let i = array.length - 1; i > 0; i--) {
    // set j to a rounded rando num * (index + 1) // either 1, 2, or 3
    let j = Math.floor(Math.random() * (i + 1));
    // switches array item order, e.g., [1, 2] becomes [2, 1]
    [array[i], array[j]] = [array[j], array[i]]; // [num, num]
  }
};
// counts of specific sort orders for all possible permutations
let count = { '123': 0, '132': 0, '213': 0, '231': 0, '321': 0, '312': 0 };

// normal for loop... if normal is 1m times
for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  // yeah dont log shuffle(array) inside the loop dummy :/
// console.log(shuffle(array)); // crashie crashie 
// switches indexes w shuffle func
  shuffle(array);
// passes a stringified array of 3 (e.g., 123) digits (key) to the count object
// and increments its corresponding value
  count[array.join('')]++; // never seen this syntax before
}
// show counts of all possible permutations
for (let key in count) {
  console.log(`${key}: ${count[key]}`);
}


// https://www.redblobgames.com/pathfinding/a-star/introduction.html 
// https://www.section.io/engineering-education/sorting-algorithms-in-js/#bubble-sort
// https://rajat-m.medium.com/implement-5-sorting-algorithms-using-javascript-63c5a917e811
// https://www.freecodecamp.org/news/recursion-demystified-99a2105cb871/ 
// What's transitivity? https://simple.wikipedia.org/wiki/Transitivity_(mathematics)  

/*
  Insertion Sort [-5, -1, 3, 4, -2, -3, 5, -4, 1, 2, 0] 
  Task: Sort the array in either ascending or descending order.

  for (initialization; condition; afterthought)
    statement

  I reviewed 'for' loops to recall the order in which the 3 expressions are called 
    specifically when 'afterthought' is invoked (i.e., after condition runs--even on first iteration).
  Repeat: 
    'afterthought' (increment/decrement) expression runs AFTER ea CONDITION runs INCLUDING on the FIRST iteration. 
  Used 'debugger;' to step through it.

  Pseudo Code:  
  Sort an array in ascending order using an insertion sort method.
  Compare the first two elements of an array 
    and test whether the second element is larger the first.
  Swap places if the second is smaller than the first (assuming asc order).
  Repeat until the rest of the array is in ascending/descending order.

  Core Ideas:
  Nested loop allows looping j times in order to process array items, 
    depending on initialization (counter) and increment/decrement value (afterthought).   
  The 2nd loop initializes j with value of 'i minus 1' 
    which provides access to immediate PREVIOUS ADJACENT index for comparison. 
*/
function insertionSort(arr) {
  let count = 0;
  //Start from the second element.
  // debugger;
  for (let i = 1; i < arr.length; i++) {

    //Go through the elements behind it.
    for (let j = i - 1; j > -1; --j) { // it's not decremented from zero, is it?
      count++;
        
      //value comparison using ascending order.
      if (arr[j + 1] < arr[j]) {

        //swap
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];
      }
    }
  };
  console.log('insertionSort count', count)
return arr;
}
// console.log(insertionSort([-5, -1, 3, 4, -2, -3, 5, -4, 1, 2, 0])); // [23, 1, 10, 5, 2]


/*
  My Bubble Sort Pseudocode 
  Prose:
    Sort an array of numbers in ascending order.  
    Loop through an array. 
    Compare whether one number is less than its immediately following adjacent number
      using a nested loop for comparing the adjacent numbers.
      In the nested loop, compare whether one of the adjacent numbers is less than the other.
        If true, switch the adjacent number's index positions.
        Loops until j is not less than the array length (equals array length). 
    Algorithm ends when i is not less than the array length (equals array length).

  Step-by-step (more or less):
    The first loop initializes i var and loops over the length of the array.
    The second loop initilizes j var 
      and loops over (the current iteration) the array length minus i minus 1.
      This (is likely just one way that) makes it possible to loop through 
        adjacent (following) elements which get compared in the conditional 'if' stmt in 2nd loop.
          (IOWs, just loops through the array.)
      // Conditional Stmt
      Using the value of j (which increments as it loops, beginning w 0) 
      (think about how I'd get the value of any array index),
        compare whether the first element value is less than
          its (immediate next) adjacent element's value, beginning with the zeroth position 
            (which is how the inner loop is designed to work).
      If true, 
        (IOWs, the value of the immediately following index is less than the preceding index value) 
          switch the order of the two indices (think reassignment operator).
      Otherwise, move to the next element/index value 
        (inner loop increments j and runs thru conditionals again).
*/
function bubbleSort(arr) {
  let count = 0; // my addition
  // Outer iteration over the array
  for (let i = 0; i < arr.length; i++) { // i = 0
    
    // Inner iteration thru array
    for (let j = 0; j < arr.length - i - 1; j++) {
    // for (let j = 0; j < arr.length; j++) { // seems to work w/out '-i -1' bit

    // Value comparison using ascending order
      if (arr[j + 1] < arr[j]) {

        // Swapping - Compares the values of ea index one at a time, starting w the first.
        [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]];

        count++; // determine how many iterations
      }
    }
  };
  console.log('count is', count) // 4
  return arr;
};
// console.log(bubbleSort([5, 3, 8, 4, 6])); // original example
console.log(bubbleSort([6, 11, 99, 62, 19, 4]))


// console.log('zero minus negative nums: 0 - -1', 0 - -1, 0 - -2) // ok, this is weird
let decrementZero = 0; 
/*
  decrement vs increment and using -= or += 
    https://stackoverflow.com/questions/1546981/post-increment-vs-pre-increment-javascript-optimization
  console.log('decrementZero',
    'initial value', decrementZero--, // logs '0' AND decrements but doesn't log -1
    'pre-decrement', --decrementZero, // now it's -2 
    'post-decrement', decrementZero--, decrementZero, // logs -2 AND decrements (logs -3)
    decrementZero--, decrementZero--, decrementZero--)
*/