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 &))
    typename SinglyLinkedList<T>::iterator itBegin itEnd;
     itBegin = A.begin();
     itEnd = A.end();
     int max = size();
     int pivot = A.begin;
        if(max <= 1)
        while(itBegin < itEnd)
          while(itBegin < pivot)
          while(itEnd > pivot)
          if(itBegin <= itEnd)
              Node *tmp = itBegin;
              itBegin = itEnd;
              itEnd = tmp;
6 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.