Tuesday, April 20, 2010

C++ exercises: selection sort, bubble sort, insertion sort

Q: Consider the record declaration
struct Month { char name[10]; //name of a month
int monthnum; //number of days in the month
};

a) Write a function
void SortByName(Month months[], int n);
that sorts an array whose elements are of type month by comparing names (use C++ function strcmp). Also write a function
void SortbyDays(Month months[], int n);
that sorts the list by comparing the number of days in a month. Write a main program that declares an array containing all the months of the year and sorts it using both functions. Print each sorted list.
b) Note that sorting a list of months by number of days produces ties. When this happens a sorting method can use a secondary key to break ties. Write the function
void Sort2byDays(Month months[], int n);
that sorts the list by first comparing the number of days and, if a tie occurs, breaks the tie by comparing names. Use the function in a main program to print out an ordered list of all the months in the year, ordered by number of days.

```#include <iostream>

using namespace std;

struct Month {
char name[10];
int monthnum;
};

// Selection sort.
void SortByName(Month month[], int n)
{
if (n < 2)
return;

Month hold;
int min_idx;
for (int i = 0; i < n - 1; i++)
{
hold = month[i];  // selected one to be exchanged with the min.
min_idx = i;
for (int j = i + 1; j < n; j++)
{
if (strcmp(month[i].name, month[j].name) > 0)
{
// Find the min one.
// Put to the first pos (index of i).
month[i] = month[j];
min_idx = j;
}
}

if (i != min_idx)
month[min_idx] = hold;
}
}

// Bubble sort.
void SortByDays(Month month[], int n)
{
if (n < 2)
return;

bool changed;
for (int i = n - 1; i >= 0; i--)
{
changed = false;
for (int j = 0; j < i; j++)
{
if (month[j].monthnum > month[j+1].monthnum)
{
Month tmpmon;
tmpmon = month[j];
month[j] = month[j+1];
month[j+1] = tmpmon;

changed = true;
}
}
if (!changed)
break;
}
}

// overload operator < for Month
bool operator<(const Month& mon1, const Month& mon2)
{
if (mon1.monthnum < mon2.monthnum)
return true;
else if (mon1.monthnum > mon2.monthnum)
return false;

// monthnum equal
if (strcmp(mon1.name, mon2.name) < 0)
return true;
else
return false;
}

// Insertion sort
void Sort2ByDays(Month month[], int n)
{
Month hold;

for (int i = 1; i < n; i++)
{
hold = month[i];  // the one to be inserted.

int j;
for (j = i; j > 0; j--)
{
if (hold < month[j-1])
month[j] = month[j-1]; // shift right. j-1 is reserved for "hold"
else
break;
}
month[j] = hold;  // j is the position for what we selected.
}
}

void PrintMonths(Month month[], int n)
{
for (int i = 0; i < n; i++)
{
cout << month[i].name << " " << month[i].monthnum << endl;
}
cout << endl;
}

int main()
{
const Month months[12] = {
{"January", 31},
{"February", 28},
{"March", 31},
{"April", 30},
{"May", 31},
{"June", 30},
{"July", 31},
{"August", 31},
{"September", 30},
{"October", 31},
{"November", 30},
{"December", 31}
};

Month mn[12];

cout << "--- Original ---" << endl;
memcpy(mn, months, sizeof(mn));
PrintMonths(mn, 12);

cout << "--- SortByName ---" << endl;
memcpy(mn, months, sizeof(mn));
SortByName(mn, 12);
PrintMonths(mn, 12);

cout << "--- SortByDays ---" << endl;
memcpy(mn, months, sizeof(mn));
SortByDays(mn, 12);
PrintMonths(mn, 12);

cout << "--- Sort2ByDays ---" << endl;
memcpy(mn, months, sizeof(mn));
Sort2ByDays(mn, 12);
PrintMonths(mn, 12);

return 0;
}
```