This programming assignment is to implement and compare the following sorting al

Question

This programming assignment is to implement and compare the following sorting algorithms on arrays of integers, using either Java or C++.

- Insertionsort

- quicksort (recursive version ) use the right-most element as pivot

- quicksort (recursive version ), use the right-most element as pivot and switch to insertion sort when size of array is less than certain predetermined integer -- the cutoff size

- Quicksort2 (recursive version ) , use the median of three as the pivot element.

- mergesort recursive

- Heapsort

You must submit the following:

All the source codes

Your source code must be well-documented.

Documentation that describes what you did, and how to run your program

Explanation / Answer

public class Main {
public static void main(String[] args){
   int t= 50000;
   int t2=100000;
   int t3=200000;
   int t4=300000;
   int t5=400000;


   /**
   * QUICK SORT
   */
   System.out.println("***********Quick Sort *****************");
   Long b=System.currentTimeMillis();
   QuickSort q1=new QuickSort(t);
   q1.sort();
   Long a=System.currentTimeMillis();
   System.out.println("Quick sort takes "+(a-b)+" ms"+ " for " +t);
   Long b2=System.currentTimeMillis();
   QuickSort q2=new QuickSort(t2);
   q2.sort();
   Long a2=System.currentTimeMillis();
   System.out.println("Quick sort takes "+(a2-b2)+" ms"+ " for " +t2);
   Long b3=System.currentTimeMillis();
   QuickSort q3=new QuickSort(t3);
   q3.sort();
   Long a3=System.currentTimeMillis();
   System.out.println("Quick sort takes "+(a3-b3)+" ms"+ " for "+ t3);
   Long b4=System.currentTimeMillis();
   QuickSort q4=new QuickSort(t4);
   q4.sort();
   Long a4=System.currentTimeMillis();
   System.out.println("Quick sort takes "+(a4-b4)+" ms" + " for "+ t4);
   Long b5=System.currentTimeMillis();
   QuickSort q5=new QuickSort(t5);
   q5.sort();
   Long a5=System.currentTimeMillis();
   System.out.println("Quick sort takes "+(a5-b5)+" ms" + " for "+ t5);


   /**
   * InsertionSort
   */
   System.out.println("********************Insertion Sort ************************");
   b=System.currentTimeMillis();
   InsertionSort i1=new InsertionSort(t);
   i1.sort();
   a=System.currentTimeMillis();
   System.out.println("Insertion sort takes "+(a-b)+ " ms"+ " for " +t);
   b2=System.currentTimeMillis();
   InsertionSort i2=new InsertionSort(t2);
   i2.sort();
   a2=System.currentTimeMillis();
   System.out.println("Insertion sort takes "+(a2-b2)+" ms"+ " for " +t2);
b3=System.currentTimeMillis();
   InsertionSort i3=new InsertionSort(t3);
   i3.sort();
   a3=System.currentTimeMillis();
   System.out.println("Insertion sort takes "+(a3-b3)+" ms"+ " for "+ t3);
   b4=System.currentTimeMillis();
   InsertionSort i4=new InsertionSort(t4);
   i4.sort();
   a4=System.currentTimeMillis();
   System.out.println("Insertion sort takes "+(a4-b4)+" ms" + " for "+ t4);
   b5=System.currentTimeMillis();
   InsertionSort i5=new InsertionSort(t5);
   i5.sort();
   a5=System.currentTimeMillis();
   System.out.println("Insertion sort takes "+(a5-b5)+" ms" + " for "+ t5);

   /**
   * MergeSort
   */
   System.out.println("*******************MergeSort************************");
   MergeSort m1=new MergeSort(t);
   m1.sort();
   a=System.currentTimeMillis();
   System.out.println("Merge sort takes "+(a-b)+ " ms"+ " for " +t);
   b2=System.currentTimeMillis();
   MergeSort m2=new MergeSort(t2);
   m2.sort();
   a2=System.currentTimeMillis();
   System.out.println("Merge sort takes "+(a2-b2)+ " ms"+ " for " +t2);
   b3=System.currentTimeMillis();
   MergeSort m3=new MergeSort(t3);
   m3.sort();
   a3=System.currentTimeMillis();
   System.out.println("Merge sort takes "+(a3-b3)+" ms"+ " for "+ t3);
   b4=System.currentTimeMillis();
   MergeSort m4=new MergeSort(t4);
   m4.sort();
   a4=System.currentTimeMillis();
   System.out.println("Mege sort takes "+(a4-b4)+ " ms" + " for "+ t4);
   b5=System.currentTimeMillis();
   MergeSort m5=new MergeSort(t5);
   m5.sort();
   a5=System.currentTimeMillis();
   System.out.println("Merge sort takes "+(a5-b5)+" ms" + " for "+ t5);

   /**
   * SELECTION SORT
   */

   System.out.println("********************Selection Sort****************");
   b=System.currentTimeMillis();
   SelectionSort s1=new SelectionSort(t);
   s1.sort();
   a=System.currentTimeMillis();
   System.out.println("Selection sort takes "+(a-b)+" ms"+ " for " +t);
   b2=System.currentTimeMillis();
   SelectionSort s2=new SelectionSort(t2);
   s2.sort();
   a2=System.currentTimeMillis();
   System.out.println("Selection sort takes "+(a2-b2)+ "ms"+ " for " +t2);
   b3=System.currentTimeMillis();
   SelectionSort s3=new SelectionSort(t3);
   s3.sort();
   a3=System.currentTimeMillis();
   System.out.println("Selection sort takes "+(a3-b3)+" ms"+ " for "+ t3);
   b4=System.currentTimeMillis();
   SelectionSort s4=new SelectionSort(t4);
   s4.sort();
   a4=System.currentTimeMillis();
   System.out.println("Selection sort takes "+(a4-b4)+" ms" + " for "+ t4);
   b5=System.currentTimeMillis();
   SelectionSort s5=new SelectionSort(t5);
   s5.sort();
   a5=System.currentTimeMillis();
   System.out.println("Selection sort takes "+(a5-b5)+" ms" + " for "+ t5);

   }
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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