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

Dynamic Data Structures in C
Homework Solution
$30.00
C-Family
Programming
Computer Science
Dynamic Structures
ASCII Codes
Text Files
Numbers
Lists
Trees
Allocated Memory
Input
Output
Pointers
Statements
Variables
Associative Arrays in C++
Homework Solution
$75.00
Programming
C++
Associative Arrays
Computer Science
Hash Tables
Chaining
Static Arrays
Game of Life
Records
Strings
Integers
Objects
Functions
Copying
Applet
Sequences
Lists
Prime Numbers
Simulations
An Electrodialysis Machine
Homework Solution
$15.00
Electrodialysis
Machine
Computer
Science
C-Family
Programming
Filter
Impurities
Water
Current
Experiment
Attributes & Methods in C++
Homework Solution
$10.00
Programming
C++
Computer Science
Attributes
Methods
Students
People
Inheritance
Employees
Salaries
Job Titles
Classes
Statements
Variables
Restaurant Waitlist Using C++
Homework Solution
$13.00
Programming
C++
Computer Science
Linked Lists
Queue
People
Restaurant Waitlist
Guests
Reservations
Statements
Variables
Data Sets
Constructors
Pointers
Search
Input
Output
Get help from a qualified tutor
Live Chats