#ifndef ORDERED_LIST_H
#define ORDERED_LIST_H
#include "list.h"
//header file ORDERED_LIST.H for class
//Ordered_list. This is a derived class
//from the array-based List class.
//Methods of insert and replace are redefined.
//Because this is a template class,
//both interface and implementation
//are in the header file
//Class interface and implementation
//of both insert methods are
//from Kruse, Section 7.3.1
template <class List_entry>
class Sortable_list:public List<List_entry>
{
public:
// methods of the Ordered_list ADT
Sortable_list();
//constructor
//postcondition: empty list has been created
bool SortCheck();
//checks if the list is sorted;
void insertion_sort();
int max_int(int low, int high);
void swap(int low, int high);
void selection_sort();
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 heap_sort();
void insert_heap(const List_entry ¤t, int low, int high);
void build_heap();
void COMBSORT();
};
#endif //Sortable_list_H
template <class List_entry>
Sortable_list<List_entry>::Sortable_list()
//constructor
//postcondition: empty sortable list has been created
{
count = 0;
}
template <class List_entry>
bool Sortable_list<List_entry>::SortCheck()
//precondition: array list has supposedly been sorted
//postcondition: returns true if sorted, false if not
{
int ARRAY_SIZE = 5;
bool flag = true;
for (int i = 0; i < ARRAY_SIZE-1; i++)
{
if (entry[i] > entry[i+1])
flag = false;
}
return flag;
}
template <class List_entry>
void Sortable_list<List_entry>::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.
Uses: Methods for the class List_entry; the contiguous List implementation of
Chapter 6
*/
{
int first_unsorted; // position of first unsorted entry
int position; // searches sorted part of list
int current; // holds the entry temporarily removed from list
for (first_unsorted = 1; first_unsorted < count; first_unsorted++)
if (entry[first_unsorted] < entry[first_unsorted - 1]) {
position = first_unsorted;
current = entry[first_unsorted]; // Pull unsorted entry out of the list.
do { // Shift all entries until the proper position is found.
entry[position] = entry[position - 1];
position--; // position is empty.
} while (position > 0 && entry[position - 1] > current);
entry[position] = current;
}
}
template <class List_entry>
void Sortable_list<List_entry>::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: The contiguous List implementation of Chapter 6.
*/
{
List_entry temp;
temp = entry[low];
entry[low] = entry[high];
entry[high] = temp;
}
template <class List_entry>
int Sortable_list<List_entry>::max_int(int low, int high)
/*
Pre: low and high are valid positions in the Sortable_list and low <= high.
Post: The position of the entry between low and high with the largest
key is returned.
Uses: The class List_entry. The contiguous List implementation of Chapter 6.
*/
{
int largest, current;
largest = low;
for (current = low + 1; current <= high; current++)
if (entry[largest] < entry[current])
largest = current;
return largest;
}
template <class List_entry>
void Sortable_list<List_entry>::selection_sort()
/*
Post: The entries of the Sortable_list have been rearranged so that
the keys in all the entries are sorted into nondecreasing order.
Uses: max_key, swap.
*/
{
for (int position = count - 1; position > 0; position--) {
int max = max_int(0, position);
swap(max, position);
}
}
template <class List_entry>
void Sortable_list<List_entry>::shell_sort()
/*
Post: The entries of the Sortable_list have been rearranged so that
the keys in all the entries are sorted into nondecreasing order.
Uses: sort_interval
*/
{
int increment, // spacing of entries in sublist
start; // starting point of sublist
increment = count;
do {
increment = increment / 3 + 1;
for (start = 0; start < increment; start++)
sort_interval(start, increment); // modified insertion sort
} while (increment > 1);
}
template <class List_entry>
void Sortable_list<List_entry>::sort_interval(int start, int increment)
/*
Post: the sublist defined by "increment" has been sorted?
Uses: Methods for the class List_entry; the contiguous List implementation of
Chapter 6
--supposed to be a "modified insertion sort" ...
*/
{
int first_unsorted; // position of first unsorted entry
int position; // searches sorted part of list
int current; // holds the entry temporarily removed from list
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]; // Pull unsorted entry out of the list.
do { // Shift all entries until the proper position is found.
entry[position] = entry[position - increment];
position=(position-increment); // position is empty.
} while (position > 1 && entry[position - increment] > current);
entry[position] = current;
}
}
// Section 8.8:
template <class List_entry>
void Sortable_list<List_entry>::quick_sort()
/*
Post: The entries of the Sortable_list have been rearranged so
that their keys are sorted into nondecreasing order.
Uses: The contiguous List implementation of Chapter 6, recursive_quick_sort.
*/
{
recursive_quick_sort(0, count - 1);
}
template <class List_entry>
void Sortable_list<List_entry>::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: The contiguous List implementation of Chapter 6,
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 List_entry>
int Sortable_list<List_entry>::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(int i, int j) (interchanges entries in positions
i and j of a Sortable_list), the contiguous List implementation
of Chapter 6, and methods for the class List_entry.
*/
{
List_entry 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 = 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 (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 List_entry>
void Sortable_list<List_entry>::heap_sort()
/*
Post: The entries of the Sortable_list have been rearranged so
that their keys are sorted into nondecreasing order.
Uses: The contiguous List implementation of Chapter 6,build_heap,
and insert_heap.
*/
{
List_entry current; // temporary storage for moving entries
int last_unsorted; // Entries beyond last_unsorted have been sorted.
build_heap(); // First phase: Turn the list into a heap.
for (last_unsorted = count - 1; last_unsorted > 0; last_unsorted--) {
current = entry[last_unsorted]; // Extract the last entry from the list.
entry[last_unsorted] = entry[0]; // Move top of heap to the end
insert_heap(current, 0, last_unsorted - 1); // Restore the heap
}
}
template <class List_entry>
void Sortable_list<List_entry>::insert_heap(const List_entry ¤t, int low, int high)
/*
Pre: The entries of the Sortable_list between indices low + 1 and high,
inclusive, form a heap. The entry in position low will be discarded.
Post: The entry current has been inserted into the Sortable_list
and the entries rearranged
so that the entries between indices low and high, inclusive,
form a heap.
Uses: The class List_entry, and the contiguous List implementation of Chapter 6.
*/
{
int large; // position of child of entry[low] with the larger key
large = 2 * low + 1; // large is now the left child of low.
while (large <= high) {
if (large < high && entry[large] < entry[large + 1])
large++; // large is now the child of low with the largest key.
if (current >= entry[large])
break; // current belongs in position low.
else { // Promote entry[large] and move down the tree.
entry[low] = entry[large];
low = large;
large = 2 * low + 1;
}
}
entry[low] = current;
}
template <class List_entry>
void Sortable_list<List_entry>::build_heap()
/*
Post: The entries of the Sortable_list have been rearranged
so that it becomes a heap.
Uses: The contiguous List implementation of Chapter 6, and insert_heap.
*/
{
int low; // All entries beyond the position low form a heap.
for (low = count / 2 - 1; low >= 0; low--) {
List_entry current = entry[low];
insert_heap(current, low, count - 1);
}
}
template <class List_entry>
void Sortable_list<List_entry>::COMBSORT()
{
int SWITCH = 0;
int GAP = count;
char temp;
do
{
GAP = int(GAP/1.3);
if (GAP==0)
GAP=1;
SWITCH = 0;
for(int I = 0; I<(count - GAP); I++)
{
int J = I + GAP;
if (entry[I] > entry[J])
{
//SWAP THE ELEMENTS
int HOLD = entry[I];
entry[I] = entry[J];
entry[J] = HOLD;
SWITCH = SWITCH + 1;
}
}
}
while((SWITCH != 0) || (GAP != 1));
}