Lab 13A: Searching and Sorting

Objectives:

In this lab, we will practice:

Linear search
Sorting

Background

Linear search is an algorithm that looks for an element in an array. It starts at the first index, compares that element with the query. If they are identical, it will return that index. Otherwise, it continues on to the next element and compares that element with the query. This continues until the last element of the array. If the item is not found in the array, it is common to return -1.
Algorithmically,

for each index, pos, 0 to size - 1
    if the element at index pos is identical to the query, then
    return pos
    otherwise, increment pos
return -1

Selection sort is an algorithm that sorts the elements in an array. It starts by locating the index of the smallest element in the array, and swapping it with what is in the first index. For example, given the following array of numbers:

Selection sort would first swap 6 and 0:

Notice that the 0 is in it's final location. Here, the pink color indicates the sorted region of the array. Next, it would locate the smallest element in the unsorted portion of the array. This iteration, it is 2. Then, it would swap 4 and 2:

Next, it would locate the smallest element in the unsorted portion of the array. This iteration, it is 4. Then, it would swap 4 and 4:

Next, it would locate the smallest element in the unsorted portion of the array. This iteration, it is 6. Then, it would swap 8 and 6:

At this point, there's only one element in the unsorted portion of the array, so we know that it is sorted as well:

Algorithmically,

for each index, pos, 0 to size - 1 - 1
    find the index of the smallest element in the unsorted portion of the array by searching the elements from pos to size - 1
    swap the smallest element with the element at pos
    increment pos

Assignment:

Develop algorithms to perform linear searching and selection sorting. Implement each of your algorithms in a separate function in a single new project (within your existing CodeLite workspace). Use the 2170 template for this and all CodeLite projects.
First, have the program prompt the user to read in 10 numbers and store them in an array. (Use good programming technique by making the program flexible and able to handle a higher count of numbers by only changing a single identifier.) Then, prompt the user for a number to search for. Use your linear search algorithm to find the index of that number. Display the index of that number (or -1 if it's not in the array). Then, perform a Selection Sort on all of the numbers (in the array).

Example

Typing the following on the command-line:

echo "99 55 44 33 77 66 11 22 33 88 55" | ./lab13A

your program should match the following output exactly: (user input in bold text)

Please enter 10 numbers: 
You entered:
99
55
44
33
77
66
11
22
33
88

Please enter a number to search for: 
You entered 55
55 is located at index 1

All elements sorted in ascending order:
11
22
33
33
44
55
66
77
88
99

Submission

Submit your source code using the handin program. For handin, for this lab, type the following in a terminal window exactly as it appears:

handin  lab13A  main.cpp

To verify your submission, type the following in a terminal window:

handin  lab13A

Rubric:

Points  Item
------  --------------------------------------------------------------
10      Documentation
        Header comment block at the beginning of each file with:
        + Your full name
        + Date(s) code was written
        + Description
        Comments explaining the role of each variable and major section of code

40      Correctness
        Program solves the assigned problem using methods described in program description
	+ Prompts the user for 10 numbers
        + Stores those numbers in an array
        + Performs linear search
        + Sorts the numbers in ascending order
        Program compiles without errors
        Program executes without crashing
        Program produces the correct output
------  --------------------------------------------------------------
50      Total

CSCI 2170