3 Replies - 7521 Views - Last Post: 26 February 2011 - 10:19 PM Rate Topic: -----

#1 dunsta  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 79
  • Joined: 08-April 10

count swap/comparisons in sort methods

Posted 26 February 2011 - 09:56 PM

Hi,
I have modified sort methods to count the number of swaps and comparisons each one does.
I have 4 methods: Bubble, Insertion, Selection and Quick sort.
Can you take a look to see if I am counting the swaps and comparisons correctly.
I will post one at a time, so I am not posting too much code at once.

/**
   The IntQuickSorter class provides a public static
   method for performing a QuickSort on an int array.
*/

public class IntQuickSorter
{
	public static int compare =0, swap=0;
  /**
      The quickSort method calls the doQuickSort method
      to sort an int array.
      @param array The array to sort.
   */
   
   public static void quickSort(int array[])
   {
      doQuickSort(array, 0, array.length - 1);
      System.out.println("Quick sort swap: "+swap+" compare: "+compare);
   }

   /**
      The doQuickSort method uses the QuickSort algorithm
      to sort an int array.
      @param array The array to sort.
      @param start The starting subscript of the list to sort
      @param end The ending subscript of the list to sort
   */
   
   private static void doQuickSort(int array[], int start, int end)
   {
   	
      int pivotPoint;
      
      if (start < end)
      {
         // Get the pivot point.
         pivotPoint = partition(array, start, end);
         
         // Sort the first sub list.
         doQuickSort(array, start, pivotPoint - 1);
         
         // Sort the second sub list.
         doQuickSort(array, pivotPoint + 1, end);
      }
   }

   /**
      The partiton method selects a pivot value in an array
      and arranges the array into two sub lists. All the
      values less than the pivot will be stored in the left
      sub list and all the values greater than or equal to
      the pivot will be stored in the right sub list.
      @param array The array to partition.
      @param start The starting subscript of the area to partition.
      @param end The ending subscript of the area to partition.
      @return The subscript of the pivot value.
   */
   
   private static int partition(int array[], int start, int end)
   {
      int pivotValue;    // To hold the pivot value
      int endOfLeftList; // Last element in the left sub list.
      int mid;           // To hold the mid-point subscript

      // Find the subscript of the middle element.
      // This will be our pivot value.
      mid = (start + end) / 2;

      // Swap the middle element with the first element.
      // This moves the pivot value to the start of 
      // the list.
      swap(array, start, mid);

      // Save the pivot value for comparisons.
      pivotValue = array[start];
      
      // For now, the end of the left sub list is
      // the first element.
      endOfLeftList = start;
      
      // Scan the entire list and move any values that
      // are less than the pivot value to the left
      // sub list.
      for (int scan = start + 1; scan <= end; scan++)
      {
      	compare++;
         if (array[scan] < pivotValue)
         {
            endOfLeftList++;
            swap(array, endOfLeftList, scan);
         }
      }
      
      // Move the pivot value to end of the
      // left sub list.
      swap(array, start, endOfLeftList);
      
      // Return the subscript of the pivot value.
      return endOfLeftList;
   }

   /**
      The swap method swaps the contents of two elements
      in an int array.
      @param The array containing the two elements.
      @param a The subscript of the first element.
      @param b The subscript of the second element.
   */
   
   private static void swap(int[] array, int a, int B)/>
   {
      int temp;
      
      temp = array[a];
      
      array[a] = array[b];
      swap++;
      array[b] = temp;
      
   }
}



Thanks for taking a look

Is This A Good Question/Topic? 0
  • +

Replies To: count swap/comparisons in sort methods

#2 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:08 PM

You're missing a comparison here in your doQuicksort() method: if (start < end). Looks good to me otherwise.
Was This Post Helpful? 1
  • +
  • -

#3 dunsta  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 79
  • Joined: 08-April 10

Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:18 PM

thanks macosxnerd101,
You have helped me quite a lot over the last year. :)
and Insertion sort...
/**
   The IntInsertionSorter class provides a public static
   method for performing an insertion sort on an int array.
*/

public class IntInsertionSorter
{

   /**
      The insertionSort method performs an insertion sort on
      an int array. The array is sorted in ascending order.
      @param array The array to sort.
   */

   public static void insertionSort(int[] array)
   {
   	int swap = 0;
   	int compare = 0;
      int unsortedValue;  // The first unsorted value
      int scan;           // Used to scan the array
      
      // The outer loop steps the index variable through 
      // each subscript in the array, starting at 1. This
      // is because element 0 is considered already sorted.
      for (int index = 1; index < array.length; index++)
      {
         // The first element outside the sorted subset is
         // array[index]. Store the value of this element
         // in unsortedValue.
         unsortedValue = array[index];
         
         // Start scan at the subscript of the first element
         // outside the sorted subset.
         scan = index;
         
         // Move the first element outside the sorted subset
         // into its proper position within the sorted subset.
         
         while (scan > 0 && array[scan-1] > unsortedValue)
         {
            array[scan] = array[scan - 1];
            scan--;
            swap++;
            compare++;
         }
         
         // Insert the unsorted value in its proper position
         // within the sorted subset.
         array[scan] = unsortedValue;
         swap++;

      }
      System.out.println("Insertion sort swap: "+swap+" compare: "+compare);
   }
}

Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10567
  • View blog
  • Posts: 39,121
  • Joined: 27-December 08

Re: count swap/comparisons in sort methods

Posted 26 February 2011 - 10:19 PM

Do you want to count the conditions in the loop as two comparisons or one? Looks good to me otherwise.
while (scan > 0 && array[scan-1] > unsortedValue)


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1