Question

Simulate the performances of different sorting algorithms with randomly generated input data and measure their execution time.

Input:
Randomly generated positive integers (ranges from 0 to 100000). The numbers of input should be 1000, 5000, 10,000, 50,000 and 1000,000 which will be stored into one dimensional array. Each sorting algorithm will use the same input.

Algorithms:
• Insertion Sort
• Shellsort – For increment sequence, use sequence suggested by Shell hk = floor(hk+1/2).
• Heapsort - Use O(NlogN) algorithm
• Quicksort – Use Median-of-Three Partitioning.

Output:

Run each algorithm and print out the following results:

1. Print out the running time of algorithms for each input data and draw a graph for the running times..
2. Print out the number of swaps for each algorithm.

NOTE: If the run time of an algorithm is more than 10 mins, stop running of the algorithm.

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.

import java.util.Random;
import java.math.MathContext;;

public class SortCompare
{
public static long numberOfChanges;
    public static void insertionSort( int [ ] a )
    {
    int j;
    for( int p = 1; p < a.length; p++ )
    {
    int tmp = a[ p ];
    for( j = p; j > 0 && tmp < a[ j - 1 ] ; j-- )
    {
    a[ j ] = a[ j - 1 ];
    numberOfChanges++;
    }
    a[ j ] = tmp;
    numberOfChanges++;
    }
    }
   
    public static void shellSort( int [ ] a )
    {
    int j;

    for( int gap = a.length / 2; gap > 0; gap /= 2 )
    for( int i = gap; i < a.length; i++ )
    {
    int tmp = a[ i ];
    for( j = i; j >= gap && tmp < a[ j - gap ]; j -= gap )
    {
    a[ j ] = a[ j - gap ];
    numberOfChanges++;
    }
    a[ j ] = tmp;
    numberOfChanges++;
    }
    }...

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

Assisting Tutor

Related Homework Solutions

Computer Engineering Questions
Homework Solution
$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Address Enable Signal
Processors
States
Reading
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Dynamic Programming Model for A Version of Job Scheduling Problem
Homework Solution
$30.00
Knapsack
Reduction
Algorithm
Complexity
Problem
Job
Scheduling
Dynamic
Programming
OPT
Optimal
Swapping
Exchange
Argument
Playful
Subset
Deadline
Value
Size
Profit
Function
Solution
Set
Array
Two
Dimensional
Selection
Reorder
M
Get help from a qualified tutor
Live Chats