 # Sorting Algorithms in Java

Subject Computer Science Data Structures and Algorithms

## 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

## Related Homework Solutions

Fibonacci Dynamic Programming Questions \$8.00
Fibonacci
Dynamic
Programming
Question
Pseudo
Code
Algorithm
DP
Optimal
Subproblem
Algorithm Analysis, Correctness and Sorted Linked List Algorithm \$10.00
Algorithm
List
Loop
Invariant
Worst
Case
Analysis
Complexity
Correctness
Ascending
Initialization
Maintenance
Termination
Computer Engineering Questions \$4.00
Computer Science
Engineering
Intel 8086
Systems
DRAM Memory
RAS
Processors
States
Writing
Propagation
Data Paths
Time Requirements
Clocking Rate
Access Time
Minimum Spanning Tree Update Question in a Connected Graph \$5.00
MST
Minimum
Spanning
Tree
Connected
Undirected
Graph
Weight
Edge
O(V+E)
Algorithm
Increased
Modification
Algorithm Design Tracing Using Pseudocode, Desk Check & Desk Checking Table Features \$28.00
Transaction
Commission
Retail Price
Employee
Algorithm Design
Pseudocode
Desk Check
Desk Checking
Expected Results
Record
Item
Sold
Dynamic Programming Model for A Version of Job Scheduling Problem \$30.00
Knapsack
Reduction
Algorithm
Complexity
Problem
Job
Scheduling
Dynamic
Programming
OPT
Optimal
Swapping
Exchange
Argument
Playful
Subset