C++

Forum

 
Don't understand Bubble Sort in my code C++

loanrefi (4)
Using vectors
I have written a piece of code to display;
1. Total numbers of words inside a text file
2. Total Distinct words used in the text file
3. The X most used words and their frequencies <--I'm stuck here
4. other steps to follow which I will work on after I understand bubble sort...

I need to use bubble sort but I don't quite understand how to apply in my code.

My code compiles and runs with the following output;

Alphabetical order...

100 appears 1 times.
1984 appears 1 times.
2 appears 1 times.
a appears 8 times.
all appears 1 times.
be appears 4 times.
come appears 1 times.
two appears 1 times.
used appears 3 times.
user appears 3 times.
very appears 1 times.
when appears 1 times.
will appears 7 times.
with appears 2 times.
word appears 3 times.
words appears 6 times.
write appears 1 times.
written appears 1 times.
x appears 6 times.
y appears 2 times.

So far it does what I want but now I need to sort the "(Number) times" so that by applying bubble sort I can list (Number) times in ascending order e.g. "word" appears 1 times, "word" appears 2 times, "word" appears 3 times etc.. instead of alphabetical order. Later I will extract words that appear X times etc.

I don't understand bubble sort. I have no experience in C++, I have spent days messing with pieces of code to get the results I want with no luck.

I guess I'm trying to bubble sort wrong information from my code.

Can someone please offer guidance as to what part of my code I should be using for bubble sort code and let me know if I'm close or way off to getting program to do what I want it to do as explained above?

As of now my code does Nothing with bubble sort code I added. I appreciate all your help.

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
 
I don't think I need all these libraries but I'll remove them later.
#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cctype>
#include <functional>
#include <fstream>
#include <string>
#include <vector>
#include <locale>

using namespace std;

int main()

{
	int distinct, amount = 1;
	int nFrequencies;
	int totalWords;
	int difW;
	int numX;
	string word;
	string removeUnwanted;
	string line;
	string temp;
	string formattedString;
	vector<string> words;

	ifstream myfile ("C:/Users/PathToMyFile/Documents/Test.txt");
	cout << "Opening File... " << endl;
	if(!myfile)
    {
        cout << "Error: Could not open file" << endl;
        return 1;
    }
	if(myfile.is_open())
	{
		while (myfile.good())
		{
			getline(myfile,line);
			istringstream ss(line);
			while(ss >> temp)
			{
			//Function to remove unwanted digits & characters
			for(int a=temp.size() -1; a >= 0; a--)
				{
				temp.at(a) = tolower (temp.at(a));
					
				if((temp.at(a) < 65 || temp.at(a) > 90) && (temp.at(a) < 97 || temp.at(a) > 122) && (temp.at(a) < 48 || temp.at(a) > 57))
					{
					//Remove character at pos a;
					temp.erase(a,1);
					}
					}
					if(temp.size() > 0)
					{
					words.push_back(temp);
					}
			}
		}
		myfile.close();
		distinct = words.size();
		sort(words.begin(), words.end());
		
		vector < string > distinctWords;
		vector < int > frequencies;

		for (int i = 0; i < distinct-1; ++i)
		{
			//if two words right next to each other are the same
			if (words[i] == words[i+1])
			{
				//increase the frequency of that word
				amount++;
			}
			else //two words right next to each other are not the same
			{
				distinctWords.push_back(words[i]);
				frequencies.push_back(amount);
				//Count number of distinct words in the sorted order
				//This Tests&Prints code above -->>
				cout << words[i] << " appears " << amount << " times." << endl;
				amount = 1;
			}
		}
		
		//Print the results
		cout << "The Total Number of Words Is: " << words.size() << "\n";
		cout << "There Are: " << distinctWords.size() << " Distinct Words" << endl;
		
		//bubble sort
		
		//go n times, each time another item will move to
		//the sorted part of the collection
		
		for(int i = 0;i < frequencies.size();i++)
		{
			for(int j = 0;j < frequencies.size() - 1;j++)
			{
				//if the left is greater than the right
				if(frequencies[j] > frequencies[j + 1])
				{
				//swap
				int temp = frequencies[j];
				frequencies[j] = frequencies[i + 1];
				frequencies[j + 1] = temp;
				}
				//else- do nothing, move on the the next pair
			}
			
		}
		//find x most frequent words
		
		{
		int xMostFreqW;
		cout<<"Enter a number to find the x most frequent words: ";
		cin >> xMostFreqW ;
		}

		//find the x most freq words that are y letters or more
		{
		
		}
		//find words that show up exactly x times
		{
		
		}
		
		return 0;
	}
}
Last edited on
Smac89 (1727)
write a comp function for sort.

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
 
#include <bits/stdc++.h>
#define all(G) G.begin(), G.end()

using namespace std;

bool compare( string rhs, string lhs) {
	int a, b;
	sscanf( string(rhs.rbegin(), rhs.rend()).c_str(), "%*s%d", &a );
	sscanf( string(lhs.rbegin(), lhs.rend()).c_str(), "%*s%d", &b );
	return ( a > b );
}

int main() {
	deque <string> words = { 
		"100 appears 1 times.", "1984 appears 1 times.",
		"2 appears 1 times.", "a appears 8 times.",
		"all appears 1 times.", "be appears 4 times.",
		"come appears 1 times.", "two appears 1 times.",
		"used appears 3 times.", "user appears 3 times.",
		"very appears 1 times.", "when appears 1 times.",
		"will appears 7 times.", "with appears 2 times.",
		"word appears 3 times.", "words appears 6 times.",
		"write appears 1 times.", "written appears 1 times.",
		"x appears 6 times.", "y appears 2 times"
	};
	
	sort( all(words), compare );
	for ( auto F: words )
		cout << F << endl;
}


a appears 8 times.
will appears 7 times.
x appears 6 times.
words appears 6 times.
be appears 4 times.
used appears 3 times.
user appears 3 times.
word appears 3 times.
y appears 2 times
with appears 2 times.
very appears 1 times.
written appears 1 times.
write appears 1 times.
when appears 1 times.
100 appears 1 times.
two appears 1 times.
come appears 1 times.
all appears 1 times.
2 appears 1 times.
1984 appears 1 times.


Another way to do this is to use a priority queue to store the words, then in the end just dequeue each element and print it:
http://www.cplusplus.com/reference/queue/priority_queue/
http://en.wikipedia.org/wiki/Priority_queue
Last edited on
loanrefi (4)
Alright, I looked at your code suggestion this is what I put together to do bubble sort...

I'm told that at this point the words should be sorted. This is how I understand this to be working:

Example
Words -->
[That][That][That][The][The]
0 1 2 3 4

Distinct Words -->
[That][The]
0 1

Frequencies -->
After Bubble Sort
[3] [2]
0 1

Now I want the user to enter a number to display the X Most frequent words.

At this point I guess I need to do a function to print out the X Most frequent words. Am I correct?

The example you gave me is basically what bubble sort does. Now what I want to do is select the number and print the corresponding words. So if "Will" appears 7 times, I want to print to the screen "Will" 7 times.

I appreciate your help.

Here is my latest code;

#include "stdafx.h"
#include <algorithm>
#include <iostream>
#include <sstream>
#include <functional>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

int main()

{
int distinct, amount = 1;
int nFrequencies;
int totalWords;
int difW;
int numX;
string word;
string removeUnwanted;
string line;
string temp;
string formattedString;
vector<string> words;

ifstream myfile ("C:/Users/MyUsername/Documents/Test.txt");


cout << "Opening File... " << endl;
if(!myfile)
{
cout << "Error: Could not open file" << endl;
return 1;
}
if(myfile.is_open())
{
while (myfile.good())
{
getline(myfile,line);

//if(myfile.good())
//{
istringstream ss(line);
while(ss >> temp)
{
//Function to remove unwanted digits & characters
for(int a=temp.size() -1; a >= 0; a--)
{
temp.at(a) = tolower (temp.at(a));

if((temp.at(a) < 65 || temp.at(a) > 90) && (temp.at(a) < 97 || temp.at(a) > 122) && (temp.at(a) < 48 || temp.at(a) > 57))
{
//Remove character at pos a;
temp.erase(a,1);
}
}
if(temp.size() > 0)
{
words.push_back(temp);
}
}
//}
}
myfile.close();
distinct = words.size();
sort(words.begin(), words.end());

vector < string > distinctWords;
vector < int > frequencies;

for (int i = 0; i < words.size() - 1; i++)
{
//if two words right next to each other are the same
if (words[i] == words[i+1])
{
//increase the frequency of that word
amount++;

//if we are at the very last word in the words
if(i == words.size() - 2)
{
//add the word and the frequency
distinctWords.push_back(words[i]);
frequencies.push_back(amount);
}
}
else //two words right next to each other are not the same
{
distinctWords.push_back(words[i]);
frequencies.push_back(amount);
//Count number of distinct words in the sorted order
//This Tests&Prints code above -->>
cout << words[i] << " appears " << amount << " times." << endl;

if(i == words.size() - 2)
{
//add the word and the frequency
distinctWords.push_back(words[i + 1]);
frequencies.push_back(1);
}
amount = 1;
}
}

//Print the results
cout << "The Total Number of Words Is: " << words.size() << "\n";
cout << "There Are: " << distinctWords.size() << " Distinct Words" << endl;

//bubble sort

for(int j=0; j < frequencies.size()-1; j++)
{
for(int i=0; i < frequencies.size()-1; i++)
{
if(frequencies[i] > frequencies[i + 1])
{

//swap left & right
//1.copy left val
int temp = frequencies[i];
string tempstring = distinctWords[i];
//2. Store the right inside left
frequencies[i] = frequencies[i+1];
distinctWords[i] = distinctWords[i+1];
//3. Store temp into right
frequencies[i+1] = temp;
distinctWords[i+1] = tempstring;
}
}

}

//find x most frequent words

int xMostFreqW;
cout<<"Enter a number to find the x most frequent words: ";
cin >> xMostFreqW ;

// Do something here to look up X Most Frequent workds, but what???? How???

//cout<< "The " << xMostFreqW << "most frequent words are: " << frequencies(xMostFreqW = frequencies[i]) << endl;

//find the x most freq words that are y letters or more
{

}
//find words that show up exactly x times
{

}

return 0;
}
}






loanrefi (4)
Success!

After adding the "correct" bubble sort code I was able to finish the rest with no problem.

I corrected this piece of code too "if(frequencies[i] > frequencies[i + 1])"
To "if(frequencies[i] < frequencies[i + 1])"

Here is bubble sort code:
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
 
 

//bubble sort
		for(int j=0; j < frequencies.size()-1; j++)
		{
			for(int i=0; i < frequencies.size()-1; i++)
			{
				if(frequencies[i] < frequencies[i + 1])
				{

					//swap left & right
					//1.copy left val
					int temp = frequencies[i];
					string tempstring = distinctWords[i];
					
					//2. Store the right inside left
					frequencies[i] = frequencies[i+1];
					distinctWords[i] = distinctWords[i+1];
					
					//3. Store temp into right
					frequencies[i+1] = temp;
					distinctWords[i+1] = tempstring;
				}
			}
			
		}
Last edited on
Topic archived. No new replies allowed.