From c1b6ffe70bd281c6c230fd63fabcaac2aff47514 Mon Sep 17 00:00:00 2001 From: Fuwn Date: Sun, 7 Apr 2024 23:18:32 -0700 Subject: feat: initial commit --- chapter13/heapsort.cxx | 166 +++++++++++++++++++++++++++++++++++++++++++++++++ chapter13/merge.cxx | 122 ++++++++++++++++++++++++++++++++++++ chapter13/quick.cxx | 107 +++++++++++++++++++++++++++++++ chapter13/select.cxx | 71 +++++++++++++++++++++ 4 files changed, 466 insertions(+) create mode 100644 chapter13/heapsort.cxx create mode 100644 chapter13/merge.cxx create mode 100644 chapter13/quick.cxx create mode 100644 chapter13/select.cxx (limited to 'chapter13') diff --git a/chapter13/heapsort.cxx b/chapter13/heapsort.cxx new file mode 100644 index 0000000..7c44599 --- /dev/null +++ b/chapter13/heapsort.cxx @@ -0,0 +1,166 @@ +// FILE: heapsort.cxx +// An interactive test program for the selectionsort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void heapsort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. + +size_t parent(size_t k); +// Precondition: k> 0. +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the parent of node k, using +// the formula from rule 3 on page 624. + +size_t left_child(size_t k); +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the left child of node k, +// using the formula from rule 2 on page 624. + +size_t right_child(size_t k); +// Postcondition: The function assumes that k is the index of an array element, where the array +// represents a complete binary tree. The return value is the index of the right child of node k, +// using the formula from rule 2 on page 624. + +void make_heap(int data[ ], size_t n); +// Precondition: data is an array with at least n elements. +// Postcondition: The elements of data have been rearranged so that the +// complete binary tree represented by this array is a heap. + +void reheapify_down(int data[ ], size_t n); +// Precondition: n > 0, and data is an array with at least n elements. These elements form a +// heap **except** that data[0] may be in an incorrect location. +// location. +// Postcondition: The data values have been rearranged so that the first n elements of data now +// form a heap. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + ++number_of_elements; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + heapsort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; ++i) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void heapsort(int data[ ], size_t n) +// Library facilities used: algorithm, cstdlib +{ + size_t unsorted; + + make_heap(data, n); + + unsorted = n; + + while (unsorted > 1) + { + --unsorted; + swap(data[0], data[unsorted]); + reheapify_down(data, unsorted); + } +} + +size_t parent(size_t k) +// Library facilities used: cstdlib +{ + return (k-1)/2; +} + +size_t left_child(size_t k) +// Library facilities used: cstdlib +{ + return 2*k + 1; +} + +size_t right_child(size_t k) +// Library facilities used: cstdlib +{ + return 2*k + 2; +} + +void make_heap(int data[ ], size_t n) +// Library facilities used: itemtool.h (from page 277), cstdlib +// +{ + size_t i; // Index of next element to be added to heap + size_t k; // Index of new element as it is being pushed upward through the heap + + for (i = 1; i < n; ++i) + { + k = i; + while ((k > 0) && (data[k] > data[parent(k)])) + { + swap(data[k], data[parent(k)]); + k = parent(k); + } + } +} + +void reheapify_down(int data[ ], size_t n) +// Library facilities used: itemtool.h (from page 277), cstdlib +{ + size_t current; // Index of the node that's moving down + size_t big_child_index; // Index of the larger child of the node that's moving down + bool heap_ok = false; // Will change to true when the heap becomes correct + + current = 0; + + // Note: The loop keeps going while the heap is not okay, and while the current node has + // at least a left child. The test to see whether the current node has a left child is + // left_child(current) < n. + while ((!heap_ok) && (left_child(current) < n)) + { + // Compute the index of the larger child: + if (right_child(current) >= n) + // There is no right child, so left child must be largest + big_child_index = left_child(current); + else if (data[left_child(current)] > data[right_child(current)]) + // The left child is the bigger of the two children + big_child_index = left_child(current); + else + // The right child is the bigger of the two children + big_child_index = right_child(current); + + // Check whether the larger child is bigger than the current node. If so, then swap + // the current node with its bigger child and continue; otherwise we are finished. + if (data[current] < data[big_child_index]) + { + swap(data[current], data[big_child_index]); + current = big_child_index; + } + else + heap_ok = true; + } +} + diff --git a/chapter13/merge.cxx b/chapter13/merge.cxx new file mode 100644 index 0000000..0d53978 --- /dev/null +++ b/chapter13/merge.cxx @@ -0,0 +1,122 @@ +// FILE: merge.cxx +// An interactive test program for the mergesort function + +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void mergesort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. +// NOTE: If there is insufficient dynamic memory, then new_handler is called. + +void merge(int data[ ], size_t n1, size_t n2); +// Precondition: data is an array (or subarray) with at least n1+n2 elements. +// The first n1 elements (from data[0] to data[n1-1]) are sorted from smallest +// to largest, and the last n2 (from data[n1] to data[n1+n2-1]) are also +// sorted from smallest to largest. +// Postcondition: The first n1+n2 elements of data have been +// rearranged to be sorted from smallest to largest. +// NOTE: If there is insufficient dynamic memory, then new_handler is called. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + mergesort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void mergesort(int data[ ], size_t n) +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. +// NOTE: If there is insufficient dynamic memory, thenbad_alloc is thrown. +// Library facilities used: cstdlib +{ + size_t n1; // Size of the first subarray + size_t n2; // Size of the second subarray + + if (n > 1) + { + // Compute sizes of the subarrays. + n1 = n / 2; + n2 = n - n1; + + mergesort(data, n1); // Sort from data[0] through data[n1-1] + mergesort((data + n1), n2); // Sort from data[n1] to the end + + // Merge the two sorted halves. + merge(data, n1, n2); + } +} + +void merge(int data[ ], size_t n1, size_t n2) +// Precondition: data is an array (or subarray) with at least n1 + n2 elements. +// The first n1 elements (from data[0] to data[n1 - 1]) are sorted from +// smallest to largest, and the last n2 (from data[n1] to data[n1 + n2 - 1]) +// also are sorted from smallest to largest. +// Postcondition: The first n1 + n2 elements of data have been rearranged to be +// sorted from smallest to largest. +// NOTE: If there is insufficient dynamic memory, then bad_alloc is thrown. +// Library facilities used: cstdlib +{ + int *temp; // Points to dynamic array to hold the sorted elements + size_t copied = 0; // Number of elements copied from data to temp + size_t copied1 = 0; // Number copied from the first half of data + size_t copied2 = 0; // Number copied from the second half of data + size_t i; // Array index to copy from temp back into data + + // Allocate memory for the temporary dynamic array. + temp = new int[n1+n2]; + + // Merge elements, copying from two halves of data to the temporary array. + while ((copied1 < n1) && (copied2 < n2)) + { + if (data[copied1] < (data + n1)[copied2]) + temp[copied++] = data[copied1++]; // Copy from first half + else + temp[copied++] = (data + n1)[copied2++]; // Copy from second half + } + + // Copy any remaining entries in the left and right subarrays. + while (copied1 < n1) + temp[copied++] = data[copied1++]; + while (copied2 < n2) + temp[copied++] = (data+n1)[copied2++]; + + // Copy from temp back to the data array, and release temp's memory. + for (i = 0; i < n1+n2; i++) + data[i] = temp[i]; + delete [ ] temp; +} + + diff --git a/chapter13/quick.cxx b/chapter13/quick.cxx new file mode 100644 index 0000000..4a978a3 --- /dev/null +++ b/chapter13/quick.cxx @@ -0,0 +1,107 @@ +// FILE: quick.cxx +// An interactive test program for the quicksort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPES of the functions used in this test program: +void quicksort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements of data have been rearranged so +// that data[0] <= data[1] <= ... <= data[n-1]. + +void partition(int data[ ], size_t n, size_t& pivot_index); +// Precondition: n > 1, and data is an array (or subarray) +// with at least n elements. +// Postcondition: The function has selected some "pivot value" +// that occurs in data[0]..data[n-1]. The elements of data +// have then been rearranged, and the pivot index set so that: +// -- data[pivot_index] is equal to the pivot; +// -- Each item before data[pivot_index] is <= the pivot; +// -- Each item after data[pivot_index] is >= the pivot. + + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions + cout << "Please type up to " << ARRAY_SIZE << " positive integers."; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers and print the result with two blanks after each number + quicksort(data, number_of_elements); + cout << "In sorted order, your numbers are: " << endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void quicksort(int data[ ], size_t n) +// Library facilities used: cstdlib +{ + size_t pivot_index; // Array index for the pivot element + size_t n1; // Number of elements before the pivot element + size_t n2; // Number of elements after the pivot element + + if (n > 1) + { + // Partition the array, and set the pivot index. + partition(data, n, pivot_index); + + // Compute the sizes of the subarrays. + n1 = pivot_index; + n2 = n - n1 - 1; + + // Recursive calls will now sort the subarrays. + quicksort(data, n1); + quicksort((data + pivot_index + 1), n2); + } +} + +void partition(int data[ ], size_t n, size_t& pivot_index) +// Library facilities used: itemtool.h, stdlib.h +// +// NOTES FROM THE IMPLEMENTOR: +// How the partition works on small arrays: +// +// Notice that n=0 is not permitted by the precondition. +// +// If n=1, then too_big_index is initialized as 1, and too_small_index is +// initialized as 0. Therefore, the body of the loop is never executed, +// and after the loop pivot_index is set to zero. +// +// If n=2, then both too_big_index and too_small_index are initialized as 1. +// The loop is entered, and there are two cases to consider: +// -- if data[1] <= pivot, then too_big_index increases to 2, and +// too_small_index stays at 1. The if-statement at the bottom of the loop +// is then skipped, and after the loop we copy data[1] down to data[0], +// and copy the pivot into data[0]. Thus, the smaller element is in +// data[0], and the larger element (the pivot) is in data[1]. +// -- if data[1] > pivot, then too_big_index stays at 1, and too_small_index +// decreases to 0. The if-statement at the bottom of the loop is then +// skipped, and after the loop we end up copying the pivot onto data[0] +// (leaving data[1] alone). Thus, the smaller element (the pivot) remains +// at data[0], leaving the larger element at data[1]. +{ + -- Implementation is left to the student +} diff --git a/chapter13/select.cxx b/chapter13/select.cxx new file mode 100644 index 0000000..44514e9 --- /dev/null +++ b/chapter13/select.cxx @@ -0,0 +1,71 @@ +// FILE: select.cxx +// An interactive test program for the selectionsort function + +#include // Provides swap +#include // Provides EXIT_SUCCESS, size_t +#include // Provides cout and cin +using namespace std; + +// PROTOTYPE of the function used in this test program: +void selectionsort(int data[ ], size_t n); +// Precondition: data is an array with at least n components. +// Postcondition: The elements are rearranged so that +// data[0] <= data[1] <= ... <= data[n-1]. + +int main( ) +{ + const char BLANK = ' '; + const size_t ARRAY_SIZE = 10; // Number of elements in the array to be sorted + int data[ARRAY_SIZE]; // Array of integers to be sorted + int user_input; // Number typed by the user + size_t number_of_elements; // How much of the array is used + size_t i; // Array index + + // Provide some instructions. + cout << "Please type up to " << ARRAY_SIZE << " positive integers. "; + cout << "Indicate the list's end with a zero." << endl; + + // Read the input numbers. + number_of_elements = 0; + cin >> user_input; + while ((user_input != 0) && (number_of_elements < ARRAY_SIZE)) + { + data[number_of_elements] = user_input; + number_of_elements++; + cin >> user_input; + } + + // Sort the numbers, and print the result with two blanks after each number. + selectionsort(data, number_of_elements); + cout << "In sorted order, your numbers are: "<< endl; + for (i = 0; i < number_of_elements; i++) + cout << data[i] << BLANK << BLANK; + cout << endl; + + return EXIT_SUCCESS; +} + +void selectionsort(int data[ ], size_t n) +// Library facilities used: algorithm, cstdlib +{ + size_t i, j, index_of_largest; + int largest; + + if (n == 0) + return; // No work for an empty array. + + for (i = n-1; i > 0; --i) + { + largest = data[0]; + index_of_largest = 0; + for (j = 1; j <= i; ++j) + { + if (data[j] > largest) + { + largest = data[j]; + index_of_largest = j; + } + } + swap(data[i], data[index_of_largest]); + } +} -- cgit v1.2.3