PREV INDEX NEXT

Author: Unknown
Subject: Infinite Loop (ignore first incomplete message)
Date: Sunday, 29 Mar 2020, 09:57:54

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, for which the only solution I see is choosing a random splitter each time, which I don't know how to do without: 

"read the i-th item, transfer i-1 items from the head of the Deque to the
   tail; transfer 1 item from head to tail, making a copy to return to
   quickSort; and then transfer n-i items from head to tail, restoring the
   status quo"

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, so I should want to randomize or at least change the splitters to ensure the deque gets sorted correctly. How would I do that without simulating a random access array?
PREV INDEX NEXT