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:
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:
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.:
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?