Homework SourseWrite a java program to randomly generate the following sets
Write a java program to randomly generate the following sets of data:
1.) 10 numbers
2.) 1,000 numbers
3.) 100,000 numbers
4.) 1,000,000 numbers
5.) 10,000,000 numbers
Your program must sort the above sets of numbers using the following algorithms:
1.) Insertion Sort
2.) Merge Sort
3.) Quick Sort
4.) Heap Sort
Print out the time each algorithm takes to sort the above numbers
Solution
import java.util.Random;
public class Sort {
private int[] array;
private int size ;
public Sort(int n){
array = new int[n];
size = n;
Random rand = new Random();
for (int i = 0 ; i < n ; i++ ) {
array[i] = rand.nextInt(100000) ;
}
}
public void print(){
for (int i = 0; i < size ; i++ ) {
System.out.print(array[i] + \" \");
}
System.out.println(\"\");
}
void insertion_sort()
{
for (int i=1; i<size; ++i)
{
int key = array[i];
int j = i-1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j>=0 && array[j] > key)
{
array[j+1] = array[j];
j = j-1;
}
array[j+1] = key;
}
}
void merge(int arr[], int l, int m, int r)
{
// Find sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = arr[l + i];
for (int j=0; j<n2; ++j)
R[j] = arr[m + 1+ j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarry array
int k = l;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of L[] if any */
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Main function that sorts arr[l..r] using
// merge()
void merge_sort(int l, int r)
{
if (l < r)
{
// Find the middle point
int m = (l+r)/2;
// Sort first and second halves
merge_sort(l, m);
merge_sort(m+1, r);
// Merge the sorted halves
merge(array, l, m, r);
}
}
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<=high-1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
array[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quick_sort(int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(array, low, high);
// Recursively sort elements before
// partition and after partition
quick_sort(low, pi-1);
quick_sort(pi+1, high);
}
}
public void heap_sort()
{
int n = array.length;
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(array, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
int temp = array[0];
array[0] = array[i];
array[i] = temp;
// call max heapify on the reduced heap
heapify(array, i, 0);
}
}
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
Sort sort1 = new Sort(10);
long start = System.currentTimeMillis();
sort1.insertion_sort();
long time = System.currentTimeMillis() - start;
//sort1.print();
System.out.println(\"insertion_sort for 10 numbers take \" + time + \" ms \");
sort1 = new Sort(10);
start = System.currentTimeMillis();
sort1.merge_sort(0,9);
time = System.currentTimeMillis() - start;
//sort1.print();
System.out.println(\"merge_sort for 10 numbers take \" + time + \" ms \");
sort1 = new Sort(10);
start = System.currentTimeMillis();
sort1.quick_sort(0,9);
time = System.currentTimeMillis() - start;
//sort1.print();
System.out.println(\"quick_sort for 10 numbers take \" + time + \" ms \");
sort1 = new Sort(10);
start = System.currentTimeMillis();
sort1.heap_sort();
time = System.currentTimeMillis() - start;
//sort1.print();
System.out.println(\"heap_sort for 10 numbers take \" + time + \" ms \");
////////////////////////////////////////////////////////////////////////
System.out.println(\"\");System.out.println(\"\");
sort1 = new Sort(1000);
start = System.currentTimeMillis();
sort1.insertion_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"insertion_sort for 1000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000);
start = System.currentTimeMillis();
sort1.merge_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"merge_sort for 1000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000);
start = System.currentTimeMillis();
sort1.quick_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"quick_sort for 1000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000);
start = System.currentTimeMillis();
sort1.heap_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"heap_sort for 1000 numbers take \" + time + \" ms \");
////////////////////////////////////////////////////////////////////////
System.out.println(\"\");System.out.println(\"\");
sort1 = new Sort(100000);
start = System.currentTimeMillis();
sort1.insertion_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"insertion_sort for 100000 numbers take \" + time + \" ms \");
sort1 = new Sort(100000);
start = System.currentTimeMillis();
sort1.merge_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"merge_sort for 100000 numbers take \" + time + \" ms \");
sort1 = new Sort(100000);
start = System.currentTimeMillis();
sort1.quick_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"quick_sort for 100000 numbers take \" + time + \" ms \");
sort1 = new Sort(100000);
start = System.currentTimeMillis();
sort1.heap_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"heap sort for 100000 numbers take \" + time + \" ms \");
////////////////////////////////////////////////////////////////////////
System.out.println(\"\");System.out.println(\"\");
sort1 = new Sort(1000000);
start = System.currentTimeMillis();
sort1.insertion_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"insertion_sort for 1000000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000000);
start = System.currentTimeMillis();
sort1.merge_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"merge_sort for 1000000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000000);
start = System.currentTimeMillis();
sort1.quick_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"quick_sort for 1000000 numbers take \" + time + \" ms \");
sort1 = new Sort(1000000);
start = System.currentTimeMillis();
sort1.heap_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"heap_sort for 1000000 numbers take \" + time + \" ms \");
////////////////////////////////////////////////////////////////////////
System.out.println(\"\");System.out.println(\"\");
sort1 = new Sort(10000000);
start = System.currentTimeMillis();
sort1.insertion_sort();
time = System.currentTimeMillis() - start;
System.out.println(\"insertion_sort for 10000000 numbers take \" + time + \" ms \");
sort1 = new Sort(10000000);
start = System.currentTimeMillis();
sort1.merge_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"merge_sort for 10000000 numbers take \" + time + \" ms \");
sort1 = new Sort(10000000);
start = System.currentTimeMillis();
sort1.quick_sort(0,9);
time = System.currentTimeMillis() - start;
System.out.println(\"quick_sort for 10000000 numbers take \" + time + \" ms \");
sort1 = new Sort(10000000);
start = System.currentTimeMillis();
sort1.heap_sort();
time = System.currentTimeMillis() - start;
}
}
Sample Output
insertion_sort for 10 numbers take 0 ms
merge_sort for 10 numbers take 0 ms
quick_sort for 10 numbers take 0 ms
heap_sort for 10 numbers take 0 ms
insertion_sort for 1000 numbers take 5 ms
merge_sort for 1000 numbers take 0 ms
quick_sort for 1000 numbers take 0 ms
heap_sort for 1000 numbers take 6 ms
insertion_sort for 100000 numbers take 1239 ms
merge_sort for 100000 numbers take 0 ms
quick_sort for 100000 numbers take 0 ms
heap sort for 100000 numbers take 21 ms
insertion_sort for 1000000 numbers take 217971 ms
merge_sort for 1000000 numbers take 0 ms
quick_sort for 1000000 numbers take 0 ms
heap_sort for 1000000 numbers take 261 ms
