# Hybrid Sorting

Write a C++ program that implements both insertion sort and quicksort for sorting arrays of n integers. Test your program (both sorts) by generating random arrays as follows: for i from 0 to n-1, assign the number i to A[i]. Then for i from 0 to n-1, swap A[i] with A[Random(i,n-1)], where Random(a,b) returns a random integer between a and b inclusive. When compiled, the program should generate a random array of length n, print the array, then print the sorted array (sorted by both sort routines). Turn in the output for arrays of length 10. Find (by experimentation) approximately for what value of n quicksort becomes more efficient than insertion sort. Implement a hybrid sorting algorithm as follows: use quicksort until the subarrays are of size k or less, and then finish off with insertion sort. Experiment to determine a good value for k. For this part, write up your conclusions along with the experimental results (at most 1 page). Explain how you did the experiments. You should not base a comparison on single runs. You should average over many (say 100) independent runs. You might generate and sort 100 random arrays, keeping track of the (wall clock) time, then compute the average time for a sort. Doing this for different values of n will give you a good idea of the average performance.

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

## Platform

Visual Studio 6.0 or Visual Net