Sorting with selection, insertion, and bubble sort

Show 50 post(s) from this thread on one page
Page 2 of 2 First 12
• May 11th, 2014, 11:45 AM
2kaud
Re: Sorting with selection, insertion, and bubble sort
Code:

```a=a+b; b=a-b; a=a-b;```
yes when dealing with numbers but can't be used for non-numbers such as strings. Also if the number is of a floating point type then rounding errors may happen which could mean that the new a and b values aren't exactly the same as the originals.

or
Code:

```temp = a; a = b; b = temp;```
This is the standard way of swapping two values. There's actually a template to this in the STL. See http://www.cplusplus.com/reference/algorithm/swap/
• May 11th, 2014, 11:57 AM
elephant7
Re: Sorting with selection, insertion, and bubble sort
Okay thank you, but it is still looping for some reason:

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;                         }                 }                 Population temp = data[minindex];                 data[minindex] = data[startscan];                 data[startscan] = temp;                 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); }```
• May 11th, 2014, 12:16 PM
2kaud
Re: Sorting with selection, insertion, and bubble sort
Quote:

but it is still looping for some reason:
In selectionSort? Don't forget you are displaying the array everytime around the startscan loop.
Code:

```displayArray (data, size); cout << endl;```
are you sure you want to do this.

Your other sort routines have the same problem re swapping/setting values as selectionSort had.

This is a working version just using selection sort
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); 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: \n";         selectionSort(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;                         }                 }                 Population temp = data[minindex];                 data[minindex] = data[startscan];                 data[startscan] = temp;         } }```
you should be able to get the other sort routines to work properly now based upon how things are done with seleection sort.
• May 11th, 2014, 12:34 PM
elephant7
Re: Sorting with selection, insertion, and bubble sort
The selection and bubble sorts are working with this code below, but I couldn't figure out how to change the insertion sort to work properly. I tried making int current to Population current, but it didn't work.
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);         cout << "Selection Sort: ";         selectionSort(sortedArray, popsize);         displayArray(sortedArray, popsize);         cout << endl << endl << endl;         cout << "Insertion 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;                         }                 }                 Population temp = data[minindex];                 data[minindex] = data[startscan];                 data[startscan] = temp;         } } 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;                 } } void bubbleSort(Population data[], int size) {         bool swap;         Population temp;         do         {                 swap = false;                 for (int count = 0; count < (size - 1); count++)                 {                                if (data[count].pop > data[count + 1].pop)                         {                                 temp = data[count];                                 data[count] = data[count +1];                                 data[count +1] = temp;                                 swap = true;                                                        }                 }         } while (swap); }```
• May 11th, 2014, 01:14 PM
2kaud
Re: Sorting with selection, insertion, and bubble sort
Rather than directly provide the corected code, do a google search for 'insertion sort c++', look at some of the sites referenced. See if you can work out what's the issue. If you look at some of the sites and still can't get the code to work I'll post the working code.
• May 11th, 2014, 01:37 PM
elephant7
Re: Sorting with selection, insertion, and bubble sort
Okay I think I got it to work, if you wouldn't mind checking over the insertion sort function:
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;         }         ofstream out("PopulationReport.txt");         Population  unSorted[maxsize],         sortedArray[maxsize];         int popsize = loadElements(ifs, unSorted);         copyPop(unSorted, sortedArray, popsize);         out << "Selection Sort: ";         selectionSort(sortedArray, popsize);         displayArray(sortedArray, popsize);         out << endl << endl << endl;         out << "Insertion Sort: ";         insertionSort(sortedArray, popsize);         displayArray(sortedArray, popsize);         out << endl << endl << endl;         out << "Bubble Sort: ";         bubbleSort(sortedArray, popsize);         displayArray(sortedArray, popsize);         out << 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;                         }                 }                 Population temp = data[minindex];                 data[minindex] = data[startscan];                 data[startscan] = temp;         } } void insertionSort(Population data[], int size) {         int j;                         for (int i = 1; i < size; i++)         {                 j = i;                                 while (j > 0 && data[j].pop < data[j-1].pop)                 {                           Population temp = data[j];                           data[j] = data[j-1];                           data[j-1] = temp;                           j--;                 }         }        } void bubbleSort(Population data[], int size) {         bool swap;         Population temp;         do         {                 swap = false;                 for (int count = 0; count < (size - 1); count++)                 {                                if (data[count].pop > data[count + 1].pop)                         {                                 temp = data[count];                                 data[count] = data[count +1];                                 data[count +1] = temp;                                 swap = true;                                                        }                 }         } while (swap); }```
If I got that correct can you then look at where I attempted to output the results into a file?
It outputs:
Code:

```Selection Sort: Insertion Sort: Bubble Sort:```
So I tried doing:
Code:

```out << "Selection Sort: "; out << selectionSort(sortedArray, popsize); out << displayArray(sortedArray, popsize); out << endl << endl << endl;```
But it says I can't do that, can you help me get this part to work?

Thank you for all of your help!!
Much appreciated!
• May 11th, 2014, 02:36 PM
2kaud
Re: Sorting with selection, insertion, and bubble sort
Quote:

If I got that correct
Yes, but it can be slightly simplified - see code below

Code:

```out << selectionSort(sortedArray, popsize); out << displayArray(sortedArray, popsize);```
No, you can't do this as these functions don't return any value that can be output. The easiet way is to change displayArray() so that it takes a stream argument like in the code below. This way displayArray() will output the data to the specified output stream (as the 3rd parameter) or to cout if the 3rd paramater is not specified.
Code:

```#include <iostream> #include <fstream> #include <string> using namespace std; const string filename = "population.csv"; const string outputname = "PopulationReport.txt"; 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, ostream& out = cout); 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;         } ofstream out(outputname.c_str());         if (!out.is_open()) {                 cout << "could not open output file " << outputname << endl;                 return 2;         }         Population  unSorted[maxsize],         sortedArray[maxsize];         int popsize = loadElements(ifs, unSorted);         out << "Unsorted:\n";         displayArray(unSorted, popsize, out);         out << "Selection Sort: \n";         copyPop(unSorted, sortedArray, popsize);         selectionSort(sortedArray, popsize);         displayArray(sortedArray, popsize, out);         out << "Insertion Sort: \n";         copyPop(unSorted, sortedArray, popsize);         insertionSort(sortedArray, popsize);         displayArray(sortedArray, popsize, out);         out << "Bubble Sort: \n";         copyPop(unSorted, sortedArray, popsize);         bubbleSort(sortedArray, popsize);         displayArray(sortedArray, popsize, out);         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, ostream & out) {         for (int i = 0; i < elems; ++i)                 out << data[i].state << " " << data[i].county << " " << data[i].pop << " " << data[i].rank << endl;         out << 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) {         for (int startscan = 0; startscan < (size - 1); startscan++)         {                 int minindex = startscan;                 int minvalue = data[startscan].pop;                 for (int index = startscan + 1; index < size; index++)                         if (data[index].pop < minvalue)                                 minvalue = data[minindex = index].pop;                 Population temp = data[minindex];                 data[minindex] = data[startscan];                 data[startscan] = temp;         } } void insertionSort(Population data[], int size) {         for (int i = 1; i < size; i++)                 for (int j = i; j > 0 && data[j - 1].pop > data[j].pop; --j) {                         Population tmp = data[j];                         data[j] = data[j - 1];                         data[j - 1] = tmp;                 }  } void bubbleSort(Population data[], int size) { bool swap;         do         {                 swap = false;                 for (int count = 0; count < (size - 1); count++)                         if (data[count].pop > data[count + 1].pop)                         {                                 Population temp = data[count];                                 data[count] = data[count + 1];                                 data[count + 1] = temp;                                 swap = true;                                                        }         } while (swap); }```
All you have to do now is part 8 from the original requirement in post #1.
Show 50 post(s) from this thread on one page
Page 2 of 2 First 12