diff options
Diffstat (limited to 'chapter13')
| -rw-r--r-- | chapter13/heapsort.cxx | 166 | ||||
| -rw-r--r-- | chapter13/merge.cxx | 122 | ||||
| -rw-r--r-- | chapter13/quick.cxx | 107 | ||||
| -rw-r--r-- | chapter13/select.cxx | 71 |
4 files changed, 466 insertions, 0 deletions
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 <algorithm> // Provides swap
+#include <cstdlib> // Provides EXIT_SUCCESS, size_t
+#include <iostream> // 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 <cstdlib> // Provides EXIT_SUCCESS, size_t
+#include <iostream> // 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 <algorithm> // Provides swap
+#include <cstdlib> // Provides EXIT_SUCCESS, size_t
+#include <iostream> // 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 <algorithm> // Provides swap
+#include <cstdlib> // Provides EXIT_SUCCESS, size_t
+#include <iostream> // 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]);
+ }
+}
|