Modify the code below to count the number of comparisons and the number of swaps

Question

Modify the code below to count the number of comparisons and the number of swaps

import java.util.Random;

public class MergeSort {
private int[] data;
private static final Random generator = new Random();

public MergeSort( int size ) {
data = new int[ size ];

for ( int i = 0; i < size; i++ )
data[ i ] = 10 + generator.nextInt( 90 );
}

// call this method from main program
public void sort() {
sortArray( 0, data.length - 1 );
}

private void sortArray( int low, int high )
{
if ( ( high - low ) >= 1 ) {
int middle1 = ( low + high ) / 2;
int middle2 = middle1 + 1;

sortArray( low, middle1 );
sortArray( middle2, high );

merge ( low, middle1, middle2, high );
}
}

private void merge( int left, int middle1, int middle2, int right )
{
int leftIndex = left;
int rightIndex = middle2;
int combinedIndex = left;
int[] combined = new int[ data.length ];
  
while ( leftIndex <= middle1 && rightIndex <= right ) {
if ( data[ leftIndex ] <= data[ rightIndex ] )
combined[ combinedIndex++ ] = data[ leftIndex++ ];
else
combined[ combinedIndex++ ] = data[ rightIndex++ ];
}

if ( leftIndex == middle2 )
while ( rightIndex <= right )
combined[ combinedIndex++ ] = data[ rightIndex++ ];
else
while ( leftIndex <= middle1 )
combined[ combinedIndex++ ] = data[ leftIndex++ ];

for ( int i = left; i <= right; i++ )
data[ i ] = combined[ i ];
}
  
}

Explanation / Answer

Hi, I have added the required code.

import java.util.Random;

public class MergeSort {

   private int[] data;

   private int swap;

   private int comparisons;

   private static final Random generator = new Random();

   public MergeSort( int size ) {

       data = new int[ size ];

       for ( int i = 0; i < size; i++ )

           data[ i ] = 10 + generator.nextInt( 90 );

       // initializing swap and comaparisons

       swap = 0;

       comparisons = 0;

   }

   // call this method from main program

   public void sort() {

       sortArray( 0, data.length - 1 );

   }

   private void sortArray( int low, int high )

   {

       if ( ( high - low ) >= 1 ) {

           int middle1 = ( low + high ) / 2;

           int middle2 = middle1 + 1;

           sortArray( low, middle1 );

           sortArray( middle2, high );

           merge ( low, middle1, middle2, high );

       }

   }

   private void merge( int left, int middle1, int middle2, int right )

   {

       int leftIndex = left;

       int rightIndex = middle2;

       int combinedIndex = left;

       int[] combined = new int[ data.length ];

       while ( leftIndex <= middle1 && rightIndex <= right ) {

           comparisons++; // increasing comparisons

           if ( data[ leftIndex ] <= data[ rightIndex ] )

               combined[ combinedIndex++ ] = data[ leftIndex++ ];

           else {

               combined[ combinedIndex++ ] = data[ rightIndex++ ];

               swap = swap + (middle2 - leftIndex); // number of swap = number of inversions

           }

       }

       if ( leftIndex == middle2 )

           while ( rightIndex <= right )

               combined[ combinedIndex++ ] = data[ rightIndex++ ];

       else

           while ( leftIndex <= middle1 )

               combined[ combinedIndex++ ] = data[ leftIndex++ ];

       for ( int i = left; i <= right; i++ )

           data[ i ] = combined[ i ];

   }

}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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