Objectives » To understand sorting better Instructions You may pick one of the t

Question

Objectives » To understand sorting better Instructions You may pick one of the two following exercises to do as your project 3 Option 1: Experimenting with Sorting Implement (or use built-in algorithms for) QuickSort, and InsertionSort. Compare their running times on sets of integers of size 10, 25, 50, and 100. Which appears to perform better as the number of integers increases? Why did you get the results you did? Make sure to run each algorithm at least 5 times on each set size (five times for set size of 10, five times for 25, etc. - for EACH algorithm.) Hint: Make use of the currentTimeMillis() method of System long startingTime = System.currentTimeMillis(); long total = 0; //do something here: run an algorithm to test timing on long stoppingTime = System.currentTimeMillis(); long elapsed stopping line - starting line; System. out.println(elapsed); This obtains the current time from the system at the beginning, then after the algorithm being tested is performed, get the stopping time. Then, find the difference, referred to as the elapsed time, and do something with it. Record in a table for this assignment.

Explanation / Answer

Complete Program:

// File: SortingTest.java
import java.util.Random;
public class SortingTest
{
public static void main(String[] args)
{  
  int size;
  int[] items1;
  int[] items2;  
  long startingTime, stoppingTime, elapsed, total;
    
  size = 10;
  items1 = new int[size];
  items2 = new int[size];
  fillArrays(items1, items2, size);
  
  System.out.println("Size: " + size);
  total = 0;
  for(int i = 1; i <= 5; i++)
  {
   startingTime = System.nanoTime();
   QuickSort(items1);
   stoppingTime = System.nanoTime();
   elapsed = stoppingTime - startingTime;
   total += elapsed;
  }  
  System.out.println("Total time for QuickSort in nanoseconds:     " + total);
    
  total = 0;
  for(int i = 1; i <= 5; i++)
  {
   startingTime = System.nanoTime();
   InsertionSort(items2);
   stoppingTime = System.nanoTime();
   elapsed = stoppingTime - startingTime;
   total += elapsed;
  }
  System.out.println("Total time for InsertionSort in nanoseconds: " + total);
  
  for(size = 25; size <= 100; size *= 2)
  {
   System.out.println(" Size: " + size);
   items1 = new int[size];
   items2 = new int[size];
   fillArrays(items1, items2, size);
   
   total = 0;
   for(int i = 1; i <= 5; i++)
   {
    startingTime = System.nanoTime();
    QuickSort(items1);
    stoppingTime = System.nanoTime();
    elapsed = stoppingTime - startingTime;
    total += elapsed;
   }  
   System.out.println("Total time for QuickSort in nanoseconds:     " + total);
   
   total = 0;
   for(int i = 1; i <= 5; i++)
   {
    startingTime = System.nanoTime();
    InsertionSort(items2);
    stoppingTime = System.nanoTime();
    elapsed = stoppingTime - startingTime;
    total += elapsed;
   }  
   System.out.println("Total time for InsertionSort in nanoseconds: " + total);
  }  
}

public static void fillArrays(int[] items1, int[] items2, int size)
{
  Random rand = new Random();  
  
  for(int i = 0; i < size; i++)
  {
   int number = rand.nextInt(size);
   items1[i] = number;
   items2[i] = number;
  }
}

public static void QuickSort(int[] items)
{
  QuickSort(items, 0, items.length - 1);
}

private static void QuickSort(int[] items, int l, int r)
{
  int s = Partition(items, l, r);

  if(l < s - 1)
   QuickSort(items, l, s - 1);
  if(s < r)
   QuickSort(items, s, r);
}

private static int Partition(int[] items, int l, int r)
{
  int p = l;
  int q = r;
  int temp;
  int pivot;
  pivot = items[(l + r) / 2];

  while(p <= q)
  {
   while(items[p] < pivot)
    p++;
   while(items[q] > pivot)
    q--;

   if(p <= q)
   {
    temp = items[p];
    items[p] = items[q];
    items[q] = temp;
    p++;
    q--;
   }
  }
  return p;
}


public static void InsertionSort(int[] items)
{
  for(int i = 1; i < items.length; i++)
  {
   int temp = items[i];
   int j = i;

   while(j > 0 && temp < items[j - 1])
   {
    items[j] = items[j - 1];
    j--;
   }

   items[j] = temp;
  }
}
}

Sample Output:

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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