Using Searches and sorts for strings

I've got this code to sort and search random strings. But the time isn't calculating correctly.. Unsure of the issue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <ctime>

using namespace std;

//Functions Prototypes
int Linear(string[],string);
int Binary(string[],string);
void Bubble(string[],int);
void Select(string[],int);
void Fill(string[],int);
string Random(string[]);
string Create();

string Create()
{
    string randStr;
    char alpha[53] = "abcdefghijklmnopqrstuvwxyz"
                     "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    for(int i = 0; i <= 20; i++)
    {
        int randIndx = rand() % 52;
        randStr += alpha[randIndx];
    }
    return randStr;
}

void Fill(string ary[], int cnt)
{
    for(int i = 0; i < cnt; i++)
        ary[i] = Create();
}

void Bubble(string ary[], int cnt)
{
    for(int start = 0; start < cnt; start++)
        for(int index = cnt; index < cnt-1; index++)
            if(ary[index] > ary[index+1])
            {
                string temp = ary[index+1];
                ary[index+1] = ary[index];
                ary[index] = temp;
            }
}

void Select(string ary[], int cnt)
{
    for(int start = 0; start < cnt-1; start++)
    {
        int minIndex = start;

        for(int index = start+1; index < start; index++)
        {
            if(ary[index] < ary[minIndex])
                minIndex = index;

            string temp = ary[minIndex];
            ary[minIndex] = ary[index];
            ary[index] = temp;
        }
    }
}

string Random(string ary[])
{
    int randIndex = rand() % 10999;
    return ary[randIndex];
}

int Linear(string ary[], string goal)
{
    int numProbes = 0;
    for(int i = 0; i < 10999; i++)
    {
        numProbes++;

        if(ary[i] == goal)
            return numProbes;
    }
    return numProbes+1;
}

int Binary(string ary[], string goal)
{
    Bubble(ary, 11000);

    int numProbes=0, first=0, last=10999,
          middle = (first + last)/2;

    while(first <= last)
    {
        numProbes++;

        if(ary[middle] < goal)
            first = middle+1;

        else if(ary[middle] == goal)
            return numProbes;

        else
            last = middle-1;

        middle = (first + last)/2;
    }
    return numProbes+1;
}

int main()
{
    ofstream out("Search.out");

    string ary[11000];
    srand(time(0));

    out << fixed << setprecision(4)
        << "\t\t\t\t\t\t\t Sort & Search Evaluation\n\n\n"
        << "\t\t\t\t\t\tSort\n"
        << " Strings\t\tBubble \t\t   Selection\n"
        << "----------------------------------------------\n";

    for(int start = 1000; start <= 11000; start += 2000)
    {
        switch(start)
        {
            case 1000:
                out << "  1000: ";
                break;

            case 3000:
                out << "  3000: ";
                break;

            case 5000:
                out << "  5000: ";
                break;

            case 7000:
                out << "  7000: ";
                break;

            case 9000:
                out << "  9000: ";
                break;

            case 11000:
                out << " 11000: ";
                break;
        }
        for(int index = 1; index <= 2; index++)
        {
            Fill(ary,start);
            clock_t time = clock();

            if(index == 1)
                Bubble(ary,start);

            else if(index == 2)
                Select(ary,start);

            time -= clock();

            out << "\t\t" << (float)time / CLOCKS_PER_SEC
                << "\t";
        }
        out << "\n----------------------------------------------\n\n";
    }

    out << "\n\t\t\t\t\t\tSearch\n"
        << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
        << " \t\t\t\tLinear\t\t\t\tBinary"
        << "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n";

    Fill(ary, 11000);

    int LinearSearches = 0, BinarySearches = 0; int i = 0;

    for(i = 1; i <= 4500; i++)
    {
        string RandString = Random(ary);
        LinearSearches += Linear(ary, RandString);
        BinarySearches += Binary(ary, RandString);
    }

    out << " Avg Probes:\t" << LinearSearches / (i-1)
        << " \t\t\t\t " << BinarySearches / (i-1)
        << "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n\n";

    out.close();
    return 0;
}

OUTPUT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
							 Sort & Search Evaluation


						Sort
 Strings		Bubble 		   Selection

  1000: 		0.0000			0.0000	

----------------------------------------------

  3000: 		0.0000			0.0000	
----------------------------------------------

  5000: 		0.0000			0.0000	
----------------------------------------------

  7000: 		0.0000			0.0000	
----------------------------------------------

  9000: 		0.0000			0.0000	
----------------------------------------------

 11000: 		0.0000			0.0000	
----------------------------------------------


						Search
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 				Linear				Binary
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 Avg Probes:	5439 				 14
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Last edited on
Assignment:

You are to compare two sorting algorithms and compare two searching algorithms by running the algorithms and collecting data on each. Your data for sorting and searching will be strings of 20 characters in length. You are to have your program run, compute and print all the results in one run, not multiple runs. (You are to run your program once for all data sets.) In order to test sort algorithm, we will need to run the sort algorithms on different size data sets.

First Part:
The two sorts to compare are the Bubble Sort and the Selection Sort. You are to test your sorts against different sets of strings. Each sort will sort six sets of data, one set has 1000 strings, then a set with 3000 strings, 5000, 7000, 9000 and 11000 strings. You will compare how well each sort did with the different data sizes and show results. I would like to see a plot of the results. A table format showing results will do. Use the ‘time’ function and the ‘difftime’ function to gather sort times or the ‘clock’ function shown in the handout. Show answers with at least 4 places to right of decimal point. (Note: you need only one array of 11000 using only part of it for the sort/search tasks.)

Second Part:
The two searches to use for comparisons are the Linear Search and the Binary Search. You will search for 4500 random strings in the array of 11000 strings array only and compute the average number of probes (not time) needed to find a match. The target string will be a randomly selected string from the 11000 string’s data set. You will select randomly 4500 strings for testing each search algorithm. Output the average number of probes needed for each search algorithm.

Third Part:
How do your two search algorithms compare with the theoretical values?


You are to generate random strings of 20 characters in each string for your string data sets. Below is code to build one (1) random string.
1
2
3
4
5
6
7
8
9
Hint:
  char  charset[52];    “a b c … A B C … Z”;
  string  randomstr;
  for ( i = 1; i <=20; i++ )
  {     randomndx = rand() % 56;   //  random index into array charset.
         randomstr = randomstr + charset[ randomndx ];  //concat a char to the string begin built
				// you are building a string one char at a time.
				// The code above builds only one string.
   }

To select a random string form the 11000. How? You will generate a random number 0 to 10999, an index into the 11000 string array, use the selected string to do a Search. The you will search for the random string using the Linear Search and for the Binary Search. Now generate a new random number as an index into the 11000 array and do the searches again. Do this for 4500 times.
You are saying time -= clock() which means time = time - clock(), but you want:

 
time = clock() - time;

You can replace the switch with:

 
out << std::setw(6) << start << ": ";

@dutch,

I've figured it out, the issue(besides the time-=clock), was within the binary function. I pulled the bubble function call out of the binary function and moved it into main, along with the select function call. Now it works like a charm.

Topic archived. No new replies allowed.