2 - Sorting & Efficiency

How many ways can you sort a complete mess of numbers? Is there one fastest method? In this unit we will begin to build our library of useful functions, beginning with random number generators, then building randomized arrays, and finishing with common sorting algorithms.

This course focuses on Computer Science and not specifically JavaScript. We will avoid using built-in functions that do the work for us. Once we become CS geniuses, we can use language-specific tools. For now, let's learn.

Insertion Sort DemoSwfung8 / CC BY-SA


2.1 - Random Library Functions

We will build a library that contains useful functions we can reuse. Look for the Helper Library project in Unit 1 of our Replit team.

Brief Description:

  • randInt(min, max)

Return a random integer where min and max are included. This function has been coded for you.

  • round(num, precision)

Return a rounded version of 'number' to the given 'precision' of decimals (>= 0). This function has been coded for you.

  • randNum(numOfDigits)

Return a random whole number where 'numOfDigits' controls the number of digits in the number (> 0). Note: The number 487 is not 0487 or 000487. numOfDigits is exact.

  • randChar(upperCase = true)

Return a random Latin letter character either from A to Z (if 'upperCase' is true) or a to z (if 'upperCase' is false). upperCase will default to true.

  • randString(maxLength, letterCase = 0)

Return a random string of maximum length 'maxLength' (> 0). The string is made up of alpha letters A-Z and/or a-z. 'letterCase' can be 0 for all uppercase, 1 for all lowercase, and 2 for a mIX Of CaSEs. See the hints section for help on this. letterCase will default to zero (mixed).

  • arrayOfInts(length, min, max)

Return an array of size 'length' where each element is a random integer from min to max, inclusively.

  • arrayOfStrings(length, maxStrLength, letterCase)

Return an array (of length 'length') containing random strings, each of length 1 to maximum 'maxStrLength'. 'letterCase' can be 0 for all uppercase, 1 for all lowercase, and 2 for a mix of cases. See the hints section for help on this.

  • mixedArray(length, min, max, maxStrLength, letterCase)

Return an array (of length 'length') containing random strings or numbers. Strings are of length 1 to maximum 'maxStrLength'. 'letterCase' can be 0 for all uppercase, 1 for all lowercase, and 2 for a mix of cases. Numbers are any random integer from min to max, inclusive.

Note: we are not permitted to use .sort( ), .reverse( ), .split( ), .join( ), or .includes( ). If you are unsure about any built-in functions ask the teacher.

2.1 - Hints

A to Z: 65 to 90 and a to z: 97 to 122

  • String.fromCharCode(num) will return a character from the ASCII table represented by 'num'

  • You can add to the end of a string (concatenation) but you can't modify the characters in a string.

someString = someString + anotherStringOrChar;someString += anotherStringOrChar; // Shortcut

  • Math.pow( ), Math.round( ) and Math.random( ) might be your friends.

  • Zero is usually a special case. You might need to take that into account, especially in randNum( ) because randNum(1) should return a number from 0 to 9.

  • To create an empty array variable:

let some_array = [ ];

  • Add an element to (or change) an array item:

some_array.push(value);some_array[some_index] = value;

  • .length gives the number of elements in the array

Important: array indexes begin at zero.

  • .push(x) will add 'x' to the end of an array (can be multiple items) and returns the new length.

  • .pop() will remove and return the last element.

  • .shift() will remove and return the first element, shifting all elements left one.

  • .unshift(x) will add 'x' to the beginning of the array (can be multiple items) and returns the new length.

A little heads up - 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)

2.2 - Insertion Sort

2.2 - 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.

  • Each time you finish looking left and insert the item, that is called a completed pass.

2.3 - 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.

2.4 - 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?

Useful Links