**2 - Sorting & Efficiency**

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

### 2.1 - Random Library Functions

We will build a * library* that contains useful functions we can reuse. Look for the

*project in*

**Helper Library****Unit 1**of our Replit team.

**Brief Description:**

randInt(min, max)

*included*.

**This function has been coded for you.**

round(num, precision)

**This function has been coded for you.**

randNum(numOfDigits)

*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)

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

**Latin letter**randString(maxLength, letterCase = 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)

*random*integer from min to max, inclusively.

arrayOfStrings(length, maxStrLength, letterCase)

*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)

*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

Characters (letters) are stored using

**ASCII**codes which are**stored in a table**.

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

**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:

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

.length gives the number of elements in the array

*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*

*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

**Univ. of San Fran. Visual Sorting Comparison**(fantastic resource)**xSortLab**- Visualization of Sorting

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) SortYou

*should*know how to swap items in an arrayWhat else is there to know?

### Useful Links

JavaScript

**Arrays**JavaScript

**Math Object**JavaScript

**Math.random( ) examples****xSortLab**- Visualization of Sorting**Wikipedia Article**on Sorting Algorithms