Help In Solving Algorithm

Question

Hi Guys,

Am suppose to return the number of character comparisons. In the while() loop i compare the index of the characters and update the counter. My question is, is it right to do it that way or i have to compare the characters themselves. I think comparing the index and updating the counter is the same as comparing the characters themselves. Any idea?

Need help.

The following is the code of the algorithm.

    // Sort an array of strings using quick sort
   // Always pivot on the first element
   // Return the number of CHARACTER comparisons

  public int stringQuickSort(ComparableByte[][] strings) {
      Counter nCompares = new Counter();
      sortStringQuickSort(strings, 0, strings.length-1, 0, nCompares, false);
    return nCompares.value;
  }

  public void sortStringQuickSort(ComparableByte[][] strings, int lo, int hi, int d, Counter nCompares, boolean switchToOtherAlgorithm){
      if(!switchToOtherAlgorithm){
      if(hi <= lo)
          return;
      }else if(hi <= lo+10){

              stringInsertionSort(strings);
          return;
      }
      int lt = lo, gt = hi;
      int v = characterAt(ComparableByte.toString(strings[lo]), d);
      int i = lo+1;

      while(i <= gt){
          int t = characterAt(ComparableByte.toString(strings[i]), d);
          nCompares.value++;
          if (t < v){
              swapTwoComparableByteElements(strings, lt++, i++);
              nCompares.value++;
          }
          else if(t > v){
              swapTwoComparableByteElements(strings, i, gt--);
          }
          else 
              i++;
      }

      sortStringQuickSort(strings, lo, lt-1, d, nCompares, switchToOtherAlgorithm);
      if(v >= 0){
          sortStringQuickSort(strings, lt, gt, d+1, nCompares, switchToOtherAlgorithm);
      }
      sortStringQuickSort(strings, gt+1, hi, d, nCompares, switchToOtherAlgorithm);
  }

Thanks for your help

Answer 1

Usually these things are used to provide an empirical estimate of comparisons needed by algoritms to study if the expected behaviour is correct.

So, yes, it doesn't matter exactly what you count if you take care to count the correct operations. You don't care if they are characters of indices as long as you are actually counting whenever you program needs to compute a < > <= >= = operation related to the input and the current implementation.