//sortedList08.cpp
//date: 09/25/2002
//author: AOU
////////////////////////////////////////////////////////////
// Include files
////////////////////////////////////////////////////////////
#include<iostream.h>
#include<math.h>
#include<stdlib.h>
#include<time.h>
////////////////////////////////////////////////////////////
// Constants
////////////////////////////////////////////////////////////
const int ARRAY_SIZE = 80;
const int UNDEFINED = -9999;
const int MAX_VALUE = 10;
////////////////////////////////////////////////////////////
// Test function prototypes
////////////////////////////////////////////////////////////
void testSortBubble2(void);
void testSearchSeq(void);
void testSearchBinary(void);
void testSearchBinaryLM(void);
////////////////////////////////////////////////////////////
// Class CSortedList
////////////////////////////////////////////////////////////
class CSortedList
{
private:
int m_array[ARRAY_SIZE];
int m_count;
int m_min;
int m_max;
void sortBubble1(void);
public:
CSortedList(void);
CSortedList(char ch);
void display(void);
bool insert(int x);
bool isSorted(void);
void sortBubble2(void);
void shuffle(void);
int searchSeq(int x);
int searchBinary(int x); //2002.09.23
int searchBinaryLM(int x); //2002.09.25
};
////////////////////////////////////////////////////////////
// main function
////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//testSortBubble2();
//testSearchSeq();
//testSearchBinary();
testSearchBinaryLM();
}
////////////////////////////////////////////////////////////
// searchBinaryLM(x)
////////////////////////////////////////////////////////////
/*
Given sorted array[0..count-1], x
[12, 23, 23, 29, 32], 23 => 1
[12, 23, 27, 27, 32], 24 => 2
Algorithm0:
Find the position of x in p using binary search
if not found then return -1
while (value at p-1 is same as at p)
p--
end while
*/
int CSortedList::searchBinaryLM(int x)
{
int p;
p = this->searchBinary(x);
if (-1 == p)
return -1;
while((p>0) && (this->m_array[p] == this->m_array[p-1]))
p--;
return p;
}
void testSearchBinaryLM(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p1, p2;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p1 = myList.searchBinaryLM(x);
cout << x << " was found at position " << p1 << endl;
p2 = myList.searchSeq(x);
cout << x << " was found at position " << p2 << endl;
if (p1 != p2)
cout << "***************************\n";
cout << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// searchBinary(x)
////////////////////////////////////////////////////////////
/*
Given sorted array[0..count-1], x
[12, 23, 27, 29, 32], 27 => 2
[12, 23, 27, 29, 32], 24 => -1
Algorithm0:
while there is a list to be searched
calculate mid point of the list to be searched
if x = array[mid] then return mid
find out which half of the list to be searched
end while
Algorithm1:
*/
int CSortedList::searchBinary(int x)
{
int lower, upper, mid;
lower = 0;
upper = this->m_count-1;
while (lower <= upper)
{
mid = (lower+upper)/2;
if (x == this->m_array[mid])
return mid;
if (x < this->m_array[mid])
upper = mid-1;
if (x > this->m_array[mid])
lower = mid+1;
}
return -1;
}
void testSearchBinary(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p = myList.searchBinary(x);
cout << x << " was found at position " << p << endl;
p = myList.searchSeq(x);
cout << x << " was found at position " << p << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// searchSeq(x)
////////////////////////////////////////////////////////////
/*Given sorted array[0..count-1], x
[12, 23, 27, 29, 32], 27 => 2
[12, 23, 27, 29, 32], 24 => -1
Algorithm0:
search for x from left to right in array[]
if found return the position
return -1
Algorithm1:
for i=0 to count-1 do the following
if x = array[i] then return i
end for
return -1
Algorithm2:
for i=0 to count-1 do the following
if x = array[i] then return i
if x < array[i] then exit for loop
end for
return -1
*/
int CSortedList::searchSeq(int x)
{
for (int i=0; i<=this->m_count-1; i++)
{
if (x == m_array[i])
return i;
if (x < this->m_array[i])
break;
}
return -1;
}
void testSearchSeq(void)
{
for (int j=1; j<=5; j++)
{
CSortedList myList('r');
int x, p;
myList.display();
for (int i=0; i<10; i++)
{
x = rand()%(MAX_VALUE+1);
p = myList.searchSeq(x);
cout << x << " was found at position " << p << endl;
}
cout << "-----------------\n";
}
}
////////////////////////////////////////////////////////////
// CSortedList(void)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(void)
{
this->m_count = 0;
this->m_min = UNDEFINED;
this->m_max = UNDEFINED;
}
////////////////////////////////////////////////////////////
// CSortedList(char ch)
////////////////////////////////////////////////////////////
CSortedList::CSortedList(char ch)
{
this->m_count = 0;
int x, n;
if ('r' == ch)
{
n = rand()%ARRAY_SIZE+1;
for (int i=0; i<n; i++)
{
x = rand()%(MAX_VALUE+1);
this->insert(x);
}
}
}
////////////////////////////////////////////////////////////
// display(void)
////////////////////////////////////////////////////////////
void CSortedList::display(void)
{
cout << "SortedList(" << this->m_count << ")= ";
for (int i=0; i<this->m_count; i++)
cout << this->m_array[i] << ' ';
cout << endl;
}
////////////////////////////////////////////////////////////
// insert(int x)
////////////////////////////////////////////////////////////
bool CSortedList::insert(int x)
{
//allow duplicate values
/*
there is no room then return false
there is room then add to the end, sort, return true
*/
if (ARRAY_SIZE == this->m_count)
return false;
else
{
this->m_array[m_count] = x;
this->m_count++;
this->sortBubble1();
return true;
}
}
////////////////////////////////////////////////////////////
// sortBubble1(void)
////////////////////////////////////////////////////////////
void CSortedList::sortBubble1(void)
{
int j;
for (int i=1; i<=this->m_count-1; i++)
{
for (j=0; j<=this->m_count-2; j++)
{
if (this->m_array[j] > this->m_array[j+1])
{
int temp = this->m_array[j];
this->m_array[j] = this->m_array[j+1];
this->m_array[j+1] = temp;
}
}
}
}
////////////////////////////////////////////////////////////
// sortBubble2(void)
////////////////////////////////////////////////////////////
/*
Algorithm0:
do
swaps =0
make one pass trying to put items in order
until swaps == 0
Algorithm1:
sorted = false
while not sorted
sorted = true
make one pass trying to put items in order
end while
Algorithm2:
sorted = false
while not sorted
sorted = true
for i= 0 to m_count-2 do the following
if m_array[i] > m_array[i+1] then
swap m_array[i], m_array[i+1]
sorted = false
end if
end for
end while
*/
void CSortedList::sortBubble2(void)
{
}
////////////////////////////////////////////////////////////
// testSortBubble2(void)
////////////////////////////////////////////////////////////
void testSortBubble2(void)
{
for (int i=1; i<=10; i++)
{
CSortedList myList('r');
cout << "Original list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.shuffle();
cout << "Shuffled list\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
myList.sortBubble2();
cout << "After sortBubble2\n";
myList.display();
if (myList.isSorted())
cout << " List is SORTED\n";
else
cout << " List is NOT SORTED\n";
cout << "-------------------\n";
}
}
////////////////////////////////////////////////////////////
// isSorted(void)
////////////////////////////////////////////////////////////
bool CSortedList::isSorted(void)
{
return true;
}
////////////////////////////////////////////////////////////
// shuffle(void)
////////////////////////////////////////////////////////////
void CSortedList::shuffle(void)
{
int picked, temp;
for (int i=0; i<=this->m_count-1; i++)
{
picked = rand()%this->m_count;
temp = this->m_array[0];
this->m_array[0] = this->m_array[picked];
this->m_array[picked] = temp;
}
}
/*
SAMPLE RUN:
SortedList(59)= 0 0 0 0 0 0 1 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 4 4 4 5 5 5 5 6 6 6
6 6 6 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 9 9 9 10 10 10 10 10 10
7 was found at position 35
7 was found at position 35
7 was found at position 35
7 was found at position 35
5 was found at position 25
5 was found at position 25
10 was found at position 53
10 was found at position 53
7 was found at position 35
7 was found at position 35
3 was found at position 11
3 was found at position 11
9 was found at position 47
9 was found at position 47
0 was found at position 0
0 was found at position 0
8 was found at position 37
8 was found at position 37
4 was found at position 18
4 was found at position 18
-----------------
SortedList(21)= 0 0 0 0 2 2 2 3 4 4 5 6 6 7 7 7 8 8 8 9 10
3 was found at position 7
3 was found at position 7
8 was found at position 16
8 was found at position 16
8 was found at position 16
8 was found at position 16
9 was found at position 19
9 was found at position 19
6 was found at position 11
6 was found at position 11
3 was found at position 7
3 was found at position 7
10 was found at position 20
10 was found at position 20
5 was found at position 10
5 was found at position 10
2 was found at position 4
2 was found at position 4
2 was found at position 4
2 was found at position 4
-----------------
SortedList(21)= 0 0 0 2 3 3 3 4 4 5 7 7 8 8 8 9 9 9 10 10 10
9 was found at position 15
9 was found at position 15
1 was found at position -1
1 was found at position -1
4 was found at position 7
4 was found at position 7
7 was found at position 10
7 was found at position 10
7 was found at position 10
7 was found at position 10
7 was found at position 10
7 was found at position 10
5 was found at position 9
5 was found at position 9
5 was found at position 9
5 was found at position 9
2 was found at position 3
2 was found at position 3
8 was found at position 12
8 was found at position 12
-----------------
SortedList(41)= 0 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 4 4 5 5 6 6 6 6 7 7 7 7 8 8 8 8
8 9 9 9 10 10 10 10 10
4 was found at position 16
4 was found at position 16
4 was found at position 16
4 was found at position 16
7 was found at position 24
7 was found at position 24
9 was found at position 33
9 was found at position 33
4 was found at position 16
4 was found at position 16
0 was found at position 0
0 was found at position 0
5 was found at position 18
5 was found at position 18
10 was found at position 36
10 was found at position 36
6 was found at position 20
6 was found at position 20
2 was found at position 4
2 was found at position 4
-----------------
SortedList(39)= 0 0 0 1 1 1 1 5 5 5 5 5 5 5 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 8 8 8
9 9 9 9 10 10 10
7 was found at position 19
7 was found at position 19
3 was found at position -1
3 was found at position -1
9 was found at position 32
9 was found at position 32
8 was found at position 29
8 was found at position 29
2 was found at position -1
2 was found at position -1
10 was found at position 36
10 was found at position 36
5 was found at position 7
5 was found at position 7
6 was found at position 14
6 was found at position 14
4 was found at position -1
4 was found at position -1
8 was found at position 29
8 was found at position 29
-----------------
Press any key to continue
*/
|