Sorting Program Create a Sortlist that implements the following sorting methods:

Question

Sorting Program

Create a Sortlist that implements the following sorting methods:

Insertion sort

Selection sort

Shell sort (optional)

Quick sort

Heap sort (optional)

Bubble sort

Merge sort

and calculate and print

The CPU time

The number of comparison of keys

The number of assignments of list entries during the sorting list.

Requirements

1. The following source files are given through SortList.zip

Key.h and Key.cpp implement the Key class to conduct and count Key comparisons and assignments.

Record.h and Record.cpp implement the Record class which is used as List items. Also, it provides operator Key to conduct and count comparisons and assignments.

List.h is the template based array-based implementation of List class

Random.h and Random.cpp implement the Random class to set random seed and generate random integers.

Timer.h and Timer.cpp implement the Timer class to calculate time interval.

Main.cpp is the test driver to test the Sortlist class. It contains user interface, filling the list with random integers, calling Sortlist sorting functions and calculate the CPU time, the number of comparison of keys, and the number of assignments of list entries during the sorting list.

Sortlist.h is the derived class of the List class. You MUST follow the public functions I provide, but you can add more member functions if necessary.

2. Implement the following member functions

void insertion_sort(); // todo: implement insertion sort

void selection_sort(); // todo: implement selection sort

void shell_sort(); // todo; implement shell sort

void quick_sort(); // todo; implement quick sort

void heap_sort(); // todo; implement heap sort (optional)

void bubble_sort(); // todo; implement bubble sort

void merge_sort(); // todo; implement merge sort

3. Submit Sortlist.h (Sortlist.cpp)

Explanation / Answer

#ifndef SORTLIST_H
#define SORTLIST_H
#include <stdafx.h>
#include "LIST.H"
#include "KEY.H"
#include "RECORD.H"
template <class Record>
class Sortable_list: public List<Record>
{
public:
void insertion_sort(ItemType theArray[], int n)
{
for (int unsorted = 1; unsorted < n; unsorted++)
{
ItemType nextItem = theArray[unsorted];
int loc = unsorted;
while ((loc> 0)&& (theArray[loc - 1] > nextItem))
{
theArray[loc] = theArray[loc - 1];
}
theArray[loc] = nextItem;
loc--;
}
}
void selection_sort(ItemType the Arrray[], int n)
{
for(int last = n-1; last >1; last--)
{
int largest = findIndexofLargest(theArray, last+1);
std::swap(theArray[largest], theArray[last]);
}
}
int findIndexofLargest(const ItemType theArray[], int size)
{
int indexSoFar = 0 ;
for (int currentIndex = 1; currentIndex <size; currentIndex++)
{
if (theArray[currentIndex] > theArray[indexSoFar])
indexSoFar = currentIndex;
}
return indexSoFar;
}
void quick_sort(ItemType the Array [], int first, int last)
{
if(last - first + 1 <MAX_LIST)
{
insertionSort(theArray, first, last);
}
else
{
int pivotIndex = partition(theArray, first, last);
quick_sort(theArray, first, pivotIndex - 1);
quick_sort(theArray, pivotIndex + 1, last);
}
}

void bubble_sort(ItemType theArray[], int n)
{
bool sorted = false;
int pass = 1;
while (!sorted && (pass < n))
{
sorted = true;
for (int index = 0; index < n - pass; index++)
{
int nextIndex = index + 1;
if (theArray[index] > theArray[nextIndex])
{
std::swap(theArray[index], theArray[nextIndex]);
sorted = false;
}
}
pass++;
}
}
void merge(ItemType theArray[], int first, int mid, int last)
{
ItemType tempArray[MAX_LIST];
int first1= first;
int last1 = mid;
int first2 = mid+1;
int last2 = last;
int index = first1;
while ((first1 <= last1) && (first2 <= last2))
{
if (theArray[first1] <= theArray[first2])
{
tempArray[index] = theArray[first1]);
first1++;
}
else
{
tempArray[index] = theArray[first2];
first2++;
}
index++;
}
while (first1 <= last1)
{
tempArray[index] = theArray[first1;
first++;
index++;
}
while (first2 <= last2)
{
tempArray[index] = theArray[first2];
first2++;
index++;
}
for (index = first; index <= last; index++)
theArray[index] = tempArray[index];
}

void merge_sort(ItemType theArray[], int first, int last)
{
if (first < last)
{
int mid = first + (last - first) / 2;
merge_sort(theArray, first, mid);
merge_sort(theArray, mid + 1, last);
merge_sort(theArray, first, mid, last);
}
}
};

//Main.cpp is the test driver to test the Sortlist class.

#include "stdafx.h"
#include "RANDOM.H"
#include "TIMER.H"
#include "SORTLIST.H"   
#include <iostream>
using namespace std;
void write_entry(Record &c)
{
cout << ((Key) c).the_key() << " ";
}
void help()
{
cout << "User options are: "

<< "[H]elp [Q]uit (re)[F]ill list "

<< "write [D]ata write sorted [O]utput "

<< "[0] insertion sort "

<< "[1] selection sort "

<< "[2] shell sort "

<< "[3] quick sort "

<< "[4] heap sort "

<< "[5] bubble sort "

<< "[6] merge sort "
<< endl;
}
void intro()
{
cout << "Testing program for sorting methods for a contiguous list." << endl;
help ();
}
void main()
{
List<Record> s; List<Record> t = s;
intro();
int n;
Random dice;
bool report;
Record target;
Sortable_list<Record> the_list;
Sortable_list<Record> copy_list;
char command = ' ';
while (command != 'q' && command != 'Q')
{
cout << "Enter a command of H, Q, F, O, D, "<< "0, 1, 2, 3, 4, 5, 6: " << flush;
cin >> command;
switch (command)
{
case 'h': case 'H':
help();
break;
case 'd': case 'D':
cout << " Unsorted list ";
the_list.traverse(write_entry);
cout << endl;
break;
case 'o': case 'O':
cout << " Last sorted list ";
copy_list.traverse(write_entry);
cout << endl;
break;
case '0': case '1': case '2': case '3': case '4': case '5': case '6':
{
copy_list = the_list;

Key::comparisons = 0;

Key::assignments = 0;

Timer clock;

switch (command) {

case '0':

cout << "Insertion Sort ";

copy_list.insertion_sort();

break;

case '1':

cout << "Selection Sort ";

copy_list.selection_sort();
break;

case '2':

cout << " Shell Sort ";

copy_list.shell_sort();

break;

case '3':

cout << " Quick Sort ";

copy_list.quick_sort();

break;

case '4':

cout << " Heap Sort ";

copy_list.heap_sort();

break;

case '5':

cout << " Bubble Sort ";

copy_list.bubble_sort();

break;
case '6':

cout << " Merge Sort ";

copy_list.merge_sort();

break;

}

cout << "Time: " << clock.elapsed_time() << " seconds. "

<< "Comparisons: " << Key::comparisons << " "

<< "Assignments: " << Key::assignments

<< endl <<endl;
}
break;
case 'f': case 'F':
the_list.clear();
cout << "How many list entries would you like? "<< flush;
cin >> n;
for (int i = 0; i < n; i++)
{
target = dice.random_integer(0, 10 * n);
the_list.insert(i, target, report);
if (report == false)
{
cout << "Available list space filled up at " << i << " entries." << endl;
break;
}
if (report != true) i--;
}
break;
}
}
}

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.