Modify code to count the number of swaps and comparisons import java.util.Random

Question

Modify code to count the number of swaps and comparisons
import java.util.Random;

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

public QuickSort( int size ) {
data = new int[ size ]; // create space for array

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

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

private void quickSortHelper( int left, int right ) {
int pivot = partition( left, right );

if ( left < pivot - 1 )
quickSortHelper( left, pivot - 1 );

if ( pivot + 1 < right )
quickSortHelper( pivot + 1, right );
}

private int partition( int left, int right ) {
int pivot = left;

while ( true ) {
while ( data[ right ] >= data[ pivot ] ) {
if ( right == pivot )
return pivot;

--right;
}

swap( pivot, right );

pivot = right--;

while ( data[ left ] <= data[ pivot ] ) {
if ( left == pivot )
return pivot;

++left;
}

swap( pivot, left );
pivot = left++;
}
}

private void swap( int first, int second ) {
int temporary = data[ first ];
data[ first ] = data[ second ];
data[ second ] = temporary;
}
}

Explanation / Answer

updated this cose to count the number of swaps and comparisons . i

import java.util.Random;

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

private int c1,s;

private int c2 ;

public QuickSort( int size ) {
data = new int[ size ]; // create space for array

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

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

private void quickSortHelper( int left, int right ) {
int pivot = partition( left, right );

if ( left < pivot - 1 )
quickSortHelper( left, pivot - 1 );

if ( pivot + 1 < right )
quickSortHelper( pivot + 1, right );
}

private int partition( int left, int right ) {
int pivot = left;

while ( true ) {
while ( data[ right ] >= data[ pivot ] ) {
if ( right == pivot )
return pivot;

c1= c1 + 1;

   --right;

}

swap( pivot, right );

pivot = right--;

while ( data[ left ] <= data[ pivot ] ) {
if ( left == pivot )
return pivot;

c2 = c2 + 1;

++left;
}

swap( pivot, left );
pivot = left++;
}
}

private void swap( int first, int second ) {
int temporary = data[ first ];
data[ first ] = data[ second ];
data[ second ] = temporary;

s=s + 1;

}
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

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