For this lab, you will implement the five sorting algorithms we discussed (selec

Question

For this lab, you will implement the five sorting algorithms we discussed (selection, bubble, insertion, merge, quick), and compare their runtime performance. Requirements Create a class called SortingComparison. In that class, create five static methods, one for each algorithm that sorts an array of a generic type, using this header format: public static > E[] algName(E[] arrayToSort) Each algorithm takes in an array of items of a generic type E (which may or may not be sorted), and returns an array that has the items sorted from smallest to largest. You may, and should, create private helper methods for some sorting algorithms. Write additional functionality that does the following. Creates 1,000 arrays that each hold 100,000 items that are randomly generated. Passes each of the 1,000 arrays to each sorting algorithm method. Measures how long it takes each call to a sorting algorithm method to complete. Calculates the average time for each sorting method to sort the 1,000 arrays. Prints the average time for each sorting method to the console.

Explanation / Answer

import java.util.ArrayList;
import java.util.Random;

public class SortingComparison {
   public static <A> void main(String args[]){
       ArrayList<ArrayList<A>> list = new ArrayList<ArrayList<A>>();
       int min = 1, max=100;
       Random rn = new Random();
      
      
       for(int j=0;j<1000;j++){
           ArrayList list1 = new ArrayList();
           for(int i=0;i<100000 ;i++){
               int answer = rn.nextInt(max - min + 1) + min;
               list1.add(answer);
           }
           list.add(list1);
       }  
      
       long bubblestartTime = System.currentTimeMillis();
       for(int i=0;i<1000;i++){
           bubbleSort(list.get(i));
       }
       long bubbleendTime = System.currentTimeMillis();
       long bubbletotalTime = bubbleendTime - bubblestartTime;
       System.out.println("Bubble sort takes "+bubbletotalTime);
      
      
       long selectionstartTime = System.currentTimeMillis();
       for(int i=0;i<1000;i++){
           selectionSort(list.get(i));
       }
       long selectionendTime = System.currentTimeMillis();
       long selectiontotalTime = selectionendTime - selectionstartTime;
       System.out.println("Selection sort takes "+selectiontotalTime);
      
      
       long insertionstartTime = System.currentTimeMillis();
       for(int i=0;i<1000;i++){
           insertionSort(list.get(i));
       }
       long insertionendTime = System.currentTimeMillis();
       long insertiontotalTime = insertionendTime - insertionstartTime;
       System.out.println("insertion sort takes "+insertiontotalTime);
      
       long quickstartTime = System.currentTimeMillis();
       for(int i=0;i<1000;i++){
           quickSort(list.get(i),0,list.get(i).size());
       }
       long quickendTime = System.currentTimeMillis();
       long quicktotalTime = quickendTime - quickstartTime;
       System.out.println("Quick sort takes "+quicktotalTime);
      
       long mergestartTime = System.currentTimeMillis();
       for(int i=0;i<1000;i++){
           mergeSort(list.get(i),0,list.get(i).size());
       }
       long mergeendTime = System.currentTimeMillis();
       long mergetotalTime = mergeendTime - mergestartTime;
       System.out.println("Merge sort takes "+mergetotalTime);
      
   }
  
   static void bubbleSort(ArrayList arr) {
int len = arr.size();
Object temp = 0;
for(int i=0; i < len; i++){
for(int j=1; j < (len-i); j++){
if(arr.get(j-1).toString().compareTo(arr.get(j).toString())>0 ){
temp = arr.get(j-1);
arr.add(j-1, arr.get(j));
arr.add(j,temp);
}
  
}
}
   }
  
   public static void selectionSort(ArrayList arr){
for (int i = 0; i < arr.size() - 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.size(); j++){
if (arr.get(j).toString().compareTo(arr.get(index).toString())<0){
index = j;
}
}
Object smallerNumber = arr.get(index);   
arr.add(index, arr.get(i));
arr.add(i,smallerNumber);
}
}
  
   public static void insertionSort(ArrayList array) {
int n = array.size();
for (int j = 1; j < n; j++) {
Object key = array.get(j);
int i = j-1;
while ( (i > -1) && ( array.get(i).toString().compareTo(key.toString() )) >0 ) {
array.add(i+1,array.get(i));
i--;
}
array.add(i+1, key);
}
}
  
   public static void quickSort(ArrayList arr, int low, int high)
{
int i = low, j = high;
Object temp;
Object pivot = arr.get((low + high)/2);

while (i <= j)
{
while (arr.get(i).toString().compareTo(pivot.toString())<0)
i++;
while (arr.get(j).toString().compareTo(pivot.toString())>0)
j--;
if (i <= j)
{

temp = arr.get(i);
arr.add(i,arr.get(j));
arr.add(j,temp);

i++;
j--;
}
}
if (low < j)
quickSort(arr, low, j);
if (i < high)
quickSort(arr, i, high);
}
   public static void mergeSort(ArrayList arr, int low, int high)
{
int N = high - low;   
if (N <= 1)
return;
int mid = low + N/2;
mergeSort(arr, low, mid);
mergeSort(arr, mid, high);
Object[] temp = new Object[N];
int i = low, j = mid;
for (int k = 0; k < N; k++)
{
if (i == mid)
temp[k] = arr.get(j++);
else if (j == high)
temp[k] = arr.get(i++);
else if (arr.get(j).toString().compareTo(arr.get(i).toString())<0)
temp[k] = arr.get(j++);
else
temp[k] = arr.get(i++);
}
for (int k = 0; k < N; k++)
arr.add(low + k, temp[k]);   
}
}  

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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