Question

The running time of quicksort can be improved in practice by taking advantage of the fast running time of insertion sort when its input is ”nearly” sorted. When quicksort is called on a subarray with fewer than k elements, let it simply return without sorting the subarray. After the top-level call to quicksort returns, run insertion sort on the entire array to finish the sorting process. Argue that this sorting algorithm runs in O(nk + n log(n/k)) expected time. How should k be picked, both in theory and in practice ?

Sorting Algorithms
The goal here is a comparative experimental study, in terms of running time, of the following sorting algorithms.
• Insertion sort.
• Mergesort.
• Quicksort.
• Quicksort as shown in exercise above (we will call this algorithm Quick-insertion).

1. Implement these algorithms above within the same program. The input and output are described as follows.
Input: 2 parameters N (number of random naturals to sort) and K (used by Quick-insertion).
Output: Display the list of N randomly generated naturals. For each algorithm display the list of sorted numbers + corresponding running time.

2. Find the pair of values (N, K) where :
(a) Quick-insertion outperforms all the other algorithms.
(b) Insertion sort outperforms all the other algorithms.
(c) Quicksort outperforms all the other algorithms.

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

void insertionSort(int data[], int n) //Simple insertion sort
{
    for(int i = 1; i < n; i++)
    {
   int j = i;
   while(j > 0 && data[j-1] > data[j])
   {
int temp = data[j];
data[j] = data[j-1];
data[j-1] = temp;
j = j-1;
   }
    }
}

void mergeSort(int data[], int n)
{
    vector<int> dataList; //Used vectors because they're easier to deal with than making several small array
    dataList.reserve(n); //Reserve spots to reduce time usage
    for(int i = 0;i < n; i++) //Move array into vector
   dataList.push_back(data[i]);
    dataList = mergeSortRecursive(dataList); //Run recursive method
    for(int i = 0; i < n; i++) //put resulting data vector back into original array
   data[i] = dataList[i];
}...

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

An Electrodialysis Machine
Homework Solution
$15.00
Electrodialysis
Machine
Computer
Science
C-Family
Programming
Filter
Impurities
Water
Current
Experiment
Parsing Line Input in C++
Homework Solution
$28.00
Programming
Computer Science
C++
Classes
ASCII Files
Individual Words
Arrays
Reverse Order
OOP
Functions
Algorithms
Parsing Lines
Strings
Loops
Output
Memory Leaks
One Line Object
C-Programming Questions
Homework Solution
$80.00
Computer Science
Programming
C-Programming
GPA Calculator
Grades
Battle Fleet Game
Rules
Players
Ships
Ocean
Enemies
Computer Mode
Player Mode
Skills
Grids
Axes
Slot Machine
Gambling Industry
Payoffs
Winners
Percentage
Do-While Loop For a Ticket-Taker Problem
Homework Solution
$15.00
Programming
Computer Science
C++
Ticket-Taker
Prices
Do-While Loop
Discounts
Children
Constant Values
Integers
Sales
Messages
Input
Output
Get help from a qualified tutor
Live Chats