Sorting Program Create a Sortlist that implements the following sorting methods:
ID: 3766450 • Letter: S
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
//main.cpp
#include "RANDOM.H"
#include "TIMER.H"
#include "SORTLIST.H" // SORTABLE LIST SPECIFICATION
#include <iostream>
using namespace std;
//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.
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; // help out a poor old compiler
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;
} // end of outer switch statement
} // end of outer while statement
}
//key.cpp
#include "KEY.H"
int Key::comparisons = 0;
int Key::assignments = 0;
void Key::initialize()
{
comparisons = 0;
}
int Key::sizeer()
{
return comparisons;
}
Key::Key (int x)
{
key = x;
}
Key &Key::operator =(const Key &x)
{
Key::assignments++;
key = x.key;
return *this;
}
bool operator ==(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() == y.the_key();
}
bool operator !=(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() != y.the_key();
}
bool operator >=(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() >= y.the_key();
}
bool operator <=(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() <= y.the_key();
}
bool operator >(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() > y.the_key();
}
bool operator <(const Key &x, const Key &y)
{
Key::comparisons++;
return x.the_key() < y.the_key();
}
int Key::the_key() const
{
return key;
}
//key.h
#ifndef KEY_H
#define KEY_H
class Key {
int key;
public:
static int comparisons; // # of Key comparisons
static int assignments; // # of Key Assignment
static void initialize();
static int sizeer();
Key ( int x = 0 );
int the_key() const;
Key &operator =(const Key &y);
};
bool operator ==(const Key &y,const Key &x);
bool operator !=(const Key &y,const Key &x);
bool operator >=(const Key &y,const Key &x);
bool operator <=(const Key &y,const Key &x);
bool operator >(const Key &y,const Key &x);
bool operator <(const Key &y,const Key &x);
#endif
//list.h
const int MAX_LIST=10000;
template <class T>
class List
{
public:
List(); //default constructor. Create an empty list.
bool isEmpty() const; // test if the list is empty
bool isFull() const; // test if the list is full
int getLength() const; // get the length of the list
void insert(int index, const T& newItem, bool& success);
//Insert the newItem into the list at position index. NOTE: 0<=index<=getlength()
void remove(int index, bool& success);
//Remove an item from the list at position index. NOTE: 0<=index<=getlength()
void retrieve(int index, T& dataItem, bool& success) const;
// Retrieve a list item by position index. NOTE: 0<=index<=getlength()
void traverse (void(*visit)(T &));
//Traverse all items in the list from the beginning to the end
void clear(); // Remove all items from the list.
protected:
T items[MAX_LIST];
int size; // number of items in the list
};
template <class T>
List<T>::List()
{
size=0;
}
template <class T>
bool List<T>::isEmpty() const
{
return (size==0);
}
template <class T>
bool List<T>::isFull() const
{
return (size >= MAX_LIST);
}
template <class T>
int List<T>::getLength() const
{
return size;
}
template <class T>
void List<T>::clear()
{
size=0;
}
template <class T>
void List<T>::insert(int index, const T& newItem, bool& success)
{
success=(index>=0)&&(index<=size)&&(size<MAX_LIST);
if (success)
{
for (int i=size-1; i>=index; i--)
{
items[i+1]=items[i];
}
items[index]=newItem;
size++;
}
}
template <class T>
void List<T>::remove(int index, bool& success)
{
success=(index>=0)&&(index<size);
if (success)
{
for (int i=index; i<size; i++)
items[i]=items[i+1];
size--;
}
}
template <class T>
void List<T>::retrieve(int index, T& dataItem, bool& success) const
{
success=(index>=0)&&(index<size);
if (success)
{
dataItem=items[index];
}
}
template <class T>
void List<T>::traverse(void (*visit)(T &))
{
for (int i=0; i<size; i++)
(*visit)(items[i]);
}
//random.h
#ifndef RANDOM_H
#define RANDOM_H
class Random {
public:
Random(bool pseudo = true);
// Declare random-number generation methods here.
int random_integer(int low, int high);
double random_real();
int poisson(double mean);
private:
int reseed(); // Re-randomize the seed.
int seed,
multiplier, add_on; // constants for use in arithmetic operations
};
#endif
//random.cpp
#include <limits.h>
const int max_int = INT_MAX;
#include <math.h>
#include <time.h>
#include "RANDOM.H"
Random::Random(bool pseudo)
/*
Post: The values of seed, add_on, and multiplier
are initialized. The seed is initialized randomly only if
pseudo == false.
*/
{
if (pseudo) seed = 1;
else seed = int (time(NULL) % max_int);
multiplier = 2743;
add_on = 5923;
}
double Random::random_real()
/*
Post: A random real number between 0 and 1 is returned.
*/
{
double max = max_int + 1.0;
double temp = reseed();
if (temp < 0) temp = temp + max;
return temp / max;
}
int Random::random_integer(int low, int high)
/*
Post: A random integer between low and high (inclusive)
is returned.
*/
{
if (low > high) return random_integer(high, low);
else return ((int) ((high - low + 1) * random_real())) + low;
}
int Random::poisson(double mean)
/*
Post:
A random integer, reflecting a Poisson distribution
with parameter mean, is returned.
*/
{
double limit = exp(-mean);
double product = random_real();
int size = 0;
while (product > limit) {
size++;
product *= random_real();
}
return size;
}
int Random::reseed()
/*
Post:
The seed is replaced by a psuedorandom successor.
*/
{
seed = seed * multiplier + add_on;
return seed;
}
//record.h
#ifndef REC_H
#define REC_H
#include "Key.h"
class Record {
Key key;
public:
Record(int x);
Record();
// cast to Key to conduct and size comparisons and assignments.
// do not override comparisons and assignments operators
operator Key() const;
};
#endif
//record.cpp
#include "RECORD.H"
Record::Record()
{
key = 0;
}
Record::Record(int x)
{
key = x;
}
Record::operator Key() const
{
return key;
}
//timer.h
#include <time.h>
// Timer class to calculate time interval.
class Timer{
public:
Timer();
double elapsed_time();
void reset();
private:
clock_t start_time;
};
//timer.cpp
#include "TIMER.H"
Timer::Timer()
{
start_time = clock();
}
double Timer::elapsed_time()
{
clock_t end_time = clock();
return ((double) (end_time - start_time)) / ((double) CLK_TCK);
}
void Timer::reset()
{
start_time = clock();
}
//sortlist.h
#ifndef SORTLIST_H
#define SORTLIST_H
#include "LIST.H"
#include "KEY.H"
#include "RECORD.H"
template <class Record>
class Sortable_list: public List<Record> {
public:
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
private:
// add private member functions if needed
};
#endif
Explanation / Answer
#include"Key.h"
#include"List.h"
typedef Key Record;
template<class Record>
class Sortable_list:public List<Record>
{
public:
void insertion_sort();
void selection_sort();
int max_key(int low,int high);
void swap(int low,int high);
void shell_sort();
void Sort_interval(int start,int increment);
void quick_sort( );
void recursive_quick_sort(int low, int high);
int partition(int low, int high);
void build_heap( );
void Insert_heap(const Record ¤t,int low,int high);
void heap_sort();
void merge_sort();
void recursive_merge_sort(Record a[],int n);
void merge(Record *des,Record *p,Record *q,int pcount,int qcount);
};
template <class Record>
void Sortable_list<Record>::merge(Record *des,Record *p,Record *q,int pcount,int qcount)
{
int i=0;
int j=0;
for(int k=0;k<pcount+qcount;++k)
{
if(i<pcount&&j<qcount&&p[i]<=q[j])
{
des[k]=p[i];
i++;
}
else if(i<pcount&&j<qcount&&p[i]>q[j])
{
des[k]=q[j];
j++;
}
else if(i>=pcount)
{
des[k]=q[j];
j++;
}
else if(j>=qcount)
{
des[k]=p[i];
i++;
}
}
}
template <class Record>
void Sortable_list<Record>::recursive_merge_sort(Record a[],int n)
{
if(n>1)
{
Record *p=new Record[n/2];
Record *q=new Record[n-n/2];
for(int i=0;i<n/2;++i)
{
p[i]=a[i];
}
for(int j=n/2;j<n;++j)
{
q[j-n/2]=a[j];
}
recursive_merge_sort(p,n/2);
recursive_merge_sort(q,n-n/2);
merge(a,p,q,n/2,n-n/2);
}
}
template <class Record>
void Sortable_list<Record>::merge_sort( )
{
recursive_merge_sort(entry,count);
}
template<class Record>
void Sortable_list<Record>::insertion_sort()
{
int first_unsorted;
int position;
Record current;
for(first_unsorted=1;first_unsorted<count;first_unsorted++)
if(entry[first_unsorted]<entry[first_unsorted-1])
{
position=first_unsorted;
current=entry[first_unsorted];
do
{
entry[position]=entry[position-1];
position--;
}
while(position>0&&entry[position-1]>current);
entry[position]=current;
}
}
template <class Record>
void Sortable_list<Record>::selection_sort( )
{
for(int position=count-1;position>0;position--)
{
int max=max_key(0, position);
swap(max, position);
}
}
template <class Record>
int Sortable_list<Record>::max_key(int low, int high)
{
int largest,current;
largest=low;
for(current=low+1;current<=high;current++)
if(entry[largest]<entry[current])
largest=current;
return largest;
}
template <class Record>
void Sortable_list<Record>::swap(int low,int high)
{
Record temp;
temp=entry[low];
entry[low]=entry[high];
entry[high]=temp;
}
template <class Record>
void Sortable_list<Record>::Sort_interval(int start,int increment)
{
int first_unsorted;
int position;
Record current;
for(first_unsorted=start+increment;first_unsorted<count;first_unsorted=first_unsorted+increment)
if(entry[first_unsorted]<entry[first_unsorted-increment])
{
position=first_unsorted;
current=entry[first_unsorted];
do
{
entry[position]=entry[position-increment];
position-=increment;
}
while(position>start&&entry[position-increment]>current);
entry[position]=current;
}
}
template <class Record>
void Sortable_list<Record>::shell_sort( )
{
int increment, start;
increment=count;
do
{
increment=increment/3+1;
for(start=0;start<increment;start++)
Sort_interval(start,increment);
}
while(increment>1);
}
template <class Record>
void Sortable_list<Record>::quick_sort( )
{
recursive_quick_sort(0, count - 1);
}
template <class Record>
void Sortable_list<Record>::recursive_quick_sort(int low, int high)
{
int pivot_position;
if(low<high)
{
pivot_position=partition(low, high);
recursive_quick_sort(low,pivot_position-1);
recursive_quick_sort(pivot_position+1,high);
}
}
template <class Record>
int Sortable_list<Record>::partition(int low, int high)
{
Record pivot;
int i,last_small;
swap(low,(low + high)/2);
pivot=entry[low];
last_small=low;
for(i=low+1;i<=high;i++)
if (entry[i] < pivot)
{
last_small=last_small+1;
swap(last_small, i);
}
swap(low, last_small);
return last_small;
}
template <class Record>
void Sortable_list<Record>::heap_sort( )
{
Record current;
int last_unsorted;
build_heap( );
for(last_unsorted=count-1;last_unsorted>0;last_unsorted--)
{
current=entry[last_unsorted]; entry[last_unsorted]=entry[0];
Insert_heap(current,0,last_unsorted-1);
}
}
template <class Record>
void Sortable_list<Record>::Insert_heap(const Record ¤t,int low,int high)
{
int large;
large=2*low+1;
while(large<=high)
{
if(large<high&&entry[large]<entry[large +1])
large++;
if(current>entry[large])
break;
else
{
entry[low]=entry[large];
low=large;
large=2*low+1;
}
}
entry[low]=current;
}
template <class Record>
void Sortable_list<Record>::build_heap( )
{
int low;
for(low=count/2-1;low>=0;low--)
{
Record current=entry[low];
Insert_heap(current,low,count-1);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.