1. Programming (non-collaborative) -Due at the end of Module 9. Given an array,
ID: 3700823 • Letter: 1
Question
1. Programming (non-collaborative) -Due at the end of Module 9. Given an array, a[i],... ,alj] with J-1-2, let k = 1(it j)/2 and choose as the partition element for QUICKSORT the median among ali], aljl, ak] (i.e., the value that would be in the middle if ali], alj], and a[k] were sorted). This is called median-of-three partitioning. (NOTE: There are several descriptions of the median-of-three method on the web. Students are not permitted to seek out these descriptions in solving this problem.) (a) [15 pointsl Write pseudocode for median-of-three partitioning. (b) 15 points What is the running time of median-of-three partitioning? Justify your answer (c) 20 pointsl What is the running time of QUICKSORT if you use median-of-three partitioning on an input set that is already sorted? Justify your answer (d) 50 pointsl Implement QUIcKSoRT using a normal pivot process and the median-of-three process described above. Test your run time analysis of medium-of-three, and then compare the average and worst case run times of QUICKSoRT with the two pivot processes. Note that you must implement all of these algorithms from scratch. Also remember that CPU time is not a valid measure for testing run time. You must use something such as the number of comparisons.Explanation / Answer
Code:
//Define method
public static void Qsort( Comparable [ ] a )
{
//Call method Qsort( a, 0, a.length - 1 );
}
//Declare variable private static final int CTOF = 10;
//Define method
private static void Qsort( Comparable [ ] a,int lw, int hgh )
{
//If value is greater if( lw + CTOF > hgh )
//Call method instnSrt( a, lw, hgh );
//Otherwise else
{
//Compute value
int mddle = ( lw + hgh ) / 2;
//If value is less than 0
if( a[ mddle ].compareTo( a[ lw ] ) < 0 )
//Call method
swpRfcs( a, lw, mddle );
//If value is less
if( a[ hgh ].compareTo( a[ lw ] ) < 0 )
//Call method
swpRfcs( a, lw, hgh );
//If value is negative
if( a[ hgh ].compareTo( a[ mddle ] ) < 0 )
//Call method
swpRfcs( a, mddle, hgh );
//Call method swpRfcs( a, mddle, hgh - 1 );
//Assign value Comparable pvt = a[ hgh - 1 ];
//Declare variables int li, lj;
//Loop for( li = lw, lj = hgh - 1; ; )
{
//Loop while( a[ ++li ].compareTo( pvt ) < 0 ) ;
//Loop while( pvt.compareTo( a[ --lj ] ) < 0 ) ;
//If value is greater if( li >= lj )
//Break break; //Call method swpRfcs( a, li, lj );
}
// Restore pvt swpRfcs( a, li, hgh - 1 );
//Call method Qsort( a, lw, li - 1 );
//Call method Qsort( a, li + 1, hgh );
}
}
//Define method
public static final void swpRfcs( Object [ ] a, int index1, int index2 )
{
//Assign value
Object tmp = a[ index1 ];
//Assign value
a[ index1 ] = a[ index2 ];
//Assign value
a[ index2 ] = tmp;
}
//Define method private static void instnSrt( Comparable [ ] a, int lw, int hgh )
{
//Loop
for( int p = lw + 1; p <= hgh; p++ )
{
//Create instance Comparable tmp = a[ p ];
//Declare variable
int lj; //Loop
for( lj = p; lj > lw && tmp.compareTo( a[ lj - 1 ] ) < 0; lj-- )
//Assign value
a[ lj ] = a[ lj - 1 ];
//Assign value
a[ lj ] = tmp;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.