All code should be in C++Using the UnsortedList class (UnsortedLis.pdf

All code should be in C++ Using the UnsortedList class (UnsortedList.h file below) write a function sublist which extracts elements that are smaller than a given item from the given list and forms a new list. The precondition of the function is: the list has been initialized and is not empty. The postconditions are: newList contains all the items of the list whose values are less than the given item. Implement the sublist function as a friend function of the UnsortedList class whose declaration is: friend void sublist(const UnsortedList& list, const ItemType& item, UnsortedList& newList); (Hint: The UnsortedList class has private members ItemType list[MAX_LENGTH]; int length; and the member functions getLength, resetList, insert, remove, etc.) //********************************************************** // SPECIFICATION FILE (UnsortedList.h) // This file gives the specification of a basic class // template for unsorted array-based lists. // The list components are not assumed to be in order by // value. //********************************************************** #ifndef UNSORTEDLIST_H #define UNSORTEDLIST_H #include #include // Needed for the exit function using namespace std; const int MAX_LENGTH = 100; // Maximum number of components template // You may also choose to use // typedef statement class UnsortedList { public: // Constructor UnsortedList();

// Post: Empty list has been created. length has been set to zero. // Knowledge responsibilities int getLength() const; // Post: Returns the length of the list bool isEmpty() const; // Post: Returns true if list is empty; false otherwise bool isFull() const; // Post: Returns true if list is full; false otherwise bool isInList(const ItemType& item) const; // Post: Returns true if item is int the list; false otherwise int seqSearch(const ItemType& item) const; // Function to search the list for a given item. // Post: If item is found, returns the index in the array where // item is found; otherwise, return -1. // Action Responsibilities void resetList(); // Post: The list becomes empty. length has been set to zero. void insert(const ItemType& item); // Function to insert item to the end of the list. However, first // the list is searched to see whether the item to be inserted is // already in the list. // Post: list[length] = item and length++. If item is already in // the list or the list is already full, an appropriate message is // displayed. void remove(const ItemType& item); // Function to remove item from the list. // Post: If item is found in the list, it is removed from the list // and length is decremented by one. // Overloaded [] operator declaration. // This function returns a reference to the element in the // array indexed by index. ItemType& operator[](const int& index); // Additional operations void sort(); // Post: list items have been put into ascending order by selection sort void selectionSort();

// Function to sort the items in the list. // Post: list items have been put into ascending order by selection sort void insertionSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by insertion sort void bubbleSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by bubble sort void shellSort(); // Function to sort the items in the list using Shell sort. // Before sorting starts, increments are computed and stored in an array. // A simple sorting algorithm is applied in all passes except the last. // A simple sorting algorithm is applied only in the last pass, for 1-sort. // Post: list items have been put into ascending order by Shell sort. void quickSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by quick sort void mergeSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by merge sort void heapSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by heap sort private: ItemType list[MAX_LENGTH]; // array to hold the list elements int length; // to store the length of the list void swap(ItemType& first, ItemType& second); // Function to swap two items. // Post: first and second have been swapped. void recQuickSort(int first, int last); // Function using recursion to implement quick sort for the subarray // with indices between first and last. // Post: the subarray indexed between first and last have been sorted // in ascending order by quick sort int partition(int first, int last);

// Function to partion the sublist indexed between first and last. // Post: the subarray indexed between first and last have been partitioned // into two sublists with the lower sublist smaller than the pivot // element and the upper sublist larger than the pivot element. The // location of pivot is returned. void recMergeSort(int first, int last); // Function using recursion to implement merge sort for the subarray // with indices between first and last. // Post: the subarray indexed between first and last have been sorted // in ascending order by merge sort void merge(int first, int mid, int last); // Function to merge the sublists list[first..mid] and list[mid+1..last] // into one list, i.e., list[first..last]. // Pre: the two sublists are sorted in ascending order // Post: the list list[first..last] merges the two sublists and have been // is sorted in ascending order void heapify(int low, int high); // Function to restore the heap in a subtree by making one // item assignment each time through the loop. // Post: the subtree indexed between low and high have // been organized into a heap }; //********************************************************** template UnsortedList::UnsortedList() { length = 0; } //********************************************************** template int UnsortedList::getLength() const { return length; } //********************************************************** template

bool UnsortedList::isEmpty() const { return (length == 0); } //********************************************************** template bool UnsortedList::isFull() const { return (length == MAX_LENGTH); } //********************************************************** template bool UnsortedList::isInList(const ItemType& item) const { int loc; bool found = false; for (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; } return found; } //********************************************************** template int UnsortedList::seqSearch(const ItemType& item) const { int loc; bool found = false; for (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; }

if (found) return loc; else return -1; } //********************************************************** template void UnsortedList::resetList() { length = 0; } //********************************************************** template void UnsortedList::insert(const ItemType& item) { if (length == 0) // list is empty { list[length] = item; length++; } else if (length == MAX_LENGTH) cout << "Cannot insert in a full list." << endl; else { if (!isInList(item)) // the item is not already in the list { list[length] = item; length++; } else cout << "The item is already in the list. " << "No duplicates are allowed." << endl; } } //**********************************************************

template void UnsortedList::remove(const ItemType& item) { int loc; if (length == 0) cout << "Cannot delete from an empty list." << endl; else { loc = seqSearch(item); if (loc != -1) // the item is already in the list { list[loc] = list[length - 1]; // copy the last element to // where item to be deleted was length--; } } } //********************************************************** template ItemType& UnsortedList::operator[](const int& index) { if (index < 0 || index >= length) { cout << "ERROR: Index out of range. "; exit(EXIT_FAILURE); } return list[index]; } //********************************************************** template void UnsortedList::sort() { int passCount; // Outer loop control variable int searchIndex; // Inner loop control variable int minIndex; // Index of minimum so far for (passCount = 0; passCount < length - 1; passCount++)

{ minIndex = passCount; // Find the index of the smallest component // in list[passCount..length-1] for (searchIndex = passCount + 1; searchIndex < length; searchIndex++) if (list[searchIndex] < list[minIndex]) minIndex = searchIndex; // Swap list[minIndex] and list[passCount] swap(list[minIndex], list[passCount]); } } //********************************************************** template void UnsortedList::swap(ItemType& first, ItemType& second) { ItemType temp; temp = first; first = second; second = temp; } ////********************************************************** //template //void UnsortedList::insertionSort() //{ // ItemType temp; // int firstOutOfOrder; // the first index of the unsorted sublist // int location; // // for (firstOutOfOrder = 1; firstOutOfOrder < length; // firstOutOfOrder++) // { // if ( list[firstOutOfOrder] < list[firstOutOfOrder - 1] ) // { // temp = list[firstOutOfOrder]; // location = firstOutOfOrder;

// // do // { // list[location] = list[location - 1]; // location--; // } while ( location > 0 && list[location - 1] > temp ); // // list[location] = temp; // } // } //} //********************************************************** template void UnsortedList::selectionSort() { int minIndex; // Index of minimum so far int i, j; for (i = 0; i < length - 1; i++) { for (j = i + 1, minIndex = i; j < length; j++) { if (list[j] < list[minIndex]) minIndex =j; swap(list[minIndex], list[i]); } } } //********************************************************** template void UnsortedList::insertionSort() { ItemType tmp; int i; // the first index of the unsorted sublist int j; for (i = 1; i < length; i++) {

tmp = list[i]; for (j = i; j > 0 && tmp < list[j - 1]; j--) list[j] = list[j - 1]; list[j] = tmp; } } //********************************************************** template void UnsortedList::bubbleSort() { int i, j; for (i = 0; i < length - 1; i++) { for (j = length - 1; j > i; j--) { if (list[j] < list[j - 1]) swap(list[j], list[j-1]); } } } //********************************************************** template void UnsortedList::shellSort() { int i, j, hCount, h; int increments[20], k; ItemType tmp; // create an appropriate number of increments h for (h = 1, i = 0; h < length && i < 20; i++) { increments[i] = h; h = 3 * h + 1; } // loop on the number of different increments h for (i--; i >= 0; i--) {

h = increments[i]; // loop on the number of subarrays h-sorted in ith pass for (hCount = h; hCount < 2 * h; hCount++) { // insertion sort for subarray containing every hth // element of array data for (j = hCount; j < length; ) { tmp = list[j]; k = j; while (k - h >= 0 && tmp < list[k - h]) { list[k] = list[k - h]; k -=h; } list[k] = tmp; j += h; } } } } //********************************************************** template void UnsortedList::quickSort() { recQuickSort(0, length-1); } //********************************************************** template void UnsortedList::recQuickSort(int first, int last) { int pivotLocation; if (first < last) { pivotLocation = partition(first, last); recQuickSort(first, pivotLocation - 1);

recQuickSort(pivotLocation + 1, last); } } //********************************************************** template int UnsortedList::partition(int first, int last) { ItemType pivot; int index, smallIndex; swap(list[first], list[(first + last) / 2]); pivot = list[first]; smallIndex = first; for (index = first + 1; index <= last; index++) { if (list[index] < pivot) { smallIndex++; swap(list[smallIndex], list[index]); } } swap(list[first], list[smallIndex]); return smallIndex; } //********************************************************** template void UnsortedList::mergeSort() { recMergeSort(0, length-1); } //********************************************************** template void UnsortedList::recMergeSort(int first, int last) { int mid; if (first < last) {

mid = (first + last) / 2; recMergeSort(first, mid); recMergeSort(mid + 1, last); merge(first, mid, last); } } //********************************************************** template void UnsortedList::merge(int first, int mid, int last) { ItemType * tmpArray; tmpArray = new ItemType[last - first +1]; int i = first, j = mid + 1, k = 0; while(i <= mid && j <= last) { if( list[i] < list[j] ) { tmpArray[k] = list[i]; i++; } else { tmpArray[k] = list[j]; j++; } k++; } if (i > mid ) { for(int h = j ; h <= last ; h++ ) { tmpArray[k] = list[h]; k++; } } else

{ for(int h = i; h <= mid ; h++ ) { tmpArray[k] = list[h]; k++; } } for(int i = first, k = 0; i <= last ; i++) { list[i] = tmpArray[k]; k++; } delete [] tmpArray; } //********************************************************** template void UnsortedList::heapSort() { // create the heap for (int i = length/2-1; i >= 0; i--) // list[length/2-1] is the // last element in the list which is not a leaf heapify(i, length - 1); for (int i = length-1; i >= 1; i--) { swap(list[0], list[i]); // move the largest item to list[i] heapify(0, i-1); // restore the heap property } } //********************************************************** template void UnsortedList::heapify(int low, int high) { ItemType tmp = list[low]; // copy the root node of the tree int largeIndex = 2 * low + 1; // index of the left child while (largeIndex <= high) {

if (largeIndex < high) { if (list[largeIndex] < list[largeIndex + 1]) largeIndex = largeIndex + 1; // index of the larger child } if (tmp > list[largeIndex]) // subtree is already in a heap break; else { list[low] = list[largeIndex]; // move the larger child to the root low = largeIndex; // go to the subtree to restore the heap largeIndex = 2 * low + 1; } }// end while list[low] = tmp; // insert tmp into the tree, that is, list } #endif Solution #ifndef UNSORTEDLIST_H #define UNSORTEDLIST_H #include #include // Needed for the exit function using namespace std; const int MAX_LENGTH = 100; // Maximum number of components template // You may also choose to use // typedef statement class UnsortedList { public: // Constructor UnsortedList(); // Post: Empty list has been created. length has been set to zero. // Knowledge responsibilities int getLength() const; // Post: Returns the length of the list

bool isEmpty() const; // Post: Returns true if list is empty; false otherwise bool isFull() const; // Post: Returns true if list is full; false otherwise bool isInList(const ItemType& item) const; // Post: Returns true if item is int the list; false otherwise int seqSearch(const ItemType& item) const; // Function to search the list for a given item. // Post: If item is found, returns the index in the array where // item is found; otherwise, return -1. // Action Responsibilities void resetList(); // Post: The list becomes empty. length has been set to zero. void insert(const ItemType& item); // Function to insert item to the end of the list. However, first // the list is searched to see whether the item to be inserted is // already in the list. // Post: list[length] = item and length++. If item is already in // the list or the list is already full, an appropriate message is // displayed. void remove(const ItemType& item); // Function to remove item from the list. // Post: If item is found in the list, it is removed from the list // and length is decremented by one. // Overloaded [] operator declaration. // This function returns a reference to the element in the // array indexed by index. ItemType& operator[](const int& index); // Additional operations void sort(); // Post: list items have been put into ascending order by selection sort void selectionSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by selection sort void insertionSort(); // Function to sort the items in the list.

// Post: list items have been put into ascending order by insertion sort void bubbleSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by bubble sort void shellSort(); // Function to sort the items in the list using Shell sort. // Before sorting starts, increments are computed and stored in an array. // A simple sorting algorithm is applied in all passes except the last. // A simple sorting algorithm is applied only in the last pass, for 1-sort. // Post: list items have been put into ascending order by Shell sort. void quickSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by quick sort void mergeSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by merge sort void heapSort(); // Function to sort the items in the list. // Post: list items have been put into ascending order by heap sort private: ItemType list[MAX_LENGTH]; // array to hold the list elements int length; // to store the length of the list void swap(ItemType& first, ItemType& second); // Function to swap two items. // Post: first and second have been swapped. void recQuickSort(int first, int last); // Function using recursion to implement quick sort for the subarray // with indices between first and last. // Post: the subarray indexed between first and last have been sorted // in ascending order by quick sort int partition(int first, int last); // Function to partion the sublist indexed between first and last. // Post: the subarray indexed between first and last have been partitioned // into two sublists with the lower sublist smaller than the pivot // element and the upper sublist larger than the pivot element. The // location of pivot is returned.

void recMergeSort(int first, int last); // Function using recursion to implement merge sort for the subarray // with indices between first and last. // Post: the subarray indexed between first and last have been sorted // in ascending order by merge sort void merge(int first, int mid, int last); // Function to merge the sublists list[first..mid] and list[mid+1..last] // into one list, i.e., list[first..last]. // Pre: the two sublists are sorted in ascending order // Post: the list list[first..last] merges the two sublists and have been // is sorted in ascending order void heapify(int low, int high); // Function to restore the heap in a subtree by making one // item assignment each time through the loop. // Post: the subtree indexed between low and high have // been organized into a heap friend void sublist(const UnsortedList& list, const ItemType& item, UnsortedList& newList); // Function extracts elements that are smaller than a given item from the given list // and forms a new list. // Pre: the list has been initialized and is not empty. // Post: newList contains all the items of the list whose values // are less than the given item. }; template UnsortedList::UnsortedList() { length = 0; } //********************************************************** template int UnsortedList::getLength() const { return length; } //********************************************************** template bool UnsortedList::isEmpty() const {

return (length == 0); } //********************************************************** template bool UnsortedList::isFull() const { return (length == MAX_LENGTH); } //********************************************************** template bool UnsortedList::isInList(const ItemType& item) const { int loc; bool found = false; for (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; } return found; } //********************************************************** template int UnsortedList::seqSearch(const ItemType& item) const { int loc; bool found = false; for (loc = 0; loc < length; loc++) if (list[loc] == item) { found = true; break; } if (found) return loc; else return -1; } //********************************************************** template

void UnsortedList::resetList() { length = 0; } //********************************************************** template void UnsortedList::insert(const ItemType& item) { if (length == 0) // list is empty { list[length] = item; length++; } else if (length == MAX_LENGTH) cout << "Cannot insert in a full list." << endl; else { if (!isInList(item)) // the item is not already in the list { list[length] = item; length++; } else cout << "The item is already in the list. " << "No duplicates are allowed." << endl; } } //********************************************************** template void UnsortedList::remove(const ItemType& item) { int loc; if (length == 0) cout << "Cannot delete from an empty list." << endl; else { loc = seqSearch(item); if (loc != -1) // the item is already in the list { list[loc] = list[length - 1]; // copy the last element to // where item to be deleted was length--; }

} } //********************************************************** template ItemType& UnsortedList::operator[](const int& index) { if (index < 0 || index >= length) { cout << "ERROR: Index out of range. "; exit(EXIT_FAILURE); } return list[index]; } //********************************************************** template void UnsortedList::sort() { int passCount; // Outer loop control variable int searchIndex; // Inner loop control variable int minIndex; // Index of minimum so far for (passCount = 0; passCount < length - 1; passCount++) { minIndex = passCount; // Find the index of the smallest component // in list[passCount..length-1] for (searchIndex = passCount + 1; searchIndex < length; searchIndex++) if (list[searchIndex] < list[minIndex]) minIndex = searchIndex; // Swap list[minIndex] and list[passCount] swap(list[minIndex], list[passCount]); } } //********************************************************** template void UnsortedList::swap(ItemType& first, ItemType& second) { ItemType temp; temp = first; first = second; second = temp;

} ////********************************************************** //template //void UnsortedList::insertionSort() //{ // ItemType temp; // int firstOutOfOrder; // the first index of the unsorted sublist // int location; // // for (firstOutOfOrder = 1; firstOutOfOrder < length; // firstOutOfOrder++) // { // if ( list[firstOutOfOrder] < list[firstOutOfOrder - 1] ) // { // temp = list[firstOutOfOrder]; // location = firstOutOfOrder; // // do // { // list[location] = list[location - 1]; // location--; // } while ( location > 0 && list[location - 1] > temp ); // // list[location] = temp; // } // } //} //********************************************************** template void UnsortedList::selectionSort() { int minIndex; // Index of minimum so far int i, j; for (i = 0; i < length - 1; i++) { for (j = i + 1, minIndex = i; j < length; j++) { if (list[j] < list[minIndex]) minIndex = j;

swap(list[minIndex], list[i]); } } } //********************************************************** template void UnsortedList::insertionSort() { ItemType tmp; int i; // the first index of the unsorted sublist int j; for (i = 1; i < length; i++) { tmp = list[i]; for (j = i; j > 0 && tmp < list[j - 1]; j--) list[j] = list[j - 1]; list[j] = tmp; } } //********************************************************** template void UnsortedList::bubbleSort() { int i, j; for (i = 0; i < length - 1; i++) { for (j = length - 1; j > i; j--) { if (list[j] < list[j - 1]) swap(list[j], list[j - 1]); } } } //********************************************************** template void UnsortedList::shellSort() { int i, j, hCount, h; int increments[20], k; ItemType tmp; // create an appropriate number of increments h for (h = 1, i = 0; h < length && i < 20; i++) {

increments[i] = h; h = 3 * h + 1; } // loop on the number of different increments h for (i--; i >= 0; i--) { h = increments[i]; // loop on the number of subarrays h-sorted in ith pass for (hCount = h; hCount < 2 * h; hCount++) { // insertion sort for subarray containing every hth // element of array data for (j = hCount; j < length;) { tmp = list[j]; k = j; while (k - h >= 0 && tmp < list[k - h]) { list[k] = list[k - h]; k -= h; } list[k] = tmp; j += h; } } } } //********************************************************** template void UnsortedList::quickSort() { recQuickSort(0, length - 1); } //********************************************************** template void UnsortedList::recQuickSort(int first, int last) { int pivotLocation; if (first < last) { pivotLocation = partition(first, last); recQuickSort(first, pivotLocation - 1); recQuickSort(pivotLocation + 1, last);

} } //********************************************************** template int UnsortedList::partition(int first, int last) { ItemType pivot; int index, smallIndex; swap(list[first], list[(first + last) / 2]); pivot = list[first]; smallIndex = first; for (index = first + 1; index <= last; index++) { if (list[index] < pivot) { smallIndex++; swap(list[smallIndex], list[index]); } } swap(list[first], list[smallIndex]); return smallIndex; } //********************************************************** template void UnsortedList::mergeSort() { recMergeSort(0, length - 1); } //********************************************************** template void UnsortedList::recMergeSort(int first, int last) { int mid; if (first < last) { mid = (first + last) / 2; recMergeSort(first, mid); recMergeSort(mid + 1, last); merge(first, mid, last); } } //**********************************************************

template void UnsortedList::merge(int first, int mid, int last) { ItemType * tmpArray; tmpArray = new ItemType[last - first + 1]; int i = first, j = mid + 1, k = 0; while (i <= mid && j <= last) { if (list[i] < list[j]) { tmpArray[k] = list[i]; i++; } else { tmpArray[k] = list[j]; j++; } k++; } if (i > mid) { for (int h = j; h <= last; h++) { tmpArray[k] = list[h]; k++; } } else { for (int h = i; h <= mid; h++) { tmpArray[k] = list[h]; k++; } } for (int i = first, k = 0; i <= last; i++) { list[i] = tmpArray[k]; k++; } delete [] tmpArray; } //********************************************************** template void UnsortedList::heapSort() { // create the heap

for (int i = length / 2 - 1; i >= 0; i--) // list[length/2-1] is the // last element in the list which is not a leaf heapify(i, length - 1); for (int i = length - 1; i >= 1; i--) { swap(list[0], list[i]); // move the largest item to list[i] heapify(0, i - 1); // restore the heap property } } //********************************************************** template void UnsortedList::heapify(int low, int high) { ItemType tmp = list[low]; // copy the root node of the tree int largeIndex = 2 * low + 1; // index of the left child while (largeIndex <= high) { if (largeIndex < high) { if (list[largeIndex] < list[largeIndex + 1]) largeIndex = largeIndex + 1; // index of the larger child } if (tmp > list[largeIndex]) // subtree is already in a heap break; else { list[low] = list[largeIndex]; // move the larger child to the root low = largeIndex; // go to the subtree to restore the heap largeIndex = 2 * low + 1; } }// end while list[low] = tmp; // insert tmp into the tree, that is, list } //********************************************************** template void sublist(const UnsortedList& list,const ItemType& item,UnsortedList& newList) { if(list.isEmpty()) return; else

All code should be in C++Using the UnsortedList class (UnsortedLis.pdf

More Related Content

Similar to All code should be in C++Using the UnsortedList class (UnsortedLis.pdf

More from akashenterprises93

Recently uploaded

All code should be in C++Using the UnsortedList class (UnsortedLis.pdf