The purpose of this lab is to help reinforce sorting algorithms implementations in C++. You need download Sorting project from course website.
1. Merge Sort:
Do the programming problems 6 on page 681 of the text.
// 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, int temp[ ]);
// 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, int temp[ ]);
// Precondition: data[first_index] through
// data[last_index] are array elements in no
// particular order. The temp array has
// locations temp[first_index] through
// temp[last_index].
// Postcondition: The elements
// data[first_index] through data[last_index]
// have been rearranged so that they are
// ordered from smallest to largest. The array
// elements temp[first_index] through
// temp[last_index] have been used as
// temporary storage and now contain a
// copy of data[first_index] through
// data[last_index].
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 temp[ARRAY_SIZE];
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, temp);
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;
}
2. Quick Sort:
Implement partition function for the quick sort (quick.cpp).
// 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;
}
3. Do the programming problem 13 on page 682 of the text.
Write testing program to test the implemented functions.
#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 shellsort(int data[], int 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( )
{
}