C++ Program 10 and In Class
theman04
c_program_10_and_in_class.zipC++ Program 10 and In Class/Almost.txt
8 2 3 5 4 6 7 1 9 10 11 12 13 64 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 38 39 40 41 42 43 44 33 34 35 36 37 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 14 65 66 67 68 69 70 71 72 73 74 75 81 76 77 78 79 80 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
C++ Program 10 and In Class/Bubble Sort.txt
/************************************************************/ /* This program demonstrates a bubble sort algorithm */ /* to sort an unordered list read in from a data file */ /* Author: T. Klingler */ /************************************************************/ #include <iostream> #include <fstream> using namespace std; const int MAX_LIST_SIZE = 100; // Max list size // (for array declaration) // Function prototypes void GetList(int inList[],int& listsize,int maxlistsize); void sortArray(int array[], int elems); void DisplayList(int theList[],int listsize); int main() { int InList[MAX_LIST_SIZE]; // Array of list elements int ListSize; // Index of last list element GetList(InList,ListSize,MAX_LIST_SIZE); // Write list prior to sort cout << endl << "BEFORE" << endl; DisplayList(InList,ListSize); sortArray(InList,ListSize); // Write list after sort cout << endl << "AFTER" << endl; DisplayList(InList,ListSize); return 0; } /************************************************************/ /* This function opens a file to retrieve a list of values */ /* of a generic type. Values are stored in an array and */ /* passed to the calling routine. */ /* Parameters: */ /* list array of integers to build */ /* listsize number of elements in list) */ /* maxlistsize max size allowable for list array */ /* Requires: */ /* Global type definition of int */ /************************************************************/ void GetList(int inList[],int& listsize,int maxlistsize) { ifstream InFile ("listData.txt"); int i = 0; InFile >> inList[i]; while( !InFile.eof() && i < maxlistsize) { i++; InFile >> inList[i]; } listsize = i; // Size of list is lastindex + 1 } /************************************************************/ /* This function writes a list to console output: one list */ /* item at a time. */ /************************************************************/ void DisplayList(int theList[],int listsize) { for (int i = 0;i < listsize; i++) cout << theList[i] << " "; cout << endl; } /************************************************************/ /* This function receives a list of values of type int */ /* as an array. The function performs a bubble sort and */ /* returns the list in ascending order. */ /* Note: elems is number of elements in list */ /************************************************************/ void sortArray(int array[], int elems) { int temp, end; for (end = elems - 1; end >= 0; end--) { for (int count = 0; count < end; count++) { if (array[count] > array[count + 1]) { temp = array[count]; array[count] = array[count + 1]; array[count + 1] = temp; } } } }
C++ Program 10 and In Class/Bubble Sort2.txt
#include <iostream> #include <fstream> using namespace std; const int MAX_LIST_SIZE = 100; // Max list size // (for array declaration) // Function prototypes void GetList(int inList[],int& listsize,int maxlistsize); void sortArray(int Array[], int Elems); void DisplayList(int theList[],int listsize); int main() { int InList[MAX_LIST_SIZE]; // Array of list elements int ListSize; // Index of last list element GetList(InList,ListSize,MAX_LIST_SIZE); // Write list prior to sort cout << endl << "BEFORE" << endl; DisplayList(InList,ListSize); sortArray(InList,ListSize); // Write list after sort cout << endl << "AFTER" << endl; DisplayList(InList,ListSize); return 0; } /************************************************************/ /* This function opens a file to retrieve a list of values */ /* of a generic type. Values are stored in an array and */ /* passed to the calling routine. */ /* Parameters: */ /* list array of integers to build */ /* listsize number of elements in list) */ /* maxlistsize max size allowable for list array */ /* Requires: */ /* Global type definition of int */ /************************************************************/ void GetList(int inList[],int& listsize,int maxlistsize) { ifstream InFile ("listData.txt"); int i = 0; InFile >> inList[i]; while( !InFile.eof() && i < maxlistsize) { i++; InFile >> inList[i]; } listsize = i; // Size of list is lastindex + 1 } /************************************************************/ /* This function writes a list to console output: one list */ /* item at a time. */ /************************************************************/ void DisplayList(int theList[],int listsize) { for (int i = 0;i < listsize; i++) cout << theList[i] << " "; cout << endl; } /************************************************************/ /* This function receives a list of values of type int */ /* as an array. The function performs a bubble sort and */ /* returns the list in ascending order. The sorting is */ /* halted if no swaps are made in any given pass. */ /* Note: elems is number of elements in list */ /************************************************************/ void sortArray(int array[], int elems) { bool swap; int temp; int end = elems - 1; // To control stopping point do { swap = false; // Assume no swap this pass for (int count = 0; count < end; count++) { if (array[count] > array[count + 1]) { temp = array[count]; array[count] = array[count + 1]; array[count + 1] = temp; swap = true; // Mark that swap occured } } end--; // Move stopping point up // Continue if a swap occurred that pass } while (swap); }
C++ Program 10 and In Class/Heap Sort Example.txt
// This program demonstrates the HeapSort algorithm on a list // of integers #include <fstream> #include <iostream> using namespace std; #include "heapSort.cpp" // Function prototypes void GetList(int[],int&,int); void DisplayList(int[],int); const int MAX_LIST_SIZE = 100; // Max list size // (for array declaration) int main() { int InList[MAX_LIST_SIZE]; // Array of list elements int ListSize; // Index of last list element GetList(InList,ListSize,MAX_LIST_SIZE); // Write list prior to sort cout << endl << "BEFORE" << endl; DisplayList(InList,ListSize); HeapSort(InList,ListSize); // Write list after sort cout << endl << "AFTER" << endl; DisplayList(InList,ListSize); return 0; } /************************************************************/ /* This function opens a file to retrieve a list of integer */ /* values. Values are stored in an array and passed to the */ /* calling routine. */ /************************************************************/ void GetList(int inList[],int& listsize,int maxlistsize) { ifstream InFile ("listData.txt"); int ListElement; int i = 0; InFile >> ListElement; while(InFile && i < maxlistsize) { inList[i] = ListElement; i++; InFile >> ListElement; } listsize = i; // Size of list } /************************************************************/ /* This function writes a list to console output: one list */ /* item at a time. */ /************************************************************/ void DisplayList(int theList[],int listsize) { for (int i = 0;i < listsize; i++) cout << theList[i] << ' '; cout << endl; }
C++ Program 10 and In Class/Heap Sort Files.txt
// This file include the functions to implement Heap Sort. // This is a generic function to swap values of any data type template<class ItemType> inline void Swap(ItemType& item1, ItemType& item2) { ItemType tempItem; tempItem = item1; item1 = item2; item2 = tempItem; } // This function drives the heapsort algorthm by: // 1) converting any array into a heap pattern // 2) swapping and reheaping array to perform sort template<class ItemType> inline void HeapSort(ItemType values[], int numValues) { int index; // Convert the array of values into a heap for (index = numValues/2 - 1; index >= 0; index--) ReheapDown(values, index, numValues-1); // Sort the array for (index = numValues-1; index >=1; index--) { Swap(values[0], values[index]); ReheapDown(values, 0, index-1); } } // This function includes only the action to reheap down // to restore a heap from the top-down template<class ItemType> void ReheapDown(ItemType elements[], int root, int bottom) // Post: Heap property is restored. { int maxChild; int rightChild; int leftChild; leftChild = root * 2 + 1; rightChild = root * 2 + 2; if (leftChild <= bottom) { if (leftChild == bottom) maxChild = leftChild; else { if (elements[leftChild] <= elements[rightChild]) maxChild = rightChild; else maxChild = leftChild; } if (elements[root] < elements[maxChild]) { Swap(elements[root], elements[maxChild]); ReheapDown(elements, maxChild, bottom); } } }
C++ Program 10 and In Class/InClassAssignment.pdf
CST 280 In-Class Practice – Week 14 Part 1: Write the adjacency matrix for this directed graph Part 2.1: With root node C, list:
a) the sequence of nodes for a depth-first search b) the sequence of nodes for a breadth-first search
A
C
D
E B
A A
B
B
C
C
D
D
E
E 25
30
8 10
6 4 7
3
D
C
A
B E G F
H
J K
M
C++ Program 10 and In Class/Inverse.txt
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
C++ Program 10 and In Class/QuickSort.txt
// This program demonstrates the QuickSort Algorithm #include <iostream> using namespace std; // Function prototypes void quickSort(int [], int, int); int partition(int [], int, int); void swap(int &, int &); int main() { int array[10] = {7, 3, 9, 2, 0, 1, 8, 4, 6, 5}; int x; // Counter for (x = 0; x < 10; x++) cout << array[x] << " "; cout << endl; quickSort(array, 0, 9); for (x = 0; x < 10; x++) cout << array[x] << " "; cout << endl; return 0; } //************************************************ // quickSort uses the quicksort algorithm to * // sort set, from set[start] through set[end]. * //************************************************ void quickSort(int set[], int start, int end) { int pivotPoint; if (start < end) { // Get the pivot point pivotPoint = partition(set, start, end); // Sort the first sub list quickSort(set, start, pivotPoint - 1); // Sort the second sub list quickSort(set, pivotPoint + 1, end); } } //********************************************************** // partition selects the value in the middle of the * // array set as the pivot. The list is rearranged so * // all the values less than the pivot are on its left * // and all the values greater than pivot are on its right. * //********************************************************** int partition(int set[], int start, int end) { int pivotValue, pivotIndex, mid; mid = (start + end) / 2; swap(set[start], set[mid]); pivotIndex = start; pivotValue = set[start]; for (int scan = start + 1; scan <= end; scan++) { if (set[scan] < pivotValue) { pivotIndex++; swap(set[pivotIndex], set[scan]); } } swap(set[start], set[pivotIndex]); return pivotIndex; } //********************************************** // swap simply exchanges the contents of * // value1 and value2. * //********************************************** void swap(int &value1, int &value2) { int temp = value1; value1 = value2; value2 = temp; }
C++ Program 10 and In Class/Random.txt
33 89 11 70 96 18 12 94 59 80 29 95 87 72 5 8 19 67 31 99 42 65 9 16 75 46 27 48 23 44 57 68 41 88 10 49 64 3 78 100 24 6 22 50 52 32 4 51 20 74 40 92 77 2 66 85 26 58 43 82 86 73 71 53 62 37 55 83 84 25 7 15 28 38 47 61 81 56 60 45 54 35 36 93 79 39 90 63 17 21 13 91 34 97 98 1 30 76 14 69
C++ Program 10 and In Class/Selection Sort.txt
// This program uses the selection sort algorithm to sort an // array in ascending order. #include <iostream> using namespace std; // Function prototypes void selectionSort(int array[], int elems); void showArray(int array[], int elems); int main(void) { int arraySize = 6; int values[] = {5, 7, 2, 8, 9, 1}; // Hardcoded initialized array // Display unsorted list cout << "The unsorted values are\n"; showArray(values, arraySize); // Sort values selectionSort(values, arraySize); // Display sorted list cout << "The sorted values are\n"; showArray(values, arraySize); return 0; } //************************************************************** // Definition of function selectionSort. * // This function performs an ascending order selection sort on * // array. elems is the number of elements in the array. * //************************************************************** void selectionSort(int array[], int elems) { int startScan, minIndex, minValue; for (startScan = 0; startScan < (elems - 1); startScan++) { minIndex = startScan; minValue = array[startScan]; for(int index = startScan + 1; index < elems; index++) { if (array[index] < minValue) { minValue = array[index]; minIndex = index; } } array[minIndex] = array[startScan]; array[startScan] = minValue; } } //************************************************************** // Definition of function showArray. * // This function displays the contents of array. elems is the * // number of elements. * //************************************************************** void showArray(int array[], int elems) { for (int count = 0; count < elems; count++) cout << array[count] << " "; cout << endl; }
