Sorting with selection, insertion, and bubble sort
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 22

Thread: Sorting with selection, insertion, and bubble sort

  1. #1
    Join Date
    Apr 2014
    Posts
    17

    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.

  2. #2
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  3. #3
    Join Date
    Apr 2014
    Posts
    17

    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);
    }

  4. #4
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  5. #5
    Join Date
    Apr 2014
    Posts
    17

    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.

  6. #6
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  7. #7
    Join Date
    Apr 2014
    Posts
    17

    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);
    }

  8. #8
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  9. #9
    Join Date
    Apr 2014
    Posts
    17

    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 :
    Code:
    double	rank,
    		pop;
    to:
    Code:
    int	rank,
    		pop;
    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.

  10. #10
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  11. #11
    Join Date
    Apr 2014
    Posts
    17

    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.

  12. #12
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  13. #13
    Join Date
    Apr 2014
    Posts
    17

    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;

  14. #14
    Join Date
    Apr 2014
    Posts
    17

    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

  15. #15
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,378

    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. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center