Author: Stan Eisenstat
Subject: Re: [Cs223] Infinite Loop (ignore first incomplete message)
Date: Sunday, 29 Mar 2020, 12:46:55

    > Message Posted By: Unknown
    >
    > We should not be using the deques to simulate random access arrays in
    > order to choose a splitter. As a result, I am always choosing my splitter
    > to be the first line of the deque I am sorting. However, I am getting
    > caught in an infinite loop, ...

That is not possible if you have implemented quickSort
correctly.  Recall that without the requirement that the
sort be stable, the algorithm is:

(Base Case) If N = 1, the list is already sorted.

(Divide) Choose a spliiter S and assign every OTHER item
  to the LT (<= S) and a GT (> S) group.

(And) Sort the LT group and the GT group.

(Conquer) Return the concatenation the sorted LT group,
  S, and the GT group.

No matter how you choose the splitter, the number of
items to sort on each recursive call is at most N-1,
which means that the recursion cannot be infinite.

Note: Stability may require putting elements that are
equal to S in GT rather than LT.
=====

    ...
    > My infinite loop is occurring when after running quicksort on a deque
    > (containing more than one element), all the elements from the deque I was
    > sorting have been transferred to one of the other deques (in the same
    > order). My understanding is that I still do need to be sorting this deque
    > because it still contains more than one element, and the splitter's ASCII
    > value might have been lower or higher than all the other elements so the
    > deque might still actually be unsorted. Therefore, the problem in my code
    > is probably coming from the fact that I am always using the same splitter,

As you can see from the description above, the splitter
S is NOT part of LT or GT and thus cannot be reused as a
splitter.

If you would like me to look at your code, you will have
to mail me directly.

--Stan-