1. Create a file called QuicksortTester.java in which to write your code. 2. Copy the skeleton code to your file. 3. Define and initialise the variable CUTOFF (ref. line 20). CUTOFF is a global constant. It indicates the value for which the problem size is too small for quicksort. Choose it carefully.
java quick sort
use the skeleton code to do task below
skeleton code
1 class QuicksortTester
2 {
3
4 /**
5 * Quicksort
6 */
7
8 public void quicksort( int [ ] a )
9 {
10 quicksort( a, 0, a.length - 1 );
11 }
12
13 /**
14 * Internal quicksort method that makes recursive calls.
15 * Uses median-of-three partitioning and a cut-off.
16 */
17
18 public void quicksort( int [ ] a, int low, int high )
19 {
20 if( low + CUTOFF > high )
21 insertionSort( a );
22 else
23 { // Sort low, middle, high
24 int middle = ( low + high ) / 2;
25 if( a[ middle ].compareTo( a[ low ] ) < 0 )
26 swapReferences( a, low, middle );
27 if( a[ high ].compareTo( a[ low ] ) < 0 )
28 swapReferences( a, low, high );
29 if( a[ high ].compareTo( a[ middle ] ) < 0 )
30 swapReferences( a, middle, high );
31
32 // Place pivot at position high - 1
33 swapReferences( a, middle, high - 1 );
34 int pivot = a[ high - 1 ];
35
36 // Begin partitioning
37 int i, j;
38 for( i = low, j = high - 1; ; )
39 {
40 while( a[ ++i ].compareTo( pivot ) < 0 )
41 ;
42 while( pivot.compareTo( a[ --j ] ) < 0 )
43 ;
44 if( i >= j )
45 break;
46 swapReferences( a, i, j );
47 }
48
49 // Restore pivot
50 swapReferences( a, i, high - 1 );
51
52 quicksort( a, low, i - 1 ); // Sort small elements
53 quicksort( a, i + 1, high ); // Sort large elements
54 }
55 }
56
57
58 // insert code here for question 3
59
60 // insert code here for question 4 a)
61
62 // insert code here for question 4 b)
63
64 // insert code here for question 5)
65
66 // insert code here for question 6)
67
68 }
Your task is the following:
1. Create a file called QuicksortTester.java in which to write your code.
2. Copy the skeleton code to your file.
3. Define and initialise the variable CUTOFF (ref. line 20). CUTOFF is a global constant.
It indicates the value for which the problem size is too small for quicksort. Choose it
carefully.
4. Complete the quick sort method by supplying code for the following methods:
a. insertionSort(int A[]) (ref. line 21). This function is called to perform
a simple sort on an array of integers when the problem size makes using
quicksort inefficient.
b. swapReferences( int [ ] A, int i, int j ) (ref. lines 26, 28, 30,
33, 46 and 50). This function is called to perform a swap of two elements, at
positions i and j, in an array A.
5. Write a new method called removeDuplicates( int [ ] A )that removes all
duplicate elements in an array A of N items. Return the number of items that remain
in A. Your method must run in O(N log N) average time. Use quicksort as a preprocessing step.
6. Test that your quicksort( int [ ] a ) and removeDuplicates( int [ ]
A ) methods work sufficiently.
Step by step
Solved in 4 steps
