Using Selection Sort, Generate 100000 positive numbers between (0,150) Search th
ID: 3780009 • Letter: U
Question
Using Selection Sort, Generate 100000 positive numbers between (0,150) Search the position of the first “58” in the array Count how many “58” in the array Sort the array Repeat step 3 on the sorted array and compute the time cost difference between the time from step 3 only, and time from step 4 and 5 together. Run your program three times and calculate the time: The time to generate 100000# The time to search the element 58 (step 2) The time to count the 58’s (step 3) The time to sort the array (step 4) Step 5 ( difference of 4 5 and step 3)
Explanation / Answer
PROGRAM CODE:
package selectionsort;
import java.util.Random;
public class SelectionSort {
//integer array to hold the numbers
static int numberArray[] = new int[100000];
//Selection sort method
public static void sort( ){
int N = numberArray.length;
int i, j, pos, temp;
for (i = 0; i < N-1; i++)
{
pos = i;
for (j = i+1; j < N; j++)
{
if (numberArray[j] < numberArray[pos])
{
pos = j;
}
}
/* Swap arr[i] and arr[pos] */
temp = numberArray[i];
numberArray[i] = numberArray[pos];
numberArray[pos]= temp;
}
}
//main function
public static void main(String args[])
{
Random random = new Random();
long step3TD, step4_5TD;
//Step 1 - generating 100000 numbers
long startTime = System.currentTimeMillis();
for(int i=0; i<100000; i++)
{
numberArray[i] = random.nextInt(150 + 1);
}
long endTime = System.currentTimeMillis();
System.out.println("Time taken to generate 100000 numbers: " + (endTime - startTime) + " ms");
//Step 2 - searching for the element 58
startTime = System.currentTimeMillis();
for(int i=0; i<numberArray.length; i++)
{
if(numberArray[i] == 58)
break;
}
endTime = System.currentTimeMillis();
System.out.println("Time to find the element (58): " + (endTime - startTime) + " ms");
//Step 3 - count the number of elements that are 58
startTime = System.currentTimeMillis();
int counter = 0;
for(int i=0; i<numberArray.length; i++)
{
if(numberArray[i] == 58)
counter++;
}
endTime = System.currentTimeMillis();
step3TD = endTime - startTime;
System.out.println("Time to find the number of elements of 58: " + step3TD + " ms");
System.out.println("Number of elements of 58: " + counter);
//Step 4 - Sorting the array
startTime = System.currentTimeMillis();
sort();
endTime = System.currentTimeMillis();
System.out.println("Time to sort the array: " + (endTime - startTime) + " ms");
//Step 5 _ find the difference in timing
step4_5TD = System.currentTimeMillis() - startTime;
System.out.println("Time difference: " + (step4_5TD - step3TD) + " ms");
}
}
OUTPUT:
Time taken to generate 100000 numbers: 8 ms
Time to find the element (58): 0 ms
Time to find the number of elements of 58: 1 ms
Number of elements of 58: 661
Time to sort the array: 3685 ms
Time difference: 3684 ms
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.