Weeks 3&4 - Arrays & Sorting

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.0 - Join our ICS4UC Repl.it course

2.1 - Random Library Functions

We will build a library for ourselves that contains useful functions. Look for the Helper Library project in our new Repl.it course (see 3.0 above).

  • randInt(min, max, inclusive = true)
Return a random integer where min and max are numbers, 'inclusive' is a boolean to determine if min and max are included or excluded (defaults to true). This function has been coded for you.
  • randNumOfLength(precision)
Return a random number where 'precision' controls the number of digits in the number (> 0). Note: The number 487 is not 0487 or 000487. Precision is exact.
  • round(number, precision)
Return a rounded version of 'number' to the given 'precision' of decimals (>= 0).
  • randChar(letterCase = 1)
Return a random Latin letter character either from A to Z (if 'letterCase' is 1 or 'upper') or a to z (if 'letterCase' is 2 or 'lower'). letterCase will default to 1.
  • 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 1 or 'upper' for all uppercase, 2 or 'lower' for all lowercase, and 0 or 'mixed' for a mix of letters. See the hints section for help on this. letterCase will default to zero.

Important: Do not use .toFixed() as it does not round correctly.

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 (called concatenation)
someString = someString + anotherStringOrChar;someString += anotherStringOrChar; // Shortcut
  • Math.pow(), Math.round() and Math.random() will be your friends.
  • If you want a random number 4 digits long, that is a random number between 1000 and 9999 inclusive. Interesting fact: 9999 = 10 000 - 1
  • Zero is usually a special case. You might need to take that into account, especially in randNumOfLength( ) because randNumOfLength(1) should return a number from 0 to 9.

2.2 - Array Library Functions

Now let's create some functions that deal with arrays.

First - at the top of your code document, just after the heading comment block, add the following line exactly:

"use strict";

That will ensure you are following correct JavaScript guidelines.

  • inArray(item, array)
JavaScript arrays have a .includes() which will return if a given item exists in the array. We are going to mimic this functionality. Always starting at zero, go through the given array and return true if 'item' is found, false otherwise. Important note: "3" != 3 Strings and Numbers should be considered unequal.
  • arrayOfInts(length, min, max, inclusive, allowDuplicates)
Return an array of size 'length' where each element is a random integer from min to max. 'inclusive' is a boolean to determine if min and max are included or excluded (defaults to true). 'allowDuplicates' defaults to true and determines if duplicates are permitted. Heads up, for testing purposes - if allowDuplicates is false, the range from min to max must be >= length. You do not need to error check for that, it's just a note for your own sanity.
  • arrayOfStrings(length, maxStrLength, letterCase)
Return an array (of length 'length') containing random strings, each of length 1 to maximum 'maxStrLength'. 'letterCase' can be 1 or 'upper' for all uppercase, 2 or 'lower' for all lowercase, and 0 or 'mixed' for a mix of letters. See the hints section for help on this.

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.2 - Hints

  • Create an empty array variable:
let someArrayName = [ ];
  • Add an element to (or change) an array:
someArrayName[someIndex] = 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 return 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 return the new length.

2.3 - Insertion Sort

2.3 - 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.4 - Bubble (Shaker) Sort Due Wed. March 11th 8:30am

2.4 - Hints

  • You know how to swap items in an array from Insertion Sort.
  • shakerSort( ) is an adjustment of bubbleSort( )
  • Reduce the length of each pass by 1 as items bubble to the appropriate end.

🢥 2.5 - Selection Sort Due Fri. March 13th 11:30pm

2.5 - Hints

  • You should know how to go through an array
  • You should know how to reduce the search window by 1, similar to Bubble Sort
  • You should know how to swap items in an array

Useful Links