The objectives for this lab are to analyze a variety of algorithms of various complexities.

Data Cleanup, also called Array Packing, is a very important algorithm that has many applications with real data.

It is also a convenient example since there is more than one algorithm for the problem and there is no clear "winner" of the three algorithms. Each has their own advantages and disadvantages.

For each Algorithm you are to try the following example arrays:

1 0 3 4 5 |

1 2 3 4 5 |

0 0 0 0 0 |

1 2 0 4 5 6 7 8 0 10 |

Each example array will have to be entered separately in the Input

For each example:

- Record the example used
- Record the result
- Record the number of steps (note: all the steps are not counted. See instructions for each example)
- Check the correctness of the solution

We are using the values 1 - 5 and 1 - 10 in the lists to make them easier to enter and record data. Actually, we could replace any non-0 value in the list and get the same number of steps.

Here is the Shuffle-Left Algorithm:

**Example 1. Shuffle-Left Algorithm**

Steps for Shuffle Left with Array A Set the value of Size to the value of A.length Set the value of I to 0 While I < Size Do If A[I] is equal to 0 Then Set the value of J to the value of I While J < (Size - 1) Do Set the value of A[J] to the value of A[J + 1] Set the value of J to the value of J + 1 Endwhile Set the value of Size to the value of Size - 1 Else Set the value of I to the value of I + 1 Endif Endwhile Stop

It uses the Shift Left Algorithm shown earlier.

Use the lists and record the data as shown in the Data Cleanup Algorithm section. For the number of steps, count the number of times that the statement **Set the value of A[J] to the value of A[J + 1]** is reached. This is the number of copies done.

Record whether the algorithm's solution is correct. In this case, after running the algorithm, the good data items should be packed in the left end of Array A, and the value of size should indicate the number of non-zero values in the initial array.

Here is the Copy Over Algorithm:

**Example 2. Copy-Over Algorithm**

Steps for Copy Over with Array A Set the value of I to 0 Set the value of J to 0 While I < A.length Do If A[I] is not equal to 0 Then Set the value of B[J] to the value of A[I] Set the value of J to the value of J + 1 Endif Set the value of I to the value of I + 1 Endwhile If the value of J is equal to 0 Then Set the value of Size to 0 Otherwise Set the value of Size to the value of B.length Set the value of I to 0 While I < Size Do Set the value of A[I] to the value of B[I] Set the value of I to the value of I + 1 Endwhile Endif Stop

It uses a Copy Array Subalgorithm. This just copies from one array to another.

Use the lists and record the data as shown in the Data Cleanup Algorithm section. For the number of steps, count the number of times that the statement **Set the value of B[J] to the value of A[I]** is reached. Again, this is the number of copies done.

Record whether the algorithm's solution is correct.

Here is the Converging Pointers Algorithm:

**Example 3. Converging Pointers Algorithm**

Steps for Converging Pointers with Array A Set the value of Size to A.length Set the value of I to 0 While I < Size -1 Do If A[I] is equal to 0 Then Set the value of A[I] to the value of A[Size - 1] Set the value of Size to the value of Size - 1 Else Set the value of I to the value of I + 1 Endif Endwhile If A[Size - 1] is equal to 0 Then Set the value of Size to the value of Size - 1 Endif Stop

Use the lists and record the data as shown in the Data Cleanup Algorithm section. For the number of steps, count the number of times that the statement **Set the value of A[I] to the value of A[Size - 1]** is reached. This is the number of copies done.

Record whether the algorithm's solution is correct.

The Selection Sort will take a list of numbers and sort them:

**Example 4. Selection Sort Algorithm**

Steps for Selection Sort with Array A Set the value of I to A.length - 1 While I > 0 Do Set the value of L to 0 Set the value of J to 0 While J <= I Do If A[J] > A[L] Then Set the value of L to the value of J Endif Set the value of J to J + 1 Endwhile Set the value of T to the value of A[I] Set the value of A[I] to the value of A[L] Set the value of A[L] to the value of T Set the value of I to I - 1 Endwhile Stop

Try the select sort three times 1) with a list of 4 values in random order, 2) with the same 4 values in ascending order and 3) with the same 4 values in descending order. In each case, record the list of values and the following two items:

- Number of times
**If A[J] > A[L]**is executed ( number of comparisons made) - Number of times
**Set the value of T to the value of A[I]**is executed ( number of swaps done )

.

The Binary Search is another way of finding the position of an item in a list.

**Example 5. Binary Search Algorithm**

Steps for Binary Search with Array A and Value Set the value of Pos to -1 Set the value of Left to 0 Set the value of Right to A.length - 1 While Left <= Right Do Set the value of Middle to (Left + Right) / 2 - (Left + Right) % 2 / 2 If Value is equal to A[Middle] Then Set the value of Pos to Middle Set the value of Left to Right + 1 Endif If Value < A[Middle] Then Set the value of Right to Middle - 1 Endif If Value > A[Middle] Then Set the value of Left to Middle + 1 Endif Endwhile Stop

The ugly formula where we are setting the value of Middle is used to get a middle value between Left and Right that is a whole number. So, for example, if Left were 0 and Right were 7 the middle value would be 3.

Execute the algorithm with this list of 8 values:

2 5 7 9 11 12 14 19

Search for a different value each time. Also try to search for a value, such as 8, which is not in the list. Record the result and the following items for each search is performed.:

- the number of times
**If Value is equal to A[Middle]**is executed. This is the number of values (names) actually looked at when performing the search. Use this value as the number of steps when comparing to other search algorithms.

In the worst case, how many steps ( as counted above) does the algorithm take to find an item in the list?

How many steps does the algorithm take to find that an item is not on the list?