3 - Algorithms & Efficiency
How many ways can you sort a complete mess of numbers? Is there one fastest method? In this unit we will code and compare some common sorting algorithms and then dive further into algorithm design in Unit 4.
3.0 - Library of Functions (lib)
The library.js file you have been using for round() and randInt() has been updated. The functions are documented inside library.js and VSCode will pick up the documentation. Most of the added functions are to help you with creating test data.
Brief Descriptions of the most useful functions (see library.js for fill list):
randInt(min, max)
round(num, precision)
randNum(numOfDigits)
randChar(upperCase = true)
randString(maxLength, letterCase = 0)
arrayOfInts(length, min, max)
arrayOfStrings(length, maxStrLength, letterCase)
mixedArray(length, min, max, maxStrLength, letterCase)
3.1 - Insertion Sort
Univ. of San Fran. Visual Sorting Comparisonย (fantastic resource)
xSortLab - Visualization of Sorting
Link to GitHub Repo (read the README carefully)
3.1 - Hints
You will need a 'for' loop that goes through each item of the array starting at index 1 (the second element).
Begin looking left of that position and shift elements to the right (one-by-one) if they are larger than our temporary value (another loop).
Each time you finish looking left and insert the item, that is called a completed pass.
ย ย ย ย (shaker visualization video)
3.2 - Hints
You know how to swap items in an array from Insertion Sort.
shakerSort( ) is an adjustment of bubbleSort( )
Large items bubble right (odd #'d passes), small items bubble left (even #'d passes)
Reduce the length of each pass by 1 as items bubble to the appropriate end.
3.3 - Hints
By now you know how to go through an array and how to nest loops inside each other
You should know how to reduce the search window by 1, similar to Bubble (shaker) Sort
You should know how to swap items in an array
What else is there to know?
Wait for Mr. Brash to explain before you click the link below.
Reminder
Arrays in JS are passed & copied by reference
What does this mean - by reference?
It means that when you try to make a copy or pass an array into a function, it does not actually duplicate every item in the array to create separate arrays. It makes a link or shortcut to the array.
Example
let origSheeps = ['๐', '๐'];
let sheeps2 = origSheeps;
sheeps2.push('๐บ');
console.log(sheeps2);
ย ย // [ '๐', '๐', '๐บ' ]
console.log(origSheeps);
ย ย // [ '๐', '๐', '๐บ' ]
๐ฑ , our original sheeps have changed?!
(source)
Useful Links
JavaScript Arrays
JavaScript Math Object
JavaScript Math.random( ) examples
xSortLab - Visualization of Sorting
Wikipedia Article on Sorting Algorithms