write a c++ code 1.Implement the method for count sort in the file Sortable_list

ID: 3857392 • Letter: W

Question

write a c++ code

1.Implement the method for count sort in the file Sortable_list.h.

Note: This count sort is different from the count sort on the Internet. You must read the description below carefully to make sure that you do not implement the wrong sorting algorithm.

Count sort is a simple algorithm that begins with an unsorted list and creates a new sorted list. It assumes that all the records/keys in the original unsorted list are different, i.e., there are no duplicate keys in the list. For each record in the original list, count sort scans the list once and counts how many records/keys are smaller. For example, if c is the count for a record r, then the proper location for r in the sorted list is c.

sortable_list.h

template <class Record>
class Sortable_list:public List<Record> {
public:
// Add prototypes for sorting methods here
void insertion_sort();
void count_sort();
void merge_sort();
void quick_sort();
protected:
// Add prototypes for auxiliary functions here
void recursive_merge_sort(int low, int high);
void merge(int low, int high);

void recursive_quick_sort(int low, int high);
int partition(int low, int high);
void swap(int low, int high);
};

template <class Record>
void Sortable_list<Record>::insertion_sort()
/*
Post: The entries of the Sortable_list have been rearranged so that
the keys in all the entries are sorted into nondecreasing order.
*/
{
int first_unsorted; // position of first unsorted entry
int position; // searches sorted part of list
Record current; // holds the entry temporarily removed from list

for (first_unsorted = 1; first_unsorted < this->count; first_unsorted++)
if (this->entry[first_unsorted] < this->entry[first_unsorted - 1]) {
position = first_unsorted;
current = this->entry[first_unsorted]; // Pull unsorted entry out of the list.
do {
// Shift all entries until the proper position is found.
this->entry[position] = this->entry[position - 1];
position--; // position is empty.
} while (position > 0 && this->entry[position - 1] > current);
this->entry[position] = current;
}
}

template <class Record>
void Sortable_list<Record>::count_sort()
/*
Post: The entries of the Sortable_list have been rearranged so that
the keys in all the entries are sorted into nondecreasing order.
*/
{
// complete count sort here
}

template <class Record>
void Sortable_list<Record>::merge_sort()
/* Post: The entries of the sortable list have been rearranged so that their keys are sorted into non-decreasing order.
Uses: recursive_merge_sort
*/
{
recursive_merge_sort(0, this->size() - 1);
}

template <class Record>
void Sortable_list<Record> :: recursive_merge_sort(int low, int high)
{
if (high > low) {
recursive_merge_sort(low, (high + low) / 2);
recursive_merge_sort((high + low) / 2 + 1, high);
merge(low, high);
}
}

template <class Record>
void Sortable_list<Record>::merge(int low, int high)
{
Record *temp = new Record[high - low + 1];
int index = 0;
int index1 = low, mid = (low + high) / 2, index2 = mid + 1;
while (index1 <= mid && index2 <= high) {
if (this->entry[index1] < this->entry[index2])
temp[index++] = this->entry[index1++];
else
temp[index++] = this->entry[index2++];
}
while (index1 <= mid)
temp[index++] = this->entry[index1++];
while (index2 <= high)
temp[index++] = this->entry[index2++];
for (index = low; index <= high; index++)
this->entry[index] = temp[index -low];
delete []temp;
}

template <class Record>
void Sortable_list<Record>::quick_sort()
/*
Post: The entries of the Sortable_list have been rearranged so
that their keys are sorted into nondecreasing order.
Uses: recursive_quick_sort.
*/
{
recursive_quick_sort(0, this->count - 1);
}

template <class Record>
void Sortable_list<Record>::recursive_quick_sort(int low, int high)
/*
Pre: low and high are valid positions in the Sortable_list.
Post: The entries of the Sortable_list have been
rearranged so that their keys are sorted into nondecreasing order.
Uses: recursive_quick_sort and partition.
*/
{
int pivot_position;
if (low < high) { // Otherwise, no sorting is needed.
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)
/*
Pre: low and high are valid positions of the Sortable_list, with low <= high.
Post: The center (or left center) entry in the range between indices
low and high of the Sortable_list
has been chosen as a pivot. All entries of the Sortable_list
between indices low and high, inclusive, have been
rearranged so that those with keys less than the pivot come
before the pivot and the remaining entries come
after the pivot. The final position of the pivot is returned.
Uses: swap
*/
{
Record pivot;
int i, // used to scan through the list
last_small; // position of the last key less than pivot
swap(low, (low + high) / 2);
pivot = this->entry[low]; // First entry is now pivot.
last_small = low;
for (i = low + 1; i <= high; i++)
/*
At the beginning of each iteration of this loop, we have the following
conditions:
If low < j <= last_small then entry[j].key < pivot.
If last_small < j < i then entry[j].key >= pivot.
*/
if (this->entry[i] < pivot) {
last_small = last_small + 1;
swap(last_small, i); // Move large entry to right and small to left.
}
swap(low, last_small); // Put the pivot into its proper position.
return last_small;
}

template <class Record>
void Sortable_list<Record>::swap(int low, int high)
/*
Pre: low and high are valid positions in the Sortable_list.
Post: The entry at position low is swapped with the entry at position high.
Uses:
*/
{
Record temp;
temp = this->entry[low];
this->entry[low] = this->entry[high];
this->entry[high] = temp;
}

Explanation / Answer

sortable_list.h

void recursive_quick_sort(int low, int high);
int partition(int low, int high);
void swap(int low, int high);
};

Navigate

write a c++ class definition called SAMPLEST_VOIP_FSM which will evaluate the st

write a c++ code 6. Implement quicksort for linked lists. You are required to im

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

write a c++ code 1.Implement the method for count sort in the file Sortable_list

Question

Explanation / Answer

Related Questions

Navigate