-
May 4th, 2014, 06:09 PM
#1
Sorting with selection, insertion, and bubble sort
I need some help with this program using the selection, insertion, and bubble sorts. The program needs to be able to do the following:
1. Create an array of 1000 population records when the array object is instantiated. Call it unSorted.
2. Open the file called “Population.csv” (on the portal) and invoke a function that loads the population data into the array.
3. Create a second array of 1000 elements that will be used to sort the data using the different algorithms. Name is sortedArray.
4. Write a function that will copy unSorted into sortedArray and execute that function.
5. Using a function, display the unsorted array.
6. Invoke the insertionSort () function that will sort the sortedArray using the insertion sort algorithm. Sort the population data on the rank field in ascending order. Alternatively, you can sort in descending order on population.
7. Using the display function, display sortedArray.
8. Display the number of iterations it took to do the sort using this algorithm.
9. Repeat steps 4-8 for the selection and bubble sort algorithms.
Here is my code so far:
Code:
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
void loadArray (int unSorted[], int s);
void displayArray (const int num [], int size);
void selectionSort(int num [], int size);
void insertionSort(int num [], int size);
void bubbleSort(int num [], int size);
int main ()
{
const int size = 1000;
int unSorted[size];
int sortedArray[size];
ifstream inFile("Population.csv");
if (!inFile)
{
cout << "File was not found" << endl;
for (int i = 0; i < 1000; i++)
{
inFile >> unSorted[i];
}
inFile.close();
cout << "Selection Sort: ";
selectionSort(sortedArray, size) << endl;
}
void int loadElements (int unSorted[], int s)
{
for( int i = 0, i < s; i++)
}
void int displayArray (const in num [], int size)
{
for int i = 0; i < size; i++)
cout << num[i];
}
void selectionSort(int num [], int size)
{
int startscan, minindex, minvalue;
for (startscan = 0; startscan < (size - 1); startscan++)
{
minindex = startscan;
minvalue = num[startscan];
for(int index = startscan + 1; index < size; index++)
{
if (num[index] < minvalue)
{
minvalue = num[index];
minindex = index;
}
}
num[minindex] = num[startscan];
num[startscan] = minvalue;
displayArray (num, size);
cout << endl;
}
}
void insertionSort(int num [], int size)
{
for (int i = 1; i < size; i++)
{
int j;
int current = num[i];
for (j = i - 1; j >= 0 && num[j] > current; j--)
{
num[j+1]=num[j];
}
num[j+1]=current;
displayArray (num, size);
cout << endl;
}
}
void bubbleSort(int num [], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 1); count++)
{
if (num[count] > num [count + 1])
{
temp = num[count];
num[count] = num[count +1];
num[count +1] = temp;
swap = true;
}
}
displayArray (num, size);
cout << endl;
} while (swap);
}
Here is a few lines from the Population.csv file contents:
Code:
Alabama,Baldwin County,140415,389
Alabama,Blount County,51024,908
Alabama,Calhoun County,112249,477
Alabama,Colbert County,54984,858
Alabama,Cullman County,77483,653
Alabama,Dale County,49129,927
Alabama,Dallas County,46365,974
Alabama,DeKalb County,64452,753
I'm not sure how to load the data from the file into the array properly, I attempted this. I also don't know how to copy the unSorted into sortedArray.
-
May 5th, 2014, 06:26 AM
#2
Re: Sorting with selection, insertion, and bubble sort
Firstly, each line of the data file contains 4 elements - two strings and two numbers. So it isn't possible to just read the data from the file into an int array as you attempted. I suggest that you define a struct that represents this data and then have an array of this type as opposed to an array of int. You then need to read the data from the file into this array. I suggest reading a whole line at a time into a string (getline http://www.cplusplus.com/reference/s...tring/getline/) and then parsing this string into its various parts and filling the array. Once the array has been filled then it can be copied and sorted etc. You may want to consider having this as a class with class functions rather than as a struct.
As this is an exercise I won't provide the code (see http://forums.codeguru.com/showthrea...ork-assignment) but if you re-post your revised code we'll provide further guidance.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 8th, 2014, 04:16 PM
#3
Re: Sorting with selection, insertion, and bubble sort
Thank you for your help. This assignment is past due, but I am just trying to understand it for future assignments. I updated my code with your advice, but am unsure how to do the array part.
Here is what I have so far:
Code:
#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
struct Population
{
double rank,
pop;
string state,
county;
Population(){rank = 0; pop = 0;
state = "Unassigned"; county = "Unassigned";}
};
void loadArray (int unSorted[], int s);
void displayArray (const int num [], int size);
void selectionSort(int num [], int size);
void insertionSort(int num [], int size);
void bubbleSort(int num [], int size);
int main ()
{
Population population;
const int size = 1000;
population unSorted[size];
population sortedArray[size];
ifstream inFile("Population.csv");
if (!inFile)
{
cout << "File was not found" << endl;
exit (99);
}
getline(inFile, population.state);
getline(inFile, population.county);
inFile >> population.pop;
inFile.ignore();
inFile >> population.rank;
inFile.ignore();
for (int i = 0; i < 1000; i++)
{
inFile >> unSorted[i];
}
inFile.close();
cout << "Selection Sort: ";
selectionSort(sortedArray, size) << endl;
cout << "Inserition Sort: ";
insertionSort(sortedArray, size) << endl;
cout << "Bubble Sort: ";
bubbleSort(sortedArray, size) << endl;
}
void int loadElements (int unSorted[], int s)
{
for( int i = 0, i < s; i++)
}
void int displayArray (const in num [], int size)
{
for int i = 0; i < size; i++)
cout << num[i];
}
void selectionSort(int num [], int size)
{
int startscan, minindex, minvalue;
for (startscan = 0; startscan < (size - 1); startscan++)
{
minindex = startscan;
minvalue = num[startscan];
for(int index = startscan + 1; index < size; index++)
{
if (num[index] < minvalue)
{
minvalue = num[index];
minindex = index;
}
}
num[minindex] = num[startscan];
num[startscan] = minvalue;
displayArray (num, size);
cout << endl;
}
}
void insertionSort(int num [], int size)
{
for (int i = 1; i < size; i++)
{
int j;
int current = num[i];
for (j = i - 1; j >= 0 && num[j] > current; j--)
{
num[j+1]=num[j];
}
num[j+1]=current;
displayArray (num, size);
cout << endl;
}
}
void bubbleSort(int num [], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 1); count++)
{
if (num[count] > num [count + 1])
{
temp = num[count];
num[count] = num[count +1];
num[count +1] = temp;
swap = true;
}
}
displayArray (num, size);
cout << endl;
} while (swap);
}
-
May 8th, 2014, 05:22 PM
#4
Re: Sorting with selection, insertion, and bubble sort
getline() reads a whole line of data from the file - so getline(inFile, population.state) will read the whole of the first line of the file into population.state which is not really what you want. The arrays (unSorted, sortedArray) should be of type Population and not population (which is a variable).
Your functions will now need to take as a parameter an array of type Population instead of an array of type int. Also the functions cannot have a return type of void int. They must just return one type.
As this assignment is past due, the code below will read the data file into the array popdata and then display it. It does the first 5 steps from your post #1.
Code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const string filename = "population.csv";
const int maxsize = 1000;
struct Population
{
double rank,
pop;
string state,
county;
Population(): rank(0), pop(0), state("Unassigned"), county("Unassigned") {}
};
int loadElements(ifstream& ifs, Population data[]);
void displayArray(Population data[], int elems);
void parsecsv(const string& line, vector<string>& values);
istream& operator >>(istream& is, Population& pop);
void copyPop(Population frm[], Population to[], int size);
int main()
{
ifstream ifs(filename.c_str());
if (!ifs.is_open()) {
cout << "Could not open input file " << filename << endl;
return 1;
}
Population unSorted[maxsize],
sortedArray[maxsize];
int popsize = loadElements(ifs, unSorted);
copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);
return 0;
}
int loadElements(ifstream& ifs, Population data[])
{
int popind;
for (popind = 0; (ifs >> data[popind]) && (popind < maxsize); ++popind);
return popind;
}
void displayArray(Population data[], int elems)
{
for (int i = 0; i < elems; ++i)
cout << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;
}
void copyPop(Population frm[], Population to[], int size)
{
for (int i = 0; i < size; ++i)
to[i] = frm[i];
}
void parsecsv(const string& line, vector<string>& values)
{
const char csvdelim = ',';
const char ignore = ' ';
values.clear();
for (size_t st = 0, last = 0, pos = line.find_first_not_of(ignore); (last += (pos = line.find(csvdelim, st)) == string::npos) < 2; st = pos + 1, last += (pos == string::npos))
values.push_back(line.substr((st = line.find_first_not_of(ignore, st)), line.find_last_not_of(ignore, pos - 1) - st + 1));
}
istream& operator >>(istream& is, Population& pop)
{
string line;
vector<string> values;
if (getline(is, line)) {
parsecsv(line, values);
pop.state = values[0];
pop.county = values[1];
pop.pop = atoi(values[2].c_str());
pop.rank = atoi(values[3].c_str());
}
return is;
}
You'll need to change your various sort functions to work with the Population struct instead of an int. Try it and if you get problems post your revised code for further guidance.
Last edited by 2kaud; May 8th, 2014 at 06:12 PM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 8th, 2014, 06:21 PM
#5
Re: Sorting with selection, insertion, and bubble sort
Thank you for your help. I haven't used vectors very much, is there another way of doing that part?
Here is my revised code:
(I'm still having issues, it says that there is a mismatch in formal parameter list on this line: selectionSort(sortedArray, popsize) << endl; )
Code:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
const string filename = "population.csv";
const int maxsize = 1000;
struct Population
{
double rank,
pop;
string state,
county;
Population(): rank(0), pop(0), state("Unassigned"), county("Unassigned") {}
};
int loadElements(ifstream& ifs, Population data[]);
void displayArray(Population data[], int elems);
void parsecsv(const string& line, vector<string>& values);
istream& operator >>(istream& is, Population& pop);
void copyPop(Population frm[], Population to[], int size);
void selectionSort(Population data[], int size);
void insertionSort(Population data[], int size);
void bubbleSort(Population data[], int size);
int main()
{
ifstream ifs(filename.c_str());
if (!ifs.is_open()) {
cout << "Could not open input file " << filename << endl;
return 1;
}
Population unSorted[maxsize],
sortedArray[maxsize];
int popsize = loadElements(ifs, unSorted);
copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);
cout << "Selection Sort: ";
selectionSort(sortedArray, popsize) << endl;
cout << "Inserition Sort: ";
insertionSort(sortedArray, popsize) << endl;
cout << "Bubble Sort: ";
bubbleSort(sortedArray, popsize) << endl;
return 0;
}
int loadElements(ifstream& ifs, Population data[])
{
int popind;
for (popind = 0; (ifs >> data[popind]) && (popind < maxsize); ++popind);
return popind;
}
void displayArray(Population data[], int elems)
{
for (int i = 0; i < elems; ++i)
cout << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;
}
void copyPop(Population frm[], Population to[], int size)
{
for (int i = 0; i < size; ++i)
to[i] = frm[i];
}
void parsecsv(const string& line, vector<string>& values)
{
const char csvdelim = ',';
const char ignore = ' ';
values.clear();
for (size_t st = 0, last = 0, pos = line.find_first_not_of(ignore); (last += (pos = line.find(csvdelim, st)) == string::npos) < 2; st = pos + 1, last += (pos == string::npos))
values.push_back(line.substr((st = line.find_first_not_of(ignore, st)), line.find_last_not_of(ignore, pos - 1) - st + 1));
}
istream& operator >>(istream& is, Population& pop)
{
string line;
vector<string> values;
if (getline(is, line)) {
parsecsv(line, values);
pop.state = values[0];
pop.county = values[1];
pop.pop = atoi(values[2].c_str());
pop.rank = atoi(values[3].c_str());
}
return is;
}
void selectionSort(Population data[], int size)
{
int startscan, minindex, minvalue;
for (startscan = 0; startscan < (size - 1); startscan++)
{
minindex = startscan;
minvalue = data[startscan];
for(int index = startscan + 1; index < size; index++)
{
if (data[index] < minvalue)
{
minvalue = data[index];
minindex = index;
}
}
data[minindex] = data[startscan];
datastartscan] = minvalue;
displayArray (data, size);
cout << endl;
}
}
void insertionSort(Population data[], int size)
{
for (int i = 1; i < size; i++)
{
int j;
int current = data[i];
for (j = i - 1; j >= 0 && data[j] > current; j--)
{
data[j+1]=data[j];
}
data[j+1]=current;
displayArray (data, size);
cout << endl;
}
}
void bubbleSort(Population data[], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 1); count++)
{
if (data[count] > data [count + 1])
{
temp = data[count];
data[count] = data[count +1];
data[count +1] = temp;
swap = true;
}
}
displayArray (data, size);
cout << endl;
} while (swap);
}
Last edited by elephant7; May 8th, 2014 at 11:04 PM.
-
May 9th, 2014, 06:32 AM
#6
Re: Sorting with selection, insertion, and bubble sort
Code:
selectionSort(sortedArray, popsize) << endl;
???? This isn't valid. This will need to be done in a couple of steps
Code:
selectionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
and similarly for the other sorts. Before each sort you also might want to copy the unsorted array to the sorted array so that each sort starts with the same unsorted data for comparison purposes.
I haven't used vectors very much, is there another way of doing that part?
This is revised code that uses a string array instead of a vector string.
Code:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const string filename = "population.csv";
const int maxsize = 1000;
struct Population
{
double rank,
pop;
string state,
county;
Population(): rank(0), pop(0), state("Unassigned"), county("Unassigned") {}
};
int loadElements(ifstream& ifs, Population data[]);
void displayArray(Population data[], int elems);
int parsecsv(const string& line, string values[], int max);
istream& operator >>(istream& is, Population& pop);
void copyPop(Population frm[], Population to[], int size);
int main()
{
ifstream ifs(filename.c_str());
if (!ifs.is_open()) {
cout << "Could not open input file " << filename << endl;
return 1;
}
Population unSorted[maxsize],
sortedArray[maxsize];
int popsize = loadElements(ifs, unSorted);
copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);
return 0;
}
int loadElements(ifstream& ifs, Population data[])
{
int popind;
for (popind = 0; (ifs >> data[popind]) && (popind < maxsize); ++popind);
return popind;
}
void displayArray(Population data[], int elems)
{
for (int i = 0; i < elems; ++i)
cout << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;
}
void copyPop(Population frm[], Population to[], int size)
{
for (int i = 0; i < size; ++i)
to[i] = frm[i];
}
int parsecsv(const string& line, string values[], int max)
{
const char csvdelim = ',';
const char ignore = ' ';
int ind = 0;
for (size_t st = 0, last = 0, pos = line.find_first_not_of(ignore); (ind < max) && (last += (pos = line.find(csvdelim, st)) == string::npos) < 2; st = pos + 1, last += (pos == string::npos), ind++)
values[ind] = line.substr((st = line.find_first_not_of(ignore, st)), line.find_last_not_of(ignore, pos - 1) - st + 1);
return ind;
}
istream& operator >>(istream& is, Population& pop)
{
const int maxvalues = 4;
string line;
string values[maxvalues];
if (getline(is, line) && (parsecsv(line, values, maxvalues) == maxvalues)) {
pop.state = values[0];
pop.county = values[1];
pop.pop = atoi(values[2].c_str());
pop.rank = atoi(values[3].c_str());
}
return is;
}
I would suggest you have a close study of parsecsv() and see if you can work out how it does the individual element extraction.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 10th, 2014, 02:38 PM
#7
Re: Sorting with selection, insertion, and bubble sort
The code still isn't working. It now says: "error C2440: '=' : cannot convert from 'Population' to 'int' " on this line: "minvalue = data[startscan];"
Code:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const string filename = "population.csv";
const int maxsize = 1000;
struct Population
{
double rank,
pop;
string state,
county;
Population(): rank(0), pop(0), state("Unassigned"), county("Unassigned") {}
};
int loadElements(ifstream& ifs, Population data[]);
void displayArray(Population data[], int elems);
int parsecsv(const string& line, string values[], int max);
istream& operator >>(istream& is, Population& pop);
void copyPop(Population frm[], Population to[], int size);
void selectionSort(Population data[], int size);
void insertionSort(Population data[], int size);
void bubbleSort(Population data[], int size);
int main()
{
ifstream ifs(filename.c_str());
if (!ifs.is_open()) {
cout << "Could not open input file " << filename << endl;
return 1;
}
Population unSorted[maxsize],
sortedArray[maxsize];
int popsize = loadElements(ifs, unSorted);
copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);
cout << "Selection Sort: ";
selectionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
cout << "Inserition Sort: ";
insertionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
cout << "Bubble Sort: ";
bubbleSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
return 0;
}
int loadElements(ifstream& ifs, Population data[])
{
int popind;
for (popind = 0; (ifs >> data[popind]) && (popind < maxsize); ++popind);
return popind;
}
void displayArray(Population data[], int elems)
{
for (int i = 0; i < elems; ++i)
cout << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;
}
void copyPop(Population frm[], Population to[], int size)
{
for (int i = 0; i < size; ++i)
to[i] = frm[i];
}
int parsecsv(const string& line, string values[], int max)
{
const char csvdelim = ',';
const char ignore = ' ';
int ind = 0;
for (size_t st = 0, last = 0, pos = line.find_first_not_of(ignore); (ind < max) && (last += (pos = line.find(csvdelim, st)) == string::npos) < 2; st = pos + 1, last += (pos == string::npos), ind++)
values[ind] = line.substr((st = line.find_first_not_of(ignore, st)), line.find_last_not_of(ignore, pos - 1) - st + 1);
return ind;
}
istream& operator >>(istream& is, Population& pop)
{
const int maxvalues = 4;
string line;
string values[maxvalues];
if (getline(is, line) && (parsecsv(line, values, maxvalues) == maxvalues)) {
pop.state = values[0];
pop.county = values[1];
pop.pop = atoi(values[2].c_str());
pop.rank = atoi(values[3].c_str());
}
return is;
}
void selectionSort(Population data[], int size)
{
int startscan, minindex, minvalue;
for (startscan = 0; startscan < (size - 1); startscan++)
{
minindex = startscan;
minvalue = data[startscan];
for(int index = startscan + 1; index < size; index++)
{
if (data[index] < minvalue)
{
minvalue = data[index];
minindex = index;
}
}
data[minindex] = data[startscan];
datastartscan] = minvalue;
displayArray (data, size);
cout << endl;
}
}
void insertionSort(Population data[], int size)
{
for (int i = 1; i < size; i++)
{
int j;
int current = data[i];
for (j = i - 1; j >= 0 && data[j] > current; j--)
{
data[j+1]=data[j];
}
data[j+1]=current;
displayArray (data, size);
cout << endl;
}
}
void bubbleSort(Population data[], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 1); count++)
{
if (data[count] > data [count + 1])
{
temp = data[count];
data[count] = data[count +1];
data[count +1] = temp;
swap = true;
}
}
displayArray (data, size);
cout << endl;
} while (swap);
}
-
May 10th, 2014, 02:49 PM
#8
Re: Sorting with selection, insertion, and bubble sort
Code:
minvalue = data[startscan];
The error is correct. Population is of type struct. So to get the population number you would use
Code:
minvalue = data[startscan].pop;
and similarly for other statements that need to refer to individual elements of the struct.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 10th, 2014, 03:54 PM
#9
Re: Sorting with selection, insertion, and bubble sort
I tried that and now it says : "warning C4244: '=' : conversion from 'double' to 'int', possible loss of data"
So I changed : to: Now it runs, but just an infinite loop.. here is my code:
Code:
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
const string filename = "population.csv";
const int maxsize = 1000;
struct Population
{
int rank,
pop;
string state,
county;
Population(): rank(0), pop(0), state("Unassigned"), county("Unassigned") {}
};
int loadElements(ifstream& ifs, Population data[]);
void displayArray(Population data[], int elems);
int parsecsv(const string& line, string values[], int max);
istream& operator >>(istream& is, Population& pop);
void copyPop(Population frm[], Population to[], int size);
void selectionSort(Population data[], int size);
void insertionSort(Population data[], int size);
void bubbleSort(Population data[], int size);
int main()
{
ifstream ifs(filename.c_str());
if (!ifs.is_open()) {
cout << "Could not open input file " << filename << endl;
return 1;
}
Population unSorted[maxsize],
sortedArray[maxsize];
int popsize = loadElements(ifs, unSorted);
copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);
cout << "Selection Sort: ";
selectionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
cout << "Inserition Sort: ";
insertionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
cout << "Bubble Sort: ";
bubbleSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;
return 0;
}
int loadElements(ifstream& ifs, Population data[])
{
int popind;
for (popind = 0; (ifs >> data[popind]) && (popind < maxsize); ++popind);
return popind;
}
void displayArray(Population data[], int elems)
{
for (int i = 0; i < elems; ++i)
cout << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;
}
void copyPop(Population frm[], Population to[], int size)
{
for (int i = 0; i < size; ++i)
to[i] = frm[i];
}
int parsecsv(const string& line, string values[], int max)
{
const char csvdelim = ',';
const char ignore = ' ';
int ind = 0;
for (size_t st = 0, last = 0, pos = line.find_first_not_of(ignore); (ind < max) && (last += (pos = line.find(csvdelim, st)) == string::npos) < 2; st = pos + 1, last += (pos == string::npos), ind++)
values[ind] = line.substr((st = line.find_first_not_of(ignore, st)), line.find_last_not_of(ignore, pos - 1) - st + 1);
return ind;
}
istream& operator >>(istream& is, Population& pop)
{
const int maxvalues = 4;
string line;
string values[maxvalues];
if (getline(is, line) && (parsecsv(line, values, maxvalues) == maxvalues)) {
pop.state = values[0];
pop.county = values[1];
pop.pop = atoi(values[2].c_str());
pop.rank = atoi(values[3].c_str());
}
return is;
}
void selectionSort(Population data[], int size)
{
int startscan, minindex, minvalue;
for (startscan = 0; startscan < (size - 1); startscan++)
{
minindex = startscan;
minvalue = data[startscan].pop;
for(int index = startscan + 1; index < size; index++)
{
if (data[index].pop < minvalue)
{
minvalue = data[index].pop;
minindex = index;
}
}
data[minindex] = data[startscan];
data[startscan].pop = minvalue;
displayArray (data, size);
cout << endl;
}
}
void insertionSort(Population data[], int size)
{
for (int i = 1; i < size; i++)
{
int j;
int current = data[i].pop;
for (j = i - 1; j >= 0 && data[j].pop > current; j--)
{
data[j+1] = data[j];
}
data[j+1].pop = current;
displayArray (data, size);
cout << endl;
}
}
void bubbleSort(Population data[], int size)
{
bool swap;
int temp;
do
{
swap = false;
for (int count = 0; count < (size - 1); count++)
{
if (data[count].pop > data[count + 1].pop)
{
temp = data[count].pop;
data[count] = data[count +1];
data[count +1].pop = temp;
swap = true;
}
}
displayArray (data, size);
cout << endl;
} while (swap);
}
Last edited by elephant7; May 10th, 2014 at 04:01 PM.
-
May 10th, 2014, 04:11 PM
#10
Re: Sorting with selection, insertion, and bubble sort
If you debug the program using the debugger, you'll find the logic error in the sort code. Hint. Take particular note of
Code:
data[minindex] = data[startscan];
data[startscan].pop = minvalue;
What are you trying to achieve here - and what does this code actually do? How would you swap two elements in an array?
Try to find the problem before I provide the correct couple of lines.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 10th, 2014, 05:03 PM
#11
Re: Sorting with selection, insertion, and bubble sort
I can't figure out what the problem is, I tried using the debugger and didn't have any luck.
-
May 11th, 2014, 04:59 AM
#12
Re: Sorting with selection, insertion, and bubble sort
I tried using the debugger and didn't have any luck.
Using the debugger you should have at least found what was not happening that should be happening. If you used it to trace through the execution of the program then you should at least have found the problem if not the solution.
The issue is that at this point in the code from post #10 you should swap the two elements - but you are overwriting the data at minindex with the data at startscan. Hence the data that was at minindex is now lost. You need to preserve the data that was at minindex before overwriting it with the data from startscan. Given this code
Code:
int a, b;
a = 3;
b = 4;
without prior knowledge of the values of a and b, how would you swap the values so that a contains the value of b and b contains the value of a?
Last edited by 2kaud; May 11th, 2014 at 05:01 AM.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
May 11th, 2014, 11:20 AM
#13
Re: Sorting with selection, insertion, and bubble sort
Code:
a=a+b;
b=a-b;
a=a-b;
or
Code:
temp = a;
a = b;
b = temp;
-
May 11th, 2014, 11:23 AM
#14
Re: Sorting with selection, insertion, and bubble sort
So I tried this:
Code:
minvalue = data[startscan].pop;
data[startscan] = data[minindex];
data[minindex].pop = minvalue;
and it's still not working
-
May 11th, 2014, 11:40 AM
#15
Re: Sorting with selection, insertion, and bubble sort
You're close but not quite. You're trying to swap just the pop value rather than the whole struct. Replace
Code:
data[minindex] = data[startscan];
data[startscan].pop = minvalue;
with
Code:
Population temp = data[minindex];
data[minindex] = data[startscan];
data[startscan] = temp;
which swaps the minindex value with the startscan value. This swaps the whole stuct referred by minindex and startscan rather than just the pop element part of the struct.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|