CSCE 2004 - Laboratory Assignment 7

The objective of this laboratory is to gain experience with searching and sorting algorithms on arrays in C++. It has the following steps:

  1. Getting Started
  2. As needed, refer to Lab #5 to review how to declare arrays, initialize arrays, and manipulate data in arrays in C++.

  3. Searching for Elements of an Array
  4. Consider the following program:

    //---------------------------------------------------
    //Author:  Some lucky 2004 student
    //Date:    Today's date
    //Purpose: Program to search/sort the elements of an array
    //---------------------------------------------------
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    void initialize(float items[20])
    {
        srand(time(0));
        
        for(int i = 0; i < 20; i++)
        {
            //generate random values from 0 to 499.9 in increments of 0.10
            items[i] = rand()%500 + (rand()%10)/10.0;
        }
    }
    
    void findSmallestElement(const float items[20], float & smallestValue, int & indexOfSmallest)
    {
        
    }
    
    int main()
    {
        float smallestValue = -1.0;
        int indexOfSmallest = -1;
        float items[20];
        
        initialize(items);
        findSmallestElement(items, smallestValue, indexOfSmallest);
        
        cout << "The smallest element in the array is " << smallestValue
             << ", located at index: " << indexOfSmallest << endl;
        
        return 0;
    }
    

    Conceptually, to find a particular element in an array - regardless of where it is in any given array - you should iterate across every element in the array in a loop, and perform a check at each location. Once you've examined every array element, you should have found your answer.

    In this case, you are to finish the findSmallestElement() function with code that correctly reports the smallest value in the array and its index. To do so, loop across the array and check whether the element you are currently viewed is the smallest element encountered thus far. Store intermediate results in temporary variables, as needed.

  5. Swapping Array Elements
  6. Add a function, swapLocations(), to your program that takes as parameters an array of floats as well as two integer values, which are the indices of two array elements. The function should then swap the values in those locations, and return a Boolean value of true if the swap was successful.

    Note that the only time a swap should be unsuccessful (and therefore return false) is if one of the locations indicated by the parameters is outside the bounds of the array (e.g., if the first location given as a parameter is ≥ 50, etc).

    Careful! A naive implementation can accidentally erase one of the values being swapped. Make sure you use a three-step swap: (1) move the first value to a placeholder variable, (2) move the second value to the first's location, and finally (3) copy the placeholder's value into the second location.

    Finally, test your function by pasting the following code at the end of your main() function:
        cout << "Index: 14, Value: " << items[14] << endl
             << "Index: 17, Value: " << items[17] << endl;
        if(swapLocations(items, 14, 17))
            cout << "Index: 14, Value: " << items[14] << endl
                 << "Index: 17, Value: " << items[17] << endl;
        else
            cout << "Error swapping elements." << endl;
    

  7. Bubble Sort
  8. Now we will implement Bubble Sort, a basic sorting algorithm, in order to arrange the array into descending order. Here is a simple pseudocode implementation of the procedure:

    procedure Bubble Sort( Array : a list of values )
        do
            sorted = true
            for each i in Array, except the last
                if Array[i] < Array[i+1] then
                    sorted = false
                    swap(i, i+1)
                end if
            end for each
        while not sorted
    end procedure
    

    In essence, we step through the entire array, and compare adjacent values. When they are out of order, we will swap their locations. We will repeat this process until we manage to pass through the entire array without swapping any elements, at which point we are done! Note that, intuitively speaking, we can expect this process to terminate, because after every pass of the array, the elements in the array are "closer" to being sorted than they were before.

    Implement Bubble Sort as a function in your program.

    Finally, test your function by pasting the following code at the end of your main() function:

        cout << "Sorting array..." << endl;
        bubbleSort(items);
    
        for(int i = 0; i < 20; i++)
            cout << items[i] << " ";
        cout << endl;
    

  9. Submit Work
  10. To submit your lab work, have your TA check over any code/output that you've done during this lab session and record that you completed the lab assignment.

    Important Note: It is your responsibility, not the TA's, to ensure that your lab is recorded as being completed before you leave! Although the labs are intended to be completed in the alloted lab time, if you need additional time to finish the lab assignment, you have 24 hours from the end of the lab meeting time to finish. If so, you should ask your TA for instructions on how to submit the lab assignment after the lab ends.

  11. Logout of the System

    After making sure that you submitted the code correctly and you have done the entire assignment, logout of the system by clicking on the menu button in the lower left hand side of the desktop. Then, click on Log Off. Wait a few seconds for a window to pop up and then click Log Off.