//pizza03.cpp
//Authors: AOU
//Date 03/27/2002
//Project #4
//Write pure recursive version of sortSelection1
//Due 4/3/2002
/////////////////////////////////////////////////////////////////
// include files
/////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <time.h>
#include <stdlib.h>
/////////////////////////////////////////////////////////////////
// constants
/////////////////////////////////////////////////////////////////
const int MAX_COUNT = 20;
/////////////////////////////////////////////////////////////////
// prototypes
/////////////////////////////////////////////////////////////////
void sortBubble(int array[], int low, int high);
void displayArray1(int array[], int low, int high);
void displayArray2(int array[], int low, int high);
int min1(int array[], int low, int high);
int min2(int array[], int low, int high);
void sortSelection1(int array[], int low, int high);
void buildArray(int array[], int &low, int &high);
bool isSorted(int array[], int low, int high);
/////////////////////////////////////////////////////////////////
// main
/////////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
int a[MAX_COUNT], low, high;
for (int i=1; i<=10; i++)
{
int k;
buildArray(a, low, high);
displayArray1(a, low, high);
k = min1(a, low, high);
cout << "minimum is at " << k << ": " << a[k] << endl;
if (isSorted(a, low, high))
cout << "array is sorted\n";
else
cout << "array is NOT sorted\n";
//replace with sortSelection2(a, low, high);
sortSelection1(a, low, high);
k = min2(a, low, high);
cout << "minimum is at " << k << ": " << a[k] << endl;
cout << "After sort\n";
displayArray2(a, low, high);
if (isSorted(a, low, high))
cout << "array is sorted\n";
else
cout << "array is NOT sorted\n";
cout << "=================================\n";
}
}
/////////////////////////////////////////////////////////////////
// buildArray
/////////////////////////////////////////////////////////////////
void buildArray(int array[], int &low, int &high)
{
low = 0;
high = rand()%MAX_COUNT;
for (int i=0; i<=high; i++)
array[i] = 10 + rand()%90;
}
/////////////////////////////////////////////////////////////////
// isSorted
/////////////////////////////////////////////////////////////////
bool isSorted(int array[], int low, int high)
{
for (int i=low; i<high; i++)
if (array[i] > array[i+1])
return false;
return true;
}
/////////////////////////////////////////////////////////////////
// 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;
}
}
/////////////////////////////////////////////////////////////////
// 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;
}
/////////////////////////////////////////////////////////////////
// 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);
}
}
/////////////////////////////////////////////////////////////////
// sortBubble to sort array elements (non-recursive)
/////////////////////////////////////////////////////////////////
void sortBubble(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
/////////////////////////////////////////////////////////////////
/*
84 27 44 33 35 58 91 52 72 98 96 22 90 43 25 21 46 77 76 83
minimum is at 15: 21
array is NOT sorted
minimum is at 0: 21
After sort
21 22 25 27 33 35 43 44 46 52 58 72 76 77 83 84 90 91 96 98
array is sorted
=================================
58 31 44 70 83 54 27 56 20 13
minimum is at 9: 13
array is NOT sorted
minimum is at 0: 13
After sort
13 20 27 31 44 54 56 58 70 83
array is sorted
=================================
74 18
minimum is at 1: 18
array is NOT sorted
minimum is at 0: 18
After sort
18 74
array is sorted
=================================
62
minimum is at 0: 62
array is sorted
minimum is at 0: 62
After sort
62
array is sorted
=================================
13 26 19
minimum is at 0: 13
array is NOT sorted
minimum is at 0: 13
After sort
13 19 26
array is sorted
=================================
96 48 18 19 44 63 78 73 88 29 45 17 72 70 97 13
minimum is at 15: 13
array is NOT sorted
minimum is at 0: 13
After sort
13 17 18 19 29 44 45 48 63 70 72 73 78 88 96 97
array is sorted
=================================
35 37 36 90 61 52 40 11 28 97 44 12 95
minimum is at 7: 11
array is NOT sorted
minimum is at 0: 11
After sort
11 12 28 35 36 37 40 44 52 61 90 95 97
array is sorted
=================================
32 70 51 85 35 28
minimum is at 5: 28
array is NOT sorted
minimum is at 0: 28
After sort
28 32 35 51 70 85
array is sorted
=================================
34 16 38 89 19 54 63 58 39 92 20 39 93 41 50 38 43 96
minimum is at 1: 16
array is NOT sorted
minimum is at 0: 16
After sort
16 19 20 34 38 38 39 39 41 43 50 54 58 63 89 92 93 96
array is sorted
=================================
29 46 16 74 15 28 55 83 54 10
minimum is at 9: 10
array is NOT sorted
minimum is at 0: 10
After sort
10 15 16 28 29 46 54 55 74 83
array is sorted
=================================
Press any key to continue
*/ |