2

Mr professor has assigned us the task of writing a custom qucksort algorithm that we must implement using his outline ( I can't write my own from scratch, I must use his). He calls it smartQuickSort, and what makes this algorithm "custom" is that we have to calculate the averages on each side of the pivot point which is then used to sort the array. The algorithm uses a class called SmartQuickSortPivot which has int values left and right to hold the averages on the left/right side respectively.

I've written numerous quick sort algorithms in several languages but I cannot, for the life of me, get this one to sort correctly. I've spent 3 days rewriting and debugging this thing with no success, so i'm really hoping someone could help me out as i'm about to pull all of my hair out. Starting from the "skeleton code" he gave us (which includes commented instructions), this is my latest attempt:

/**
     * split4SmartQuickSort splits the array (from first to last) into two subarrays, left and right, using the
     * provided splitVal. It needs to calculate on the fly the average of all the elements of the left subarray
     * and average of all elements of the right subarray, and store the two averages in the @pivot object.
     * The following implementation is only copy of the code from
     * the split function (from line 247) and you should enhance the function to implement what we need to calculate the averages
     * as the pivot for the left and right subarray.
     *
     * Please be noted that splitVal may not even exist in the array since we choose the average.
     * But this should not impact the correctness algorithm of splitting and sorting.
     * @param first
     * @param last
     * @param splitVal
     * @param leftRightAverages
     * @return
     */
    static int split4SmartQuickSort(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
    {
      int saveF = first;
      int leftAvg = 0;
      int leftCount = 0;
      int rightAvg = 0;
      int rightCount = 0;
      boolean onCorrectSide;

      first++;
      do
      {
        onCorrectSide = true;
        while (onCorrectSide)             // move first toward last
          if (values[first] > splitVal)
            onCorrectSide = false;
          else
          {
            //I think my average calculations here are wrong,
            //but nothing I have tried works correctly 
            leftAvg += first;
            leftCount++;
            first++;
            leftRightAverages.left = leftAvg / leftCount;
            onCorrectSide = (first <= last);
          }

        onCorrectSide = (first <= last);
        while (onCorrectSide)             // move last toward first
          if (values[last] <= splitVal)
            onCorrectSide = false;
          else
          {
            //I think my average calculations here are wrong,
            //but nothing I have tried works correctly 
            rightAvg += last;
            rightCount++;
            last--;
            leftRightAverages.right = rightAvg / rightCount;
            onCorrectSide = (first <= last);
          }

        if (first < last)
        {
          swap(first, last);
          first++;
          last--;
        }
      } while (first <= last);

      swap(saveF, last);
      //I think this is one of my problems. Not sure
      //what I should be returning here
      return last;    
    }

  /**
   * Smart quick sort allows the use of a better splitting value (the pivot value) when to split the array
   * into two. In this algorithm, we will use the average of the array (subarray) of all elements as the pivot.
   *
   * Each call to split (split4SmartQuickSort method), the splitValue will be passed and also the split4SmartQuickSort
   * will return the averages of left subarray and right subarray. The two averages, each will be used for the
   * following calls to smartQuickSort.
   *
   * @param first the first element
   * @param last the last element
   * @param splitVal the pivot value for splitting the array
   */
  static void smartQuickSort(int first, int last, int splitVal)
  {
    if (first < last)
    {
      int splitPoint;
      SmartQuickSortPivot leftRightAverages = new SmartQuickSortPivot();

      splitPoint = split4SmartQuickSort(first, last, splitVal, leftRightAverages);
      if (first <= splitPoint)
      {
        smartQuickSort(first, splitPoint - 1, leftRightAverages.left);
      }
      if (last >= splitPoint)
      {
        smartQuickSort(splitPoint + 1, last, leftRightAverages.right);
      }
    }
  }

Here is the class used to store the averages to the left/right of the pivot point:

public class SmartQuickSortPivot {
    public int left;
    public int right;
}

And finally the main method used for testing:

public static void main(String[] args)
  {
    //initValues();
    printValues();
    System.out.println("values is sorted: " + isSorted());
    System.out.println();

    //quickSort(0, values.length - 1);


    /** you can either compute the average first as the first pivot or simplify choose the first one as the pivot */
    smartQuickSort(0, values.length - 1, values[4]);

    printValues();
    System.out.println("values is sorted: " + isSorted());
    System.out.println();
  }
}

The line I commented out, //quickSort(0, values.length - 1); is the algorithm I wrote that does not include the leftRightAverages object argument but is essentially the same, and it works perfectly, so i'm very confused why I can't get the "custom" smartQuickSort to work. For simplicity, I commented out the initValues() method and instead used a preset array that looks like this:

  static int[] values = {2,5,1,66,89,44,32,51,8,6};   // values to be sorted

Things I've tried (and failed at):

1.) Move the lines leftRightAverages.left = leftAvg / leftCount; , leftRightAverages.right = rightAvg / rightCount; outside of the do-while loop, which (I think) due to the recursive nature of the function, eventually gives me a divide by zero RTE.

2.) Change the return value of split4SmartQuickSort() from last to different combinations of rightLeftAverages.left and rightLeftAverages.right, which causes a stack overflow from the recursion. This is where I am really confused, as I'm not exactly sure what this method should be returning in this particular implementation of quick sort (and more importantly, how to properly calculate it).

I think my issue here is twofold; I'm either not correctly calculating the averages on each side of the pivot (I've used numerous pivot points and none of them seem to make a difference), and I'm not returning the proper calculation from the split4SmartQuickSort() method itself. If I remove the rightLeftAverages object from the method argument and use a more traditional approach to quick sort, the algorithm works fine. This is why I think those 2 issues I listed are why the algorithm doesn't function correctly. the return value from split4SmartQuickSort() (I think) acts as the new pivot point for sorting, using the splitVal argument as the original pivot point.

Yes this is my homework, but I've put hours of genuine effort into this thing, with no luck. My prof doesn't answer emails over the weekend and his office hours are during one of my other classes, so I have nowhere else to turn.

Improve this question
4
  • A homework problem with a genuine attempt on Stack Overflow /me falls off chair. Great stuff! :-) Commented Apr 15, 2017 at 8:15
  • lol, i'll take that as a compliment! I always try to give a genuine effort before posting on here, as it's only fair to me and the community :) Commented Apr 16, 2017 at 21:29
  • Indeed, but you would be surprised at how many homeworks are left to the last couple of days, are dumped into a question with no effort, and are accompanied by a request for urgent/asap treatment. :=) Commented Apr 16, 2017 at 21:38
  • 1
    Yeah not a problem! I thought about doing that at first, not sure why I changed my mind. Commented Apr 16, 2017 at 21:42

2 Answers 2

Reset to default
3

I think that you have problems with this because it's hard in this case to use one integer split point. Here is why:

Imagine that at some of the algorithm you got 44, 51, 89, 66 to partition with the average of 62.5 ~ 62. If you use 62 as pivot element there is uncertainty what to return as a split point (because you can return index 1 or 2 (values 51 or 89 correspondingly)).

Let's suppose that you pick 2. This will lead to invalid algorithm (let's remember that the split point (pivot) a_j is the point that divides array into two subarrays such for each i < j a_i < a_j and for each k > j a_j < a_k) because 89 !< 66 and cannot be a split point.

What you kind of need to do is to return something in the middle as a split point. To do this you need to return SmartQuickSortPivot object instead of int and use its left/right values as ending/starting indexes for your left/right arrays.

import java.util.Arrays;

public class Temp {
    public static class SmartQuickSortPivot {
        public int left;
        public int right;
    }

    static int[] values = {2,5,1,66,89,44,32,51,8,6};   // values to be sorted


    /**
     * split4SmartQuickSort splits the array (from first to last) into two subarrays, left and right, using the
     * provided splitVal. It needs to calculate on the fly the average of all the elements of the left subarray
     * and average of all elements of the right subarray, and store the two averages in the @pivot object.
     * The following implementation is only copy of the code from
     * the split function (from line 247) and you should enhance the function to implement what we need to calculate the averages
     * as the pivot for the left and right subarray.
     *
     * Please be noted that splitVal may not even exist in the array since we choose the average.
     * But this should not impact the correctness algorithm of splitting and sorting.
     * @param first
     * @param last
     * @param splitVal
     * @param leftRightAverages
     * @return
     */
    static SmartQuickSortPivot split4SmartQuickSort(int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
    {
        int i = first,j = last;
        int sumLeft = 0;
        int sumRight = 0;
        while (i < j) {
            while (values[i] < splitVal){
                sumLeft += values[i];
                i++;
            }

            while (values[j] > splitVal){
                sumRight += values[j];
                j--;
            }

            if (i < j) {
                swap(i, j);
            }
        }
        leftRightAverages.left = (i - first == 0) ? values[first] : sumLeft / (i - first);
        leftRightAverages.right = (last - j == 0) ? values[last] : sumRight / (last - j);

        SmartQuickSortPivot smartQuickSortPivot = new SmartQuickSortPivot();
        smartQuickSortPivot.left = i;
        smartQuickSortPivot.right = j;
        return smartQuickSortPivot;
    }

    private static void swap(int i, int j) {
        int temp = values[i];
        values[i] = values[j];
        values[j] = temp;
    }

    /**
     * Smart quick sort allows the use of a better splitting value (the pivot value) when to split the array
     * into two. In this algorithm, we will use the average of the array (subarray) of all elements as the pivot.
     *
     * Each call to split (split4SmartQuickSort method), the splitValue will be passed and also the split4SmartQuickSort
     * will return the averages of left subarray and right subarray. The two averages, each will be used for the
     * following calls to smartQuickSort.
     *
     * @param first the first element
     * @param last the last element
     * @param splitVal the pivot value for splitting the array
     */
    static void smartQuickSort(int first, int last, int splitVal)
    {
        if (first < last)
        {
            SmartQuickSortPivot splitPoint;
            SmartQuickSortPivot leftRightAverages = new SmartQuickSortPivot();

            splitPoint = split4SmartQuickSort(first, last, splitVal, leftRightAverages);
            if (first < splitPoint.left)
            {
                smartQuickSort(first, splitPoint.left - 1, leftRightAverages.left);
            }
            if (last > splitPoint.right)
            {
                smartQuickSort(splitPoint.right + 1, last, leftRightAverages.right);
            }
        }
    }

    public static void main(String[] args)
    {

        /** you can either compute the average first as the first pivot or simplify choose the first one as the pivot */
        smartQuickSort(0, values.length - 1, values[5]);
        System.out.println(Arrays.toString(values));
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you so much for taking the time to try and work this out with me. Your reasoning is very sound, and seeing it explicitly explained the way you did shows me the flaws in my logic that I was not able to see (which is very important to me). I'm going to play around with this and report back. Thanks again, I would give you 10 upvotes if I could :)
Interesting thing i've found is that it works great when no duplicates are present, but does not work with duplicates. I'll play with the code to see if I can find out why,
1

Thanks to the great advice below, I got the algorithm working, but it still was not sorting duplicates correctly (infinite loop when dupes encountered). After playing with the code, I now have a complete working algorithm. The change was in the split4SmartQuickSort() only, so here is that method updated:

static SmartQuickSortPivot split4SmartQuickSort
                    (int first, int last, int splitVal, SmartQuickSortPivot leftRightAverages)
    {
      int f = first;
      int l = last;
      int sumLeft = 0;
      int sumRight = 0;

      while (f < l)
      {
        while (values[f] < splitVal)
        {
          sumLeft += values[f];
          f++;
        }

        while (values[l] > splitVal)
        {
          sumRight += values[l];
          l--;
        }

        if (f <= l)
        {
          swap(f, l);

          //handling duplicates in the list
          if (values[f] == values[l])
          {
            f++;
          }
        }
      }

      if (f - first == 0)
      {
        leftRightAverages.left = values[first];
      }
      else
      {
        leftRightAverages.left = sumLeft / (f - first);
      }

      if (last - l == 0)
      {
        leftRightAverages.right = values[last];
      }
      else
      {
        leftRightAverages.right = sumRight / (last - l);
      }

      //create SmartQuickSortPivot object to be returned. Used in
      //smartQuickSort as the split point for sorting
      SmartQuickSortPivot sqsp = new SmartQuickSortPivot();
      sqsp.left = f;
      sqsp.right = l;
      return sqsp;

    }

And finally, the smartQuickSort() algorithm:

static void smartQuickSort(int first, int last, int splitVal)
  {
    if (first < last)
    {
      SmartQuickSortPivot splitPoint;
      SmartQuickSortPivot leftRightAverages = new SmartQuickSortPivot();

      splitPoint = split4SmartQuickSort(first, last, splitVal, leftRightAverages);
      if (first <= splitPoint.left)
      {
        smartQuickSort(first, splitPoint.left - 1, leftRightAverages.left);
      }
      if (last >= splitPoint.right)
      {
        smartQuickSort(splitPoint.right + 1, last, leftRightAverages.right);
      }
    }
  }

Thanks again to @shyyko-serhiy, as they deserve most of the credit for getting this thing working :)

Improve this answer

2 Comments

Thanks for moving this. Just so you know, while you are welcome to keep the 'tick' mark if you wish (say if your answer builds on someone else's work and is therefore a better answer) but some askers will self-answer like this, but will let the other person keep the tick. This is because they get +15 for the tick, but a self-awarded tick gets +0. Nevertheless, it is up to you.
id rather give the credit where it is due, so I will change it. I wasn't sure what the procedure was there. thanks for all the help!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.