Swap and Find Minimum

Introduction

The purpose of this set of exercises is to develop several helper functions (functions that can serve as building blocks for other functions) that will be useful later for sorting items in an array. You will eventually use these functions in the Art Catalog project, but for now you will develop and test them in a separate web page created just for this purpose. A special-purpose project for experimenting with and testing new ideas is often called a sandbox.

Getting Started

Exercise 1 - Understanding the Existing Code

  1. Start by downloading a skeleton version of the Swap and Min sandbox. (Right-click or Control-click to download the file.)

  2. Review: Scroll down in your Swap and Min page to the <body> section. Note that the page has a heading, an empty <div> section that you'll be able to write output to, and an area for printing the last modification date. The actual <body> tag calls a function — generatePage() — to generate most of the body of the page whenever the page is loaded or reloaded.

    Now scroll up to the <script> in the <head> section. There are 6 functions here, most of them incomplete.

    • generatePage — This function has been started, but you will be adding to it as you develop and experiment with new code.
      • To start with, it defines three arrays and prints information about one of them using the arrayInfoAsString function. (The arrayInfoAsString function has been completely implemented.)
      • It also contains commented-out sample calls to the incomplete swap and findMinIndex functions that you will be completing in this activity.
      • Finally, it contains a commented-out sample call to the incomplete selectionSort function that will be the focus of a future activity.
    • setLastModDate — This function is the same as you've seen in other projects.

    Load the page before making any modifications to see what it does.

  3. Experiment and Check Your Understanding: In the generatePage function, copy and paste the lines that print the original values of the Names array to do the same for the other two arrays. Reload the page to test it.

    Read the code for the arrayInfoAsString function. Note that it works equally well for different arrays of different types and different sizes. How does it know how many array elements to print? Look at both the code and the output to be sure that you understand how to refer to the array, an index into the array, and a value at a particular index in the array before going further. In other words, what do each of these refer to? 

        thisArray
    i
    thisArray[i]

Swap

Next you will implement a function that swaps two entries within an array.

Exercise 2 - Implementing the swap Function

  1. Swap: Read the code (mostly comments) for the stub swap function. What parameters does it expect? What parameters are being passed by the generatePage function? Replace the comments inside the function with code that implements the simple algorithm described in pseudo-code. Once complete, the function should swap two entries in an array.

  2. Test Swap: Uncomment the code in the generatePage function that calls swap for the Names array and reprints the array after the swap. Load your page and verify that the correct elements are now being swapped.

    Add additional tests to swap elements 1 and 4 of the Names array, and to swap some elements in your other two arrays, printing the contents of the appropriate array after each swap. Re-load the page after you add each test to see what it does.

    As an experiment, add a test to swap elements 0 and 5 in the Names array. [Stop and think: is there an element 5? What do you think this will do?] Re-load the page to test it.

    Note: you've just experimented to discover what JavaScript does when you try to access a non-existent element of an array. Not all languages handle this in the same way. In some languages, attempting to access an invalid array element will cause your program to crash.

  3. Once you're done experimenting with the invalid element 5, comment out that test so that you don't try to use that version of the array in later experiments.

    You can remove the alert message once you are confident that your function is working correctly.

Find Minimum (or Find Minimum Index)

It can be useful to find the smallest value in an array, but it's often even more useful to find the index of the smallest value. And if you have the index, you can get the value.

Exercise 3 - Implementing the findMinIndex Function

  1. Find Minimum Index: Read the code (mostly comments) for the stub findMinIndex function. What parameters does it expect? What is being passed by the generatePage function? What is the findMinIndex function supposed to return? What is it actually returning?

    Replace the capitalized comments inside the function with code that implements the simple algorithm described in the comments. Once complete, the function should return the index of the smallest value in an array.

  2. Test findMinIndex: Uncomment the code in the generatePage function that calls findMinIndex for the Names array. Test your function. Then modify the generatePage function to find the index of the minimum value in the other arrays. Since the comparison operators "<" and ">" work for both strings and numbers, your findMinIndex function should work for arrays containing either.

  3. Find Minimum in a Subrange: Modify the findMinIndex function to take a second parameter, a starting index. The function should now find the smallest element in the part of the array starting at that index. For example, if the starting index is 2, then the function should return the index of the smallest element between index 2 and the end of the array. Start by modifying the comment with the function description and adding the new parameter, as shown below. Then modify the code in the function so that it starts at the startIndex position rather than at index 0 when looking for the minimum value. 

    
//----------------
// findMinIndex:
// Returns the index of the smallest item in the array
// at or after position startIndex 
function findMinIndex(theArray, startIndex)
{
   ...
}
  4. Test: Edit the generatePage function to test your modified function by calling it several times, passing it different arrays and different starting indices. The output should correctly identify the array and starting point for each test. It is always a good idea to test boundary conditions, so include at least one test that starts with the first element (starting index of 0) and at least one test that starts with the last element (starting index is 1 less than the length of the array).
  5. You can remove the alert message once you are confident that your function is working correctly.

If You Have Time — Putting It Together to Sort

If you have time, get started on the next activity: Selection Sort — Putting it All Together.

There will be nothing to hand in for today's activity, but you will need to have these functions finished in order to complete the Sorting activity.