CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

Thread: Sorting with selection, insertion, and bubble sort

1. 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/

2. Junior Member
Join Date
Apr 2014
Posts
17

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

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];

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

3. Re: Sorting with selection, insertion, and bubble sort

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

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];

copyPop(unSorted, sortedArray, popsize);
displayArray(unSorted, popsize);

cout << "Selection Sort: \n";
selectionSort(sortedArray, popsize);
displayArray(sortedArray, popsize);
cout << endl;

return 0;
}

{
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.

4. Junior Member
Join Date
Apr 2014
Posts
17

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

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];

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 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);
}```
Last edited by elephant7; May 11th, 2014 at 12:47 PM.

5. 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.

6. Junior Member
Join Date
Apr 2014
Posts
17

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

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];

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 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!

7. Re: Sorting with selection, insertion, and bubble sort

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

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];

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 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.

Posting Permissions

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