Java- Data Structures and Analysis

profilebrinco
homework4.zip
Home>Computer Science homework help>Java- Data Structures and Analysis

homework4/BubbleSort.java

homework4/BubbleSort.java

// UMUC CMSC 350 
// Class QuickSort
// Adapted by Ioan from original sources:
// Liang - Introduction to Java Programming, 9th Edition (Code Examples of Chapter 25 - Sorting, Listing 25.2)
// Source code of the example available at: 
// http://www.cs.armstrong.edu/liang/intro9e/examplesource.html

public   class   BubbleSort   {
   /** Bubble sort method */
   public   static   void  bubbleSort ( int []  list )   {
     boolean  needNextPass  =   true ;
    
     for   ( int  k  =   1 ;  k  <  list . length  &&  needNextPass ;  k ++ )   {
       // Array may be sorted and next pass not needed
      needNextPass  =   false ;
       for   ( int  i  =   0 ;  i  <  list . length  -  k ;  i ++ )   {
         if   ( list [ i ]   >  list [ i  +   1 ])   {
           // Swap list[i] with list[i + 1]
           int  temp  =  list [ i ];
          list [ i ]   =  list [ i  +   1 ];
          list [ i  +   1 ]   =  temp ;
          
          needNextPass  =   true ;   // Next pass still needed
         }
       }
     }
   }

   /** A test method */
   public   static   void  main ( String []  args )   {
     int []  list  =   { 2 ,   3 ,   2 ,   5 ,   6 ,   1 ,   - 2 ,   3 ,   14 ,   12 };
    bubbleSort ( list );
     for   ( int  i  =   0 ;  i  <  list . length ;  i ++ )
       System . out . print ( list [ i ]   +   " " );
   }
}

homework4/InsertionSort.java

homework4/InsertionSort.java

// UMUC CMSC 350 
// Class QuickSort
// Adapted by Ioan from original sources:
// Liang - Introduction to Java Programming, 9th Edition (Code Examples of Chapter 6 - Single dimensional arrays, 
// Listing 6.9)
// Source code of the example available at: 
// http://www.cs.armstrong.edu/liang/intro9e/examplesource.html

public   class   InsertionSort   {
   /** The method for sorting the numbers */
   public   static   void  insertionSort ( double []  list )   {
     for   ( int  i  =   1 ;  i  <  list . length ;  i ++ )   {
       /** insert list[i] into a sorted sublist list[0..i-1] so that
           list[0..i] is sorted. */
       double  currentElement  =  list [ i ];
       int  k ;
       for   ( k  =  i  -   1 ;  k  >=   0   &&  list [ k ]   >  currentElement ;  k -- )   {
        list [ k  +   1 ]   =  list [ k ];
       }

       // Insert the current element into list[k+1]
      list [ k  +   1 ]   =  currentElement ;
     }
   }
}

homework4/Quick Sort Optimizations through Hybridization.docx

Quick Sort Optimizations through Hybridization

1. Specification

Part 1

Consider the attached QuickSort algorithm for sorting arrays and two algorithm optimization proposals QSopt1 and QSopt2, described below.

QSopt1 executes QuickSort for the partitions of size larger than a given cutoff value (usually 10) and executes Insertion Sort for sorting the partitions of size less than or equal to the cutoff value.

QSopt2 executes QuickSort until all partitions’ size gets lower than a given cutoff value (usually 10) and then, executes the improved Bubble Sort algorithm upon the whole "almost sorted" array.

This project requires writing two Java programs detailed below in Part 1 (testing the functionality of the proposed algorithms) and in Part 2 (measuring and comparing their execution time). The algorithms for QuickSort, InsertionSort and BubbleSort are attached.

Part 1 (Testing algorithms functionality)

Design and implement a program to test the QSopt1 and QSopt2 algorithms. Define an array of size 100, populated with randomly generated Integer or int values in the range 1 .. 999 and sort the array in increasing order by using the algorithms QuickSort, QSopt1 and QSopt2. Display the array content before sorting and then after invoking each sorting algorithm.

Part 2 (Measuring the execution time)

Design, implement and test a program which uses System.nanoTime() method to (1) measure the execution time of the three sorting algorithms and (2) display the average execution time values for 105 runs. Do this for each of the array sizes specified in the table below. Consider the arrays as being randomly populated with Integer or int values in the range 1 .. MAX as specified for each SIZE in the table below. After executing the program, fill-in the table cells with the measured values and include the table in the solution description document.

Note that due to the behavior of the JVM and JIT compiler, the execution time of the algorithms is much slower the first times they are run and therefore make sure to discard the measured values for the initial 5 runs.

Table 1 - Average Execution Time Average execution time for 100 runs SIZE = 100 MAX = 999 SIZE = 1000 MAX = 9,999 SIZE = 10,000 MAX = 99,999 SIZE = 100,000 MAX = 999,999 QuickSort QSopt1 QSopt2

The programs should compile without errors.

Notes 1. The array contents should not be displayed for Part 2. 2. For Part 2, the three algorithms should be executed and their execution time should be displayed for the required array sizes within the same program execution and without any user input.

2. Submission Requirements

Submit the following before the due date listed in the Calendar:

1. Part1.zip including all .java files for Part 1 and Part2.zip including all .java files for Part 2. The source code should use Java code conventions and appropriate code layout (white space management and indents) and comments.

2. The solution description document <YourSecondName>_P3 (.pdf or .doc / .docx) containing: (2.1) assumptions, main design decisions, error handling, (2.2) test cases and two relevant screenshots, (2.3) the table of average execution time filled in with the measure values. (2.4) discussion of the results, (2.5) lessons learned and (2.6) possible improvements. The size of the document file (including the screenshots) should be of three pages, single spaced, font size 10.

homework4/QuickSort.java

homework4/QuickSort.java

// UMUC CMSC 350 
// Class QuickSort
// Adapted by Ioan from original sources:
// Liang - Introduction to Java Programming, 9th Edition (Code Examples of Chapter 25 - Sorting, Listing 25.7)
// Source code of the example available at: 
// http://www.cs.armstrong.edu/liang/intro9e/examplesource.html

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

   private   static   void  quickSort ( int []  list ,   int  first ,   int  last )   {
     if   ( last  >  first )   {
       int  pivotIndex  =  partition ( list ,  first ,  last );
      quickSort ( list ,  first ,  pivotIndex  -   1 );
      quickSort ( list ,  pivotIndex  +   1 ,  last );
     }
   }

   /** Partition the array list[first..last] */
   private   static   int  partition ( int []  list ,   int  first ,   int  last )   {
     int  pivot  =  list [ first ];   // Choose the first element as the pivot
     int  low  =  first  +   1 ;   // Index for forward search
     int  high  =  last ;   // Index for backward search

     while   ( high  >  low )   {
       // Search forward from left
       while   ( low  <=  high  &&  list [ low ]   <=  pivot )
        low ++ ;

       // Search backward from right
       while   ( low  <=  high  &&  list [ high ]   >  pivot )
        high -- ;

       // Swap two elements in the list
       if   ( high  >  low )   {
         int  temp  =  list [ high ];
        list [ high ]   =  list [ low ];
        list [ low ]   =  temp ;
       }
     }

     while   ( high  >  first  &&  list [ high ]   >=  pivot )
      high -- ;

     // Swap pivot with list[high]
     if   ( pivot  >  list [ high ])   {
      list [ first ]   =  list [ high ];
      list [ high ]   =  pivot ;
       return  high ;
     }
     else   {
       return  first ;
     }
   }

   /** A test method */
   public   static   void  main ( String []  args )   {
     int []  list  =   { 2 ,   3 ,   2 ,   5 ,   6 ,   1 ,   - 2 ,   3 ,   14 ,   12 };
    quickSort ( list );
     for   ( int  i  =   0 ;  i  <  list . length ;  i ++ )
       System . out . print ( list [ i ]   +   " " );
   }
}