Please edit the following code to make it neatly print the sorting times for all
ID: 3739402 • Letter: P
Question
Please edit the following code to make it neatly print the sorting times for all the sorting methods in the code. It must include the time it takes to sort 1000, 10000, 100000, and 1000000 elements. I need to be able to fill out the following table with the information from the output-
import java.util.Random;
/**
*
* @author Patel Heggere
*/
public class ArraySortTest {
public static void main(String[] args) {
int arySize = 1000;
long startTime, timeTaken;
while (arySize < 1000001) {
ArraySort arySort = new ArraySort(arySize);
// For Insertion Sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.insertionSort();
timeTaken = System.currentTimeMillis() - startTime;
arySort.toString();
System.out.println("Time taken for Insertion Sort: "
+ timeTaken + " msec");
// For Enhanced Insertion Sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.enhancedInsertionSort();
timeTaken = System.currentTimeMillis() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Enhanced Insertion Sort: "
+ timeTaken + " msec");
//merge sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.MergeSort(arySort.ary, 0, arySort.ary.length - 1);
timeTaken = System.currentTimeMillis() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Merge Sort: "
+ timeTaken + " msec");
//quick sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.quicksort(arySort.ary, 0, arySort.ary.length - 1);
timeTaken = System.currentTimeMillis() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Quick Sort: "
+ timeTaken + " msec");
//improved quick sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.imprquickSort();
timeTaken = System.currentTimeMillis() - startTime;
System.out.println(arySort);
System.out.println("Time taken for improved Quick Sort: "
+ timeTaken + " msec");
//shell sort
arySort.initArray();
startTime = System.currentTimeMillis();
arySort.Shellsort();
timeTaken = System.currentTimeMillis() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Shell Sort: "
+ timeTaken + " msec");
//List Insertion sort
LinkedlistIS list = new LinkedlistIS(arySize);
list.initArray();
startTime = System.currentTimeMillis();
list.insertionSort();
timeTaken = System.currentTimeMillis() - startTime;
System.out.println("Time taken for List Insertion sort: "
+ timeTaken + " msec");
arySize *= 10;
} // end of while
}
}
class ArraySort {
public long[] ary; // ref to array a, unsorted
public int size; // array size
public ArraySort(int max) // constructor
{
ary = new long[max]; // create the array
size = max;
}
public String toString() // displays array: first 10 and last 10
{
String SortedArray = "";
for (int i = 0; i < 10; i++) {
SortedArray = SortedArray + ary[i] + " ";
}
for (int i = size - 1; i > size - 1 - 10; i--) {
SortedArray = SortedArray + ary[i] + " ";
}
return SortedArray;
}
public void initArray() {
Random rand = new Random(0);
for (int i = 0; i < size; i++) {
ary[i] = rand.nextInt(size * 20);
}
}
public void insertionSort() {
/*Function to sort array using insertion sort*/
int n = ary.length;
for (int i = 1; i < n; ++i) {
long key = ary[i];
int j = i - 1;
while (j >= 0 && ary[j] > key) {
ary[j + 1] = ary[j];
j = j - 1;
}
ary[j + 1] = key;
}
}
public void enhancedInsertionSort() {
//insertion sort
for (int i = 1; i < size; i++) {
long key = ary[i];
int pos = binary(0, i - 1, key); //finds where the element will be stored
for (int j = i; j > pos; j--) //shifts the other elements by 1 position to the right
{
ary[j] = ary[j - 1];
}
ary[pos] = key; //places the key element in the pos position
}
}
//uses binary search technique to find the position where the element will be inserted
public int binary(int low, int high, long key) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (key > ary[mid]) {
low = mid + 1;
} else if (key < ary[mid]) {
high = mid - 1;
} else {
return mid;
}
}
return low;
}
public void merge(long arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
long L[] = new long[n1];
long R[] = new long[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];
}
int i = 0, j = 0;
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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public void imprquickSort() {
recursiveQuickSort(0, ary.length - 1);
}
public void recursiveQuickSort(int left, int right) {
if (left >= right) {
return;
}
long pivotIndexvot = ary[right];
int mid = partition(left, right, pivotIndexvot);
recursiveQuickSort(left, mid - 1);
recursiveQuickSort(mid + 1, right);
} // end recursiveQuickSort()
public void swap(int dex1, int dex2) { // swap two elements
long temp = ary[dex1];
ary[dex1] = ary[dex2];
ary[dex2] = temp;
} // end swap()
public int partition(int left, int right, long pivotIndexvot) {
int leftPointer = left - 1; // left of first element
int rightPoiter = right;
while (true) {
while (ary[++leftPointer] < pivotIndexvot)
;
while (leftPointer < rightPoiter && ary[--rightPoiter] >= pivotIndexvot)
;
if (leftPointer >= rightPoiter) //
{
break;
} else
{
swap(leftPointer, rightPoiter); // swap elements
}
}
swap(leftPointer, right);
return leftPointer;
} // end partition()
//method Mto mergesort
void MergeSort(long arr[], int l, int r) {
if (l < r) {
// Find mid point
int m = (l + r) / 2;
// Sort first and second partition
MergeSort(arr, l, m);
MergeSort(arr, m + 1, r);
// Merge the sorted partioton
merge(arr, l, m, r);
}
}
int partition(long arr[], int low, int high) {
long pivotIndexvot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivotIndexvot) {
i++;
// swap arr[i] and arr[j]
long temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivotIndexvot)
long temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
//method to quick sort
public void quicksort(long arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
/* function to sort arr using shellSort */
int Shellsort() {
int n = ary.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {
long temp = ary[i];
int j;
for (j = i; j >= gap && ary[j - gap] > temp; j -= gap) {
ary[j] = ary[j - gap];
}
ary[j] = temp;
}
}
return 0;
}
}
class LinkedlistIS {
node head;
node sorted;
int size;
public LinkedlistIS(int size) {
this.size = size;
}
class node {
long value;
node next;
public node(long value) {
this.value = value;
}
}
public void initArray() {
Random rand = new Random(0);
for (int i = 0; i < size; i++) {
push(rand.nextInt(size * 20));
}
}
void push(long value) {
/* allocate node */
node newnode = new node(value);
newnode.next = head;
head = newnode;
}
// function to sort a list using insertion sort
void insertionSort() {
sorted = null;
node current = head;
//traverse list
while (current != null) {
node next = current.next;
sortedInsert(current);
// Update current
current = next;
}
head = sorted;
}
//method to insert new node
void sortedInsert(node newnode) {
if (sorted == null || sorted.value >= newnode.value) {
newnode.next = sorted;
sorted = newnode;
} else {
node current = sorted;
while (current.next != null && current.next.value < newnode.value) {
current = current.next;
}
newnode.next = current.next;
current.next = newnode;
}
}
/* Method to print list */
void printlist(node head) {
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
}
}
Explanation / Answer
You will have to take the time in nanosec to capture the time for smaller lists
and for size 100000 it will take quite a long time but for other lists the output is
For Size 1000
Time taken for Insertion Sort: 3865299 nsec
2 6 9 18 31 41 49 127 130 132 19999 19985 19980 19964 19939 19911 19884 19857 19855 19841
Time taken for Enhanced Insertion Sort: 3029712 nsec
60 108 141 147 190 205 210 214 214 226 19936 19931 19905 19902 19900 19859 19818 19782 19771 19766
Time taken for Merge Sort: 1243375 nsec
11 12 13 21 44 56 69 80 84 115 19989 19987 19985 19897 19885 19881 19877 19875 19872 19854
Time taken for Quick Sort: 518797 nsec
14 19 113 125 131 142 192 238 243 249 19995 19930 19928 19907 19867 19833 19802 19780 19762 19750
Time taken for improved Quick Sort: 663033 nsec
34 53 67 144 146 170 211 220 224 246 19981 19972 19911 19908 19877 19876 19864 19861 19860 19856
Time taken for Shell Sort: 909593 nsec
Time taken for List Insertion sort: 1873935 nsec
For Size 10000
Time taken for Insertion Sort: 81248299 nsec
47 52 68 109 128 166 170 189 244 264 199974 199957 199956 199940 199900 199890 199878 199865 199830 199796
Time taken for Enhanced Insertion Sort: 21357503 nsec
25 35 40 49 79 85 87 104 111 123 199992 199972 199971 199942 199938 199938 199899 199881 199839 199821
Time taken for Merge Sort: 2746903 nsec
18 34 65 75 78 82 90 109 109 111 199989 199989 199953 199924 199920 199903 199872 199871 199850 199805
Time taken for Quick Sort: 1636437 nsec
33 41 94 106 115 115 142 160 164 177 199989 199954 199935 199930 199917 199894 199884 199865 199865 199845
Time taken for improved Quick Sort: 1666643 nsec
17 26 34 45 53 65 67 109 143 148 199989 199971 199964 199960 199942 199937 199845 199815 199774 199772
Time taken for Shell Sort: 6268980 nsec
Time taken for List Insertion sort: 318919801 nsec
For Size 100000
Time taken for Insertion Sort: 4552532305 nsec
46 48 52 75 77 87 94 104 130 130 1999954 1999948 1999932 1999932 1999904 1999859 1999852 1999809 1999722 1999711
Time taken for Enhanced Insertion Sort: 3634540297 nsec
23 37 48 71 77 132 139 185 228 240 1999963 1999848 1999841 1999839 1999785 1999747 1999724 1999680 1999664 1999647
Time taken for Merge Sort: 29046944 nsec
10 42 51 87 109 139 140 200 226 229 1999993 1999988 1999934 1999920 1999914 1999865 1999828 1999826 1999800 1999799
Time taken for Quick Sort: 30166472 nsec
66 88 116 143 155 160 181 206 231 250 1999983 1999949 1999943 1999940 1999911 1999861 1999850 1999845 1999831 1999783
Time taken for improved Quick Sort: 13386008 nsec
3 8 105 129 157 164 168 180 180 208 1999984 1999969 1999921 1999910 1999902 1999883 1999849 1999845 1999813 1999781
Time taken for Shell Sort: 36544195 nsec
The code is
////////////////
import java.util.Random;
/**
*
* @author Patel Heggere
*/
public class ArraySortTest {
public static void main(String[] args) {
int arySize = 1000;
long startTime, timeTaken;
while (arySize < 1000001) {
System.out.println("For Size "+arySize);
ArraySort arySort = new ArraySort(arySize);
// For Insertion Sort
arySort.initArray();
startTime = System.nanoTime();
arySort.insertionSort();
timeTaken = System.nanoTime() - startTime;
arySort.toString();
System.out.println("Time taken for Insertion Sort: "
+ timeTaken + " nsec");
// For Enhanced Insertion Sort
arySort.initArray();
startTime = System.nanoTime();
arySort.enhancedInsertionSort();
timeTaken = System.nanoTime() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Enhanced Insertion Sort: "
+ timeTaken + " nsec");
//merge sort
arySort.initArray();
startTime = System.nanoTime();
arySort.MergeSort(arySort.ary, 0, arySort.ary.length - 1);
timeTaken = System.nanoTime() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Merge Sort: "
+ timeTaken + " nsec");
//quick sort
arySort.initArray();
startTime = System.nanoTime();
arySort.quicksort(arySort.ary, 0, arySort.ary.length - 1);
timeTaken = System.nanoTime() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Quick Sort: "
+ timeTaken + " nsec");
//improved quick sort
arySort.initArray();
startTime = System.nanoTime();
arySort.imprquickSort();
timeTaken = System.nanoTime() - startTime;
System.out.println(arySort);
System.out.println("Time taken for improved Quick Sort: "
+ timeTaken + " nsec");
//shell sort
arySort.initArray();
startTime = System.nanoTime();
arySort.Shellsort();
timeTaken = System.nanoTime() - startTime;
System.out.println(arySort);
System.out.println("Time taken for Shell Sort: "
+ timeTaken + " nsec");
//List Insertion sort
LinkedlistIS list = new LinkedlistIS(arySize);
list.initArray();
startTime = System.nanoTime();
list.insertionSort();
timeTaken = System.nanoTime() - startTime;
System.out.println("Time taken for List Insertion sort: "
+ timeTaken + " nsec");
arySize *= 10;
} // end of while
}
}
class ArraySort {
public long[] ary; // ref to array a, unsorted
public int size; // array size
public ArraySort(int max) // constructor
{
ary = new long[max]; // create the array
size = max;
}
public String toString() // displays array: first 10 and last 10
{
String SortedArray = "";
for (int i = 0; i < 10; i++) {
SortedArray = SortedArray + ary[i] + " ";
}
for (int i = size - 1; i > size - 1 - 10; i--) {
SortedArray = SortedArray + ary[i] + " ";
}
return SortedArray;
}
public void initArray() {
Random rand = new Random();
for (int i = 0; i < size; i++) {
ary[i] = rand.nextInt(size * 20);
}
}
public void insertionSort() {
/*Function to sort array using insertion sort*/
int n = ary.length;
for (int i = 1; i < n; ++i) {
long key = ary[i];
int j = i - 1;
while (j >= 0 && ary[j] > key) {
ary[j + 1] = ary[j];
j = j - 1;
}
ary[j + 1] = key;
}
}
public void enhancedInsertionSort() {
//insertion sort
for (int i = 1; i < size; i++) {
long key = ary[i];
int pos = binary(0, i - 1, key); //finds where the element will be stored
for (int j = i; j > pos; j--) //shifts the other elements by 1 position to the right
{
ary[j] = ary[j - 1];
}
ary[pos] = key; //places the key element in the pos position
}
}
//uses binary search technique to find the position where the element will be inserted
public int binary(int low, int high, long key) {
int mid;
while (low <= high) {
mid = (low + high) / 2;
if (key > ary[mid]) {
low = mid + 1;
} else if (key < ary[mid]) {
high = mid - 1;
} else {
return mid;
}
}
return low;
}
public void merge(long arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
long L[] = new long[n1];
long R[] = new long[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];
}
int i = 0, j = 0;
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++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public void imprquickSort() {
recursiveQuickSort(0, ary.length - 1);
}
public void recursiveQuickSort(int left, int right) {
if (left >= right) {
return;
}
long pivotIndexvot = ary[right];
int mid = partition(left, right, pivotIndexvot);
recursiveQuickSort(left, mid - 1);
recursiveQuickSort(mid + 1, right);
} // end recursiveQuickSort()
public void swap(int dex1, int dex2) { // swap two elements
long temp = ary[dex1];
ary[dex1] = ary[dex2];
ary[dex2] = temp;
} // end swap()
public int partition(int left, int right, long pivotIndexvot) {
int leftPointer = left - 1; // left of first element
int rightPoiter = right;
while (true) {
while (ary[++leftPointer] < pivotIndexvot)
;
while (leftPointer < rightPoiter && ary[--rightPoiter] >= pivotIndexvot)
;
if (leftPointer >= rightPoiter) //
{
break;
} else
{
swap(leftPointer, rightPoiter); // swap elements
}
}
swap(leftPointer, right);
return leftPointer;
} // end partition()
//method Mto mergesort
void MergeSort(long arr[], int l, int r) {
if (l < r) {
// Find mid point
int m = (l + r) / 2;
// Sort first and second partition
MergeSort(arr, l, m);
MergeSort(arr, m + 1, r);
// Merge the sorted partioton
merge(arr, l, m, r);
}
}
int partition(long arr[], int low, int high) {
long pivotIndexvot = arr[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (arr[j] <= pivotIndexvot) {
i++;
// swap arr[i] and arr[j]
long temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivotIndexvot)
long temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
//method to quick sort
public void quicksort(long arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
/* function to sort arr using shellSort */
int Shellsort() {
int n = ary.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i += 1) {
long temp = ary[i];
int j;
for (j = i; j >= gap && ary[j - gap] > temp; j -= gap) {
ary[j] = ary[j - gap];
}
ary[j] = temp;
}
}
return 0;
}
}
class LinkedlistIS {
node head;
node sorted;
int size;
public LinkedlistIS(int size) {
this.size = size;
}
class node {
long value;
node next;
public node(long value) {
this.value = value;
}
}
public void initArray() {
Random rand = new Random(0);
for (int i = 0; i < size; i++) {
push(rand.nextInt(size * 20));
}
}
void push(long value) {
/* allocate node */
node newnode = new node(value);
newnode.next = head;
head = newnode;
}
// function to sort a list using insertion sort
void insertionSort() {
sorted = null;
node current = head;
//traverse list
while (current != null) {
node next = current.next;
sortedInsert(current);
// Update current
current = next;
}
head = sorted;
}
//method to insert new node
void sortedInsert(node newnode) {
if (sorted == null || sorted.value >= newnode.value) {
newnode.next = sorted;
sorted = newnode;
} else {
node current = sorted;
while (current.next != null && current.next.value < newnode.value) {
current = current.next;
}
newnode.next = current.next;
current.next = newnode;
}
}
/* Method to print list */
void printlist(node head) {
while (head != null) {
System.out.print(head.value + " ");
head = head.next;
}
}
}