1.) For this problem, you will be getting some intuition for how much faster O(n

Question

1.) For this problem, you will be getting some intuition for how much faster O(n log n) algorithms are compared
to O(n^2).
Here is an implementation of selection sort for you...
public static void SelSort(int[] r)
{
for (int n=0; n<r.length; n++)
{
// find the minimum for posiition n
int mindex=n;
for (int i=n+1; i<r.length; i++)
{
if (r[i] < r[mindex])
{
mindex=i;
}
}
if (mindex != n)
{
// swap
int tmp = r[n];
r[n]=r[mindex];
r[mindex]=tmp;
}
}
}
Your job is to generate random int arrays of varying sizes to show the relative performance of selection sort
compared to an O(n log n) sort. Write a method int[] randomArray(int size) that creates a new empty
array of size size and fills it with random ints (see java.util.Random).
You can compute the time it takes for a method to run by calling System.currentTimeMillis() before and
after the call to the sort method.
I suggest using a loop like this:
for (int size=2500; size <= 160000; size *= 2)
{
int[] array = // generate random array
long start = System.currentTimeMillis();
// sort array
long end = System.currentTimeMillis();
long time_in_ms = (end-start);

// print out size and time_in_ms
}

Time SelSort using a loop like this and time Arrays.sort (incidentally, this is an implementation of quick
sort, another O(n log n) algorithm. Collections.sort, which is useful for non-array collections like
ArrayList uses mergesort). Save a text file containing enough times and sizes to see the behavior described by
the big-O notation.

Explanation / Answer

import java.util.Random;
public class timesel {
public static void main(String args[])
{
for (int size=2500; size <= 160000; size *= 2)
{
  
int[] array = createArray(size); // generate random array
long start = System.currentTimeMillis();
// sort array
SelSort(array);
long end = System.currentTimeMillis();
long time_in_ms = (end-start);
// print out size and time_in_ms
System.out.println("size: "+size+" "+"time in ms: "+time_in_ms);
}
}

private static int[] createArray(int size) {
int i;
//declare array
int a[] = new int[size];
Random r = new Random();
//insert random values
for(i=0;i<size;i++)
a[i]=r.nextInt();
return a;
}

private static void SelSort(int[] r) {
for (int n=0; n<r.length; n++)
{
// find the minimum for posiition n
int mindex=n;
for (int i=n+1; i<r.length; i++)
{
if (r[i] < r[mindex])
{
mindex=i;
}
}
if (mindex != n)
{
// swap
int tmp = r[n];
r[n]=r[mindex];
r[mindex]=tmp;
}
}
}
}

output:

size: 2500 time in ms: 31
size: 5000 time in ms: 128
size: 10000 time in ms: 84
size: 20000 time in ms: 266
size: 40000 time in ms: 1031
size: 80000 time in ms: 4223
size: 160000 time in ms: 17011

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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