this is a quick sort function that receives a singly linked list and a function pointer that is called before it has to be done recursive function. this is what i have so far

``````template <typename T>
void quicksort(SinglyLinkedList<T> & A, bool (* before)(T &, T &))
{

itBegin = A.begin();
itEnd = A.end();
int max = size();
int pivot = A.begin;

if(max <= 1)
{return;}
while(itBegin < itEnd)
{
while(itBegin < pivot)
{
itBegin++;
}
while(itEnd > pivot)
{
itEnd--;
}
if(itBegin <= itEnd)
Node *tmp = itBegin;
itBegin = itEnd;
itEnd = tmp;
}
while()
quicksort(,)
}``````
2
Contributors
1
2
Views
7 Years
Discussion Span
Last Post by griswolf

And "the little problem" is what? I see several candidates:

• line 2: Why return void when you can return something useful (there may be a good reason, but a comment might help)
• line 15: I think you want `while(*itBegin < *pivot)`
• line 17: You are not looking at the before-you-incremented value, so use `++itBegin` It cannot be more expensive and may be less
• line 19: (irrelevant, but) see comment about line 15
• line 21: There is no `operator--` for SinglyLinkedList<T>::iterator
• line 23: Do you want if here or while?
• lines 28,29: seem kind of empty :)
• line 31 and on: I see no use of the `before` function.
• lines 2 through 30: Where is the recursion?

From your description, I don't know how `before` is used. Is it called before every comparison? Before the function is first called? Before every swap? before each recursion? If you don't know what code is supposed to do, it is impossible(*) to make it do it
Recursion: If it were my code, I'd partition the list into two lists, then call the function on each of the two, then merge them back together with pivot between. Question: Can you do that "in place" as quicksort is supposed to work?
Meta question: Is quicksort a good idea for singly linked lists? Why or why not?
-----------------------
(*)Well, I suppose the odds are only 1/factorial(number_of_characters_in_the_code) or something like that; not quite exactly 0.

Edited by griswolf: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.