//Project05_pizza04.cpp
//Authors: AOU
//Date 04/011/2002
// Includes solution to project #5
//Project #5
//Write non-recursive and pure recursive version of
// reverse function
//Due 04/19/2002
/////////////////////////////////////////////////////////////////
// include files
/////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
/////////////////////////////////////////////////////////////////
// constants
/////////////////////////////////////////////////////////////////
const int MAX_COUNT = 30;
const int TEST_COUNT = 5;
/////////////////////////////////////////////////////////////////
// prototypes
/////////////////////////////////////////////////////////////////
void swap(int &x, int &y);
void displayArray1(int array[], int low, int high);
void displayArray2(int array[], int low, int high);
void buildArray1(int array[], int low, int high);
void testBuildArray1(void);
void buildArray2(int array[], int low, int high);
void testBuildArray2(void);
int min1(int array[], int low, int high);
void testMin1(void);
int min2(int array[], int low, int high);
void testMin2(void);
void reverse1(int array[], int low, int high);
void testReverse1(void);
void reverse2(int array[], int low, int high);
void testReverse2(void);
void sortSelection1(int array[], int low, int high);
void testSortSelection1(void);
void sortSelection2(int array[], int low, int high);
void testSortSelection2(void);
bool isSorted1(int array[], int low, int high);
void testSorted1(void);
bool isSorted2(int array[], int low, int high);
void testSorted2(void);
void sortBubble1(int array[], int low, int high);
void testSortBubble1(void);
void sortBubble2(int array[], int low, int high);
void testSortBubble2(void);
void bubbleDown(int array[], int low, int high);
void sortInsertion1(int array[], int low, int high);
void testSortInsertion1(void);
void sortInsertion2(int array[], int low, int high);
void testSortInsertion2(void);
/////////////////////////////////////////////////////////////////
// main
/////////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//testBuildArray1();
//testBuildArray2();
//testMin1();
//testMin2();
testReverse1();
testReverse2();
//testSortSelection1();
//testSortSelection2();
//testIsSorted1();
//testIsSorted2();
//testSortBubble1();
//testSortBubble2();
//testSortInsertion1();
//testSortInsertion2();
}
/////////////////////////////////////////////////////////////////
// swap
/////////////////////////////////////////////////////////////////
void swap(int &x, int &y)
{
if (x != y)
{
int temp = x;
x = y;
y = temp;
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortInsertion2(void)
{
cout << "testSortInsertion2\n";
cout << "==================\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray2(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortInsertion2(a, low, high);
cout << "sortInsertion2 ";
displayArray2(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
cout << "-------------------------------------------\n";
}
}
/////////////////////////////////////////////////////////////////
//shift array to right to find place for element
/////////////////////////////////////////////////////////////////
int shifter(int array[], int j, int element)
{
if ((j >= 0) && (element < array[j]))
{
array[j+1] = array[j];
return shifter(array, j-1, element);
}
else
return j;
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void sortInsertion2(int array[], int low, int high)
{
if (low < high)
{
int element = array[low+1];
int j = low;
int position = shifter(array, j, element);
array[position+1] = element;
sortInsertion2(array, low+1, high);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortInsertion1(void)
{
cout << "testSortInsertion1\n";
cout << "==================\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortInsertion1(a, low, high);
cout << "sortInsertion1 ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void sortInsertion1(int array[], int low, int high)
{
if (low == high)
return;
for (int i=low+1; i<=high; i++)
{
//insert the ith value at the right position
int k = i;
while (k > 0)
{
if (array[k] >= array[k-1])
break;
else
{
swap(array[k], array[k-1]);
k--;
}
}
cout << "Inserting value " << array[k] << " at " << k << ": ";
displayArray1(array, low, high);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testReverse1(void)
{
cout << "testReverse1\n";
cout << "============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
reverse1(a, low, high);
cout << "After reverse1: ";
displayArray1(a, low, high);
cout << "----------------------\n";
}
}
/////////////////////////////////////////////////////////////////
// reverse1
/////////////////////////////////////////////////////////////////
void reverse1(int array[], int low, int high)
{
if (low == high)
return;
else
{
int swapCount = (high-low+1)/2;
for (int i=0; i<swapCount; i++)
swap(array[low+i], array[high-i]);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testReverse2(void)
{
cout << "testReverse2\n";
cout << "============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
reverse2(a, low, high);
cout << "After reverse2: ";
displayArray1(a, low, high);
cout << "----------------------\n";
}
}
/////////////////////////////////////////////////////////////////
// reverse2
/////////////////////////////////////////////////////////////////
void reverse2(int array[], int low, int high)
{
if (low >= high)
return;
else
{
swap(array[low], array[high]);
reverse2(array, low+1, high-1);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortSelection2(void)
{
cout << "testSortSelection2\n";
cout << "==================\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
sortSelection2(a, low, high);
cout << "sortSelection2: ";
displayArray1(a, low, high);
}
}
/////////////////////////////////////////////////////////////////
// sortSelection2
/////////////////////////////////////////////////////////////////
void sortSelection2(int array[], int low, int high)
{
if (low == high)
return;
else
{
//find the index of minimum from i to high in k
int k = min2(array, low, high);
//swap values at k and low
int tValue = array[low];
array[low] = array[k];
array[k] = tValue;
//call sortSelection2 recursively ignoring the value at low
sortSelection2(array, low+1, high);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testBuildArray1(void)
{
cout << "testBuildArray1\n";
cout << "===============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
displayArray1(a, low, high);
displayArray2(a, low, high);
}
}
/////////////////////////////////////////////////////////////////
// buildArray1
/////////////////////////////////////////////////////////////////
void buildArray1(int array[], int low, int high)
{
for (int i=0; i<=high; i++)
array[i] = 10 + rand()%90;
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testBuildArray2(void)
{
cout << "testBuildArray2\n";
cout << "===============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray2(a, low, high);
displayArray1(a, low, high);
displayArray2(a, low, high);
}
}
/////////////////////////////////////////////////////////////////
// buildArray2
/////////////////////////////////////////////////////////////////
void buildArray2(int array[], int low, int high)
{
array[low] = rand()%90;
if (low < high)
buildArray2(array, low+1, high);
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testIsSorted1(void)
{
cout << "testIsSorted1\n";
cout << "=============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
if (isSorted1(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortSelection1(a, low, high);
cout << "sortSelection1: ";
displayArray1(a, low, high);
if (isSorted1(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
}
}
/////////////////////////////////////////////////////////////////
// isSorted1
/////////////////////////////////////////////////////////////////
bool isSorted1(int array[], int low, int high)
{
for (int i=low; i<high; i++)
if (array[i] > array[i+1])
return false;
return true;
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testIsSorted2(void)
{
cout << "testIsSorted2\n";
cout << "=============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortSelection1(a, low, high);
cout << "sortSelection1: ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
}
}
/////////////////////////////////////////////////////////////////
// isSorted2
/////////////////////////////////////////////////////////////////
/*
version 0:
if the list has one element then
return true
else if first element > next element then
return flase
else
check if the rest of the list is sorted
version 1:
if low == high then
return true
else if array[low] > array[low+1] then
return flase
else
return isSorted2(array, low+1, high)
*/
bool isSorted2(int array[], int low, int high)
{
if (low == high)
return true;
else if (array[low] > array[low+1])
return false;
else
return isSorted2(array, low+1, high);
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortSelection1(void)
{
cout << "testSortSelection1\n";
cout << "==================\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
sortSelection1(a, low, high);
cout << "sortSelection1: ";
displayArray1(a, low, high);
}
}
/////////////////////////////////////////////////////////////////
// sortSelection1
/////////////////////////////////////////////////////////////////
/*Example:
{3, 2, 1, 6, 4}
1, {2, 3, 6, 4}
1, 2, {3, 6, 4}
1, 2, 3, {6, 4}
1, 2, 3, 4, {6}
Plan:
Find the position of the minimum value
swap it with the fist value
ignore the first value
do the same thing with the remaining values
do the following for i=low to high-1
find the index of minimum from i to high in k
swap values at k and i
end do
*/
void sortSelection1(int array[], int low, int high)
{
for (int i=low; i<=high-1; i++)
{
//find the index of minimum from i to high in k
int k = min1(array, i, high);
//swap values at k and i
int tValue = array[k];
array[k] = array[i];
array[i] = tValue;
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testMin1(void)
{
cout << "testMin1\n";
cout << "========\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
displayArray1(a, low, high);
int m = min1(a, low, high);
cout << "Minimum at " << m << " is " << a[m] << endl;
}
}
/////////////////////////////////////////////////////////////////
// min1 to return the index of minimum value (non-recursive)
/////////////////////////////////////////////////////////////////
int min1(int array[], int low, int high)
{
/*
index of the minimum value?
minYet = low
compare value at minYet with every value in the list
if a value is < value at minYet then
copy index of that value to minYet
return minYet
*/
/*
minYet = low
for i= low to high
if array[i] < array[minYet]
minYest = i
return minYet
*/
int minYet = low;
for (int i= low; i<=high; i++)
if (array[i] < array[minYet])
minYet = i;
return minYet;
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testMin2(void)
{
cout << "testMin2\n";
cout << "========\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
displayArray1(a, low, high);
int m = min2(a, low, high);
cout << "Minimum at " << m << " is " << a[m] << endl;
}
}
/////////////////////////////////////////////////////////////////
// min2 to return the index of minimum value (non-recursive)
/////////////////////////////////////////////////////////////////
int min2(int array[], int low, int high)
{
if (low == high)
return low;
int minYet1 = low;
int minYet2 = min2(array, low+1, high);
if (array[minYet1] < array[minYet2])
return minYet1;
else
return minYet2;
}
/////////////////////////////////////////////////////////////////
// displayArray1 to display array elements (non-recursive)
/////////////////////////////////////////////////////////////////
void displayArray1(int array[], int low, int high)
{
for (int i=low; i<= high; i++)
cout << array[i] << ' ';
cout << endl;
}
/////////////////////////////////////////////////////////////////
// displayArray2 to display array elements (recursive)
/////////////////////////////////////////////////////////////////
void displayArray2(int array[], int low, int high)
{
/*
if only one element to be printed then
print that element
else
print the fist element
display the rest
-----------------------
if low and high are the same
print element at low
else
print element at low
display (array, low+1, high)
*/
if (low == high)
cout << array[low] << endl;
else
{
cout << array[low] << ' ';
displayArray2(array, low+1, high);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortBubble2(void)
{
cout << "testSortBubble2\n";
cout << "===============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortBubble2(a, low, high);
cout << "sortBubble2: ";
displayArray1(a, low, high);
if (isSorted2(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
}
}
/////////////////////////////////////////////////////////////////
// sortBubble2 to sort array elements (recursive)
/////////////////////////////////////////////////////////////////
/*
version0:
if only one element in the list then
return
else
bubbleUp the lowest value low to high
sortBubble2(low+1, high)
version1:
if more than one element in the list then
bubbleUp the lowest value low to high
sortBubble2(low+1, high)
version2:
if low < high then
bubbleUp(array, low, high)
sortBubble2(low+1, high)
*/
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void sortBubble2(int array[], int low, int high)
{
if (low < high)
{
bubbleDown(array, low, high);
sortBubble2(array, low, high-1);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
// bubbleDown(array, low, high)
/*
put the highest value at the bottom
version0:
if more than one element then
put the first two elements in order
do the same thing for the list low+1 to high
*/
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void bubbleDown(int array[], int low, int high)
{
if (low < high)
{
if (array[low] > array[low+1])
swap(array[low], array[low+1]);
bubbleDown(array, low+1, high);
}
}
/////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////
void testSortBubble1(void)
{
cout << "testSortBubble1\n";
cout << "===============\n";
for (int i=1; i<=TEST_COUNT; i++)
{
int a[MAX_COUNT], low, high;
low = 0;
high = rand()%MAX_COUNT;
buildArray1(a, low, high);
cout << "Original array: ";
displayArray1(a, low, high);
if (isSorted1(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
sortBubble1(a, low, high);
cout << "sortBubble1: ";
displayArray1(a, low, high);
if (isSorted1(a, low, high))
cout << " Array is sorted\n";
else
cout << " Array is not sorted\n";
}
}
/////////////////////////////////////////////////////////////////
// sortBubble1 to sort array elements (non-recursive)
/////////////////////////////////////////////////////////////////
void sortBubble1(int array[], int low, int high)
{
bool sorted;
do
{
sorted = true;
for (int i=low; i<high; i++)
{
if (array[i] > array[i+1])
{
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
sorted = false;
}
}
}
while (!sorted);
}
/////////////////////////////////////////////////////////////////
// Output
/////////////////////////////////////////////////////////////////
/*
testReverse1
============
Original array: 41 79 92 59 62 10 51 66 30 81 66 82 11 39 27 26 75 78 10 32 68 4
5
After reverse1: 45 68 32 10 78 75 26 27 39 11 82 66 81 30 66 51 10 62 59 92 79 4
1
----------------------
Original array: 69 77 35 72 99 67 91 79 78 15 34 99
After reverse1: 99 34 15 78 79 91 67 99 72 35 77 69
----------------------
Original array: 96 16 30 73 22 16 50 96 90 34
After reverse1: 34 90 96 50 16 22 73 30 16 96
----------------------
Original array: 24 99 65 19 24 69 53 22 58 53 97 81 55
After reverse1: 55 81 97 53 58 22 53 69 24 19 65 99 24
----------------------
Original array: 13 15 18 12 97
After reverse1: 97 12 18 15 13
----------------------
testReverse2
============
Original array: 33 81 51 92 12 76 83
After reverse2: 83 76 12 92 51 81 33
----------------------
Original array: 68 21 56 67 91 39 62
After reverse2: 62 39 91 67 56 21 68
----------------------
Original array: 64 81 53 61 55 31 71 69 68 12 64 43
After reverse2: 43 64 12 68 69 71 31 55 61 53 81 64
----------------------
Original array: 28 63 54 89 21 17 23 46 13 23 42 98 28 78 64 83 58 44 81 98 75 3
8 50 63 61
After reverse2: 61 63 50 38 75 98 81 44 58 83 64 78 28 98 42 23 13 46 23 17 21 8
9 54 63 28
----------------------
Original array: 54 27 57 22 87 29 22 11
After reverse2: 11 22 29 87 22 57 27 54
----------------------
Press any key to continue
*/
|