Create an ArrayListReview class with one generic type to do the following after

Question

Create an ArrayListReview class with one generic type to do the following after

import java.util.ArrayList;

import java.util.Arrays;

class ArrayListReview<N extends Number> {

ArrayList<N> mylist = new ArrayList<>();//an instance

ArrayListReview() {

mylist = (ArrayList<N>) new ArrayList<>(Arrays.asList(new Integer[]{45, 53, 10}));

}

-Implement insertionSort either recursively or non-recursively.

-Implement mergeSort using recursion.

-Use System.nanoTime() to find out the speed of your program.

Explanation / Answer

Answer 1. using recursivly insertion sort

import java.util.ArrayList;

import java.util.Arrays;

import java.lang.*;

class ArrayListReview<N extends Number> {

ArrayList<N> mylist = new ArrayList<>();//an instance

ArrayListReview() {

mylist = (ArrayList<N>) new ArrayList<>(Arrays.asList(new Integer[]{45, 53, 10}));

public void insertionSortRecursive(<n> arr[])

{

long startTime = System.nanoTime();

// Base case

int n = sizeof(arr)/sizeof(arr[0]);

if (n <= 1)

return;

// Sort first n-1 elements

insertionSortRecursive( arr, n-1 );

// Insert last element at its correct position

// in sorted array.

int last = arr[n-1];

int j = n-2;

/* Move elements of arr[0..i-1], that are

greater than key, to one position ahead

of their current position */

while (j >= 0 && arr[j] > last)

{

arr[j+1] = arr[j];

j--;

}

arr[j+1] = last;

long endTime = System.nanoTime();

long totalTime = endTime - startTime;

System.out.println(totalTime);

}

}

==================================================================

Answer 2. using mergesort using recursion

import java.util.ArrayList;

import java.util.Arrays;

import java.lang.*;

class ArrayListReview<N extends Number> {

ArrayList<N> mylist = new ArrayList<>();//an instance

ArrayListReview() {

mylist = (ArrayList<N>) new ArrayList<>(Arrays.asList(new Integer[]{45, 53, 10}));

int arr_size = sizeof(arr)/sizeof(arr[0]);

long startTime = System.nanoTime();

mergeSort(<N>arr, 0, arr_size - 1);

long endTime = System.nanoTime();

long totalTime = endTime - startTime;

public void merge(int arr[], int l, int m, int r)

{

int i, j, k;

int n1 = m - l + 1;

int n2 = r - m;

/* create temp arrays */

int L[n1], R[n2];

/* Copy data to temp arrays L[] and R[] */

for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)

R[j] = arr[m + 1+ j];

/* Merge the temp arrays back into arr[l..r]*/

i = 0; // Initial index of first subarray

j = 0; // Initial index of second subarray

k = l; // Initial index of merged subarray

while (i < n1 && j < n2)

{

if (L[i] <= R[j])

{

arr[k] = L[i];

i++;

}

else

{

arr[k] = R[j];

j++;

}

k++;

}

/* Copy the remaining elements of L[], if there

are any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy the remaining elements of R[], if there

are any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

/* l is for left index and r is right index of the

sub-array of arr to be sorted */

public void mergeSort(int arr[], int l, int r)

{

if (l < r)

{

// Same as (l+r)/2, but avoids overflow for

// large l and h

int m = l+(r-l)/2;

// Sort first and second halves

mergeSort(arr, l, m);

mergeSort(arr, m+1, r);

merge(arr, l, m, r);

}

}

}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.