stuck at quicksort

[wigga]

Sometimes i get random 0 values in my array.
and also sometimes it doesnt sort so well, givng me adbce isntead of abcde
but overal it did it pretty good job for me. theres just some bugs but i cant find them.

here is the websites i have been looking at:

http://en.wikipedia.org/wiki/Quicksort
http://mathbits.com/mathbits/compsci/Arrays/Quick.htm

inline void Swap(int& one, int& two)
	{
		one ^= two;
		two ^= one;
		one ^= two;
	}

template<typename Func, typename Iter>
	inline Iter Partition(Iter begin, Iter end, Iter pivot, Func func = Func())
	{
		if(end - begin > 2)
		{
			Swap(*pivot, *(--end));
			pivot = end;
			for(; ; ++begin)
			{
				for(; begin != end && func(*begin, *pivot); ++begin);
				if(begin == end)
					break;
				for(; begin != --end && !func(*end, *pivot); );
				if(begin == end)
					break;
				Swap(*begin, *end);
			}
			Swap(*begin, *pivot);
		}
		return begin;
	}

template<typename Func, typename Iter>
	inline void QuickSort(Iter begin, Iter end, Func func = Func())
	{
		if(begin < end)
		{
			Iter mid = Partition(begin, end, begin, func);
			QuickSort(begin, mid, func);
			QuickSort(mid + 1, end, func);
		}
	}

struct SortLess
{
	template<typename T>
	inline bool operator ()(T& a, T& b)
	{
		return a < b;
	}
};

int main()
{
	int sort[] = {1,2,3,4,5,6,7,8,9,20,11,12,13,15, 30, 9, 8, 7, 6, 5,4};
	QuickSort<SortLess>((int*)sort, (int*)sort + sizeof(sort) / sizeof(int));
}

[Lindley]

You need to make sure you're being consistent about whether "end" is the last item or one past the last item. Your "--end" in Partition() suggests the latter; however, your two recursive Quicksort() calls seem to be indicating the former. Pick one and stick with it throughout, or you'll just confuse yourself.

[wigga]

are you saying that mid is actually the last element instead of the end element?

[Lindley]

Hmm....well, if I think about it in terms of mid staying where it is, then the objection goes away.

[wigga]

i dont see anything wrong with the usage of mid and end.

the problem must lay somewhere within partition function and i also think it has something todo with this line for one

		if(end - begin > 2)

cause its not sorting 2 elements, but i get confused how to sort 2 element with the pivot swapping around

[Lindley]

Well, let's think about it. The reason for swapping the pivot out of position is so that it doesn't take part in the partitioning process. You would then swap it back into position at the end. You must ensure that what you're swapping it with is actually >= the pivot (if you stored it at the end in the meantime) or <= the pivot (if you stored it at the start).

In the case of only 2 elements, all you need to ensure is that they're in sorted order. There isn't even a need for a pivot, per se. You can easily special case that using a swap-if-necessary.

[wigga]

oops i saw one mistake. dint decrease end after swapping pivot to last.

but its still wrong..
qwertyuiopasdfghjklzxcvbnm
gets sorted into
abdecgijklhmoqpfsutrxvwyzn


i really have no idea what is wrong now

i tested the partition function once. and it does its partitioning well, there must be one scenario where it doesnt go well

here the code now.

	template<typename Func, typename Iter>
	inline Iter Partition(Iter begin, Iter end, Iter pivot, Func func = Func())
	{
         --end;//yer right maybe use first, last
		if(end - begin > 1)
		{
			Swap(*pivot, *end);
			pivot = end;
			--end;
			for(; ; ++begin)
			{
				for(; begin != end && func(*begin, *pivot); ++begin);
				if(begin == end)
					break;
				for(; begin != --end && !func(*end, *pivot); );
				if(begin == end)
					break;
				Swap(*begin, *end);
			}
			Swap(*begin, *pivot); here must be the error
		}
		else if(end - begin > 0)
		{
			if(!func(*begin, *end))
				Swap(*begin, *end);
		}
		return begin;
	}

[Martin O]

but its still wrong..
qwertyuiopasdfghjklzxcvbnm
gets sorted into
abdecgijklhmoqpfsutrxvwyzn

I'd try to find the smallest possible string that shows the problem. Then I'd debug the code instead of just guess, and see exactly where & why the code didn't do what I expected.

[JVene]

Try this one

inline void Swap(int& one, int& two)
	{
		int t = two;
		two = one;
		one = t;
	}

	template<typename Func, typename Iter>
	inline Iter Partition(Iter begin, Iter end, Iter pivot, Func func = Func())
	{
         --end;//yer right maybe use first, last
		if(end - begin > 1)
		{
			Swap(*pivot, *end);
			pivot = end;
			--end;
			for(; ; ++begin)
			{
				for(; begin != end && func(*begin, *pivot); ++begin);
				if(begin == end)
					break;
				for(; begin != end && !func(*end, *pivot); --end);
				if(begin == end)
					break;
				Swap(*begin, *end);
			}
			Swap(*begin, *pivot); //here must be the error
		}
		else if(end - begin > 0)
		{
			if(!func(*begin, *end))
				Swap(*begin, *end);
		}
		return begin;
	}

template<typename Func, typename Iter>
	inline void QuickSort(Iter begin, Iter end, Func func = Func())
	{
		if(begin < end)
		{
			Iter mid = Partition(begin, end, begin, func);
			QuickSort(begin, mid, func);
			QuickSort(mid + 1, end, func);
		}
	}

struct SortLess
{
	template<typename T>
	inline bool operator ()(T& a, T& b)
	{
		return a < b;
	}
};

	int sort[] = {81,62,73,34,95,106,117,128,139,20,11,12,13,15, 30, 9, 8, 7, 6, 5,4};

int wgmain()
{
	QuickSort<SortLess>((int*)sort, (int*)sort + (sizeof(sort) / sizeof(int)) );

  return 0;
}

Here's what I changed...

First, I use VS2008 and drop other projects into a 'skeleton' - which calls your main, now renamed wgmain() - please return that to main or whatever you require.

I moved the array out to global space only to aid debugging view of the data, nothing more.

I'd prefer not to use names that might coincide with known names from the STL, like sort, but that's just an observation.

inline void Swap(int& one, int& two)
	{
		one ^= two;
		two ^= one;
		one ^= two;
	}

Mine is a basic integer swap. The a ^= b is cute, but isn't widely used, can't be used with all types, and isn't always faster (my tests suggest it can be around 20&#37; slower or worse).



Anyway, that didn't fix anything until

for(; begin != end && !func(*end, *pivot); --end);


The original wasn't quite 'on' the point.


The output of the data set I provided was correctly sorted with this example.

Subsequent tests tell me it's not entirely fixed yet

Hope that helps...

[wigga]

I'd try to find the smallest possible string that shows the problem. Then I'd debug the code instead of just guess, and see exactly where & why the code didn't do what I expected.

hi martin. i have been doing this for hours now and i am really exhausted.


jvene thanks alot for helping me

just for the ease of not having to swap the pivot to the end. i took this approach: (when this works i could also fix the other function )

	template<typename Func, typename Iter>
	inline void QuickSort(Iter begin, Iter end, Func func = Func())
	{
		if(end - begin > 2)
		{
			Iter first = begin + 1;
			Iter last = end - 1;
                        //pivot = begin
			while(true)
			{
				while(first != last)
				{
					if(func(*last, *begin))
						break;
					--last;
				}
				while(first != last)
				{
					if(!func(*first, *begin))
						break;
					++first;
				}
				if(first == last)
				{
					--first;
					break;
				}
				Swap(*first, *last);
			}
			if(first != begin)
				Swap(*begin, *last);
                          // else the pivot should stay in place cause there was nothing swapped
			QuickSort(begin, last, func);
			QuickSort(last + 1, end, func);
		}
		else if(end - begin > 1)
		{
			--end;
			if(!func(*begin, *end))
				Swap(*begin, *end);
		}
	}

qwertyuiopasdfghjklzxcvbnm
is sorted into
ahcbdefigjklmnopqsrtuvwxyz

i am to tired to think now. good nite!

[Lindley]

Reducing the number of functions is definitely moving in the wrong direction! That won't help you solve anything. Keep Partition separate.

Hmmm.....if Partition is the problem, then you should focus on that. Add output statements telling you for each run:

1) The value of the pivot
2) The entire array of values between begin and end just before the function returns.
3) Which index is being returned.

You should be able to spot where it doesn't seem correct (everything before the returned index (which is the pivot) is smaller, everything after is larger). That should immediately give you a clue as to what's wrong.

[JVene]

At the risk of changing too much, try this (it works under several tests).

It's based on the partition you linked as a reference

I've only posted partition, quicksort functions, a changed call to quicksort (minor but important) and some test data that revealed earlier trouble

template<typename Func, typename Iter>
inline Iter Partition(Iter begin, Iter end, Iter pivot, Func func = Func())
{
    --begin;
    ++end;

    do { 
         do {
             --end;
            } while( func( *pivot, *end ) );

         do {
             ++begin;
            } while( func( *begin, *pivot ) );

         if ( begin < end ) Swap( *begin, *end );

       } while( begin < end );

    return end;
}


// this is unchanged

template<typename Func, typename Iter>
inline void QuickSort(Iter begin, Iter end, Func func = Func())
{
  if(begin < end)
		{
			Iter mid = Partition(begin, end, begin, func);
			QuickSort(begin, mid, func);
			QuickSort(mid + 1, end, func);
		}
}


.....in main.....

QuickSort<SortLess>((int*)sort, (int*)sort + (sizeof(sort) / sizeof(int) - 1 ) );


........last sample data I tried

	int sort[] = {501,502,503,504,505,506,507,508,209,510,511,512,1024,2048,1025,1026,2037,30,291,109,221,237,326,945,41,1,31,36,37,801,732,81,62,73,34,95,106,117,128,139,20,11,12,13,15, 30, 9, 8, 7, 6, 5,4};

Here's the change...

Other than switching to a different partition,

The call to quicksort now puts the "end" mark at the end, not at the end plus 1 (note the - 1 at the tail of the call to quicksort).

You might also enjoy a proof loop

 int *ptr = sort;
 int *lim = sort + (sizeof(sort) / sizeof(int));

 while( ptr < lim -1 )
    {
     if ( *ptr > *(ptr+1) )
        {
         printf("Error at &#37;d, %d\n", *ptr, *(ptr+1) );
        }

     ++ptr;
    }

I've added entries to the array several times, had a few problems along the way, but now after about 10 runs with 'more' data each time, it proves correct and doesn't include 'ghost' entries.

It seems that your earlier work was being befuddled because the initial call is made with end + 1 (end was one beyond the data to begin with). This caused the first pass of partition to work differently than subsequent calls due to recursion, which led to a "ghost" zero (in debug, garbage in release) creeping in that wasn't really in the data, and giving odd ordering on occasion probably from the corrections you've been making due in reality to the difference between the first call and subsequent recursive calls to partition. Now the first and subsequent recursive calls consider the end the end, not end+1, and it works as expected so far as I can see.

If you want to call with end+1, which I think is like some other versions, you'd need an "outer" function for calling the sort, consider this QuickSort to be interior only.

[wigga]

hi.. thanks alot for helping me i really apreciate it.

there is one scenario that scores me in this loop:

         do {
             --end;
            } while( func( *pivot, *end )

what if the data looks like this:
zzzzzzzzzzzzzzzzzzzz
and im afraid it will go out the boundaries and create UB

OK

it works now.. but im really confused and i dont want to think about it anymore...

	template<typename Func, typename Iter>
	inline Iter Partition(Iter first, Iter last, Iter pivot, Func func = Func())
	{
		--first;
		++last;
		do
		{
			do
			{
				--last;
			} while(first < last && func(*pivot, *last));
			do
			{
				++first;
			} while(first < last && func(*first, *pivot));
			if(first < last)
				Swap(*first, *last);
		} while(first < last);
		return last;
	}

	template<typename Func, typename Iter>
	inline void QuickSort(Iter first, Iter last, Func func = Func())
	{
		if(first < last)
		{
			Iter mid = Partition(first, last, first, func);
			QuickSort(first, mid, func);
			QuickSort(mid + 1, last, func);
		}
	}

however when i call partition directly.(taking 'q' as the pivot)
qwertyuiopasdfghjklzxcvbnm
is partitioned into.
mbeclkjihgafdspouytzxrvwnq

the bold parts are obviously incorrect.

the way i wanted this algorithm to work was as in the image on wikipedia, i thought it would work faster. maybe im wrong.
because the pivot is actually ON the pivot / center. and ofcourse two groups true and false. somehow s and n are not correctly positioned when calling the partitiion function directly, and i am conffused how they get correctly positioned when calling quicksort

maybe i could create them seperatly:

	template<typename Func, typename Iter>
	inline Iter Partition(Iter first, Iter last, Iter pivot, Func func = Func())
	{
//stuff todo
	}

	template<typename Func, typename Iter>
	inline void QuickSort(Iter first, Iter last, Func func = Func())
	{
	struct __QuickSort__ // ugly function in function hack, to preserve namespace.
	{
        static inline Iter Partition(Iter first, Iter last, Iter pivot, Func func)
           {
		--first;
		++last;
		do
		{
			do
			{
				--last;
			} while(first < last && func(*pivot, *last));
			do
			{
				++first;
			} while(first < last && func(*first, *pivot));
			if(first < last)
				Swap(*first, *last);
		} while(first < last);
		return last;
	   }
         };//__QuickSort__

		if(first < last)
		{
			Iter mid = __QuickSort__::Partition(first, last, first, func);
			QuickSort(first, mid, func);
			QuickSort(mid + 1, last, func);
		}
	}

Reducing the number of functions is definitely moving in the wrong direction! That won't help you solve anything. Keep Partition separate.

You are right. its because the stack will grow bigger faster right? cause of the registers taking more space?and with partition in a function they will release sooner?

Hmmm.....if Partition is the problem, then you should focus on that. Add output statements telling you for each run:

1) The value of the pivot
2) The entire array of values between begin and end just before the function returns.
3) Which index is being returned.

You should be able to spot where it doesn't seem correct (everything before the returned index (which is the pivot) is smaller, everything after is larger). That should immediately give you a clue as to what's wrong.

thats a really good idea. and i am doing that now, thanks

[JVene]

what if the data looks like this:
zzzzzzzzzzzzzzzzzzzz
and im afraid it will go out the boundaries and create UB

It can't. The test is < or it can be >, since any two of these would fail, the loop would stop. Quicksort can't accept <= or >= as tests, that's a caveat of the algorithm.

I haven't considered the rest of your post yet, but I thought I'd respond to that point and ask...are you saying the version I posted didn't work?


edit:

			do
			{
				--last;
			} while(first < last && func(*pivot, *last));
			do
			{
				++first;
			} while(first < last && func(*first, *pivot));

I'm sure there are lots of performance considerations available - there are a few variations discussed in the literature which have been the result of many years of research. However, the test for first < last is not necessary. I understand the concern, but unless something else was wrong, the test for first < last should never need be part of the algorithm. It isn't in the text example, and that works under a number of conditions, this would slow an interior loop with two tests when one should do. The loops will stop because of the nature of the comparison to pivot (which is begin relative to the partition under consideration).

You are right. its because the stack will grow bigger faster right? cause of the registers taking more space?and with partition in a function they will release sooner?

At the risk of speaking for Lindley (which I'm not trying to do), I'm fairly sure his point, at least as I read it, is about the scientific process. Changing too much at once risks two things: introducing more problems, and obfuscating what happened to actually fix the problem.



It might help me to understand what your goals are here, as I'm a bit confused. I can understand the nature of researching quicksort, the study is a CS classic. Is this purely a research project?

The STL sort is a quicksort for vector which already has most of the classic knowledge embedded with the solution, but there can be reasons to want for a specialization - is this related to your interest?

The reason I ask is that the "median of 3" selection for the algorithm is a classic algorithmic advance on the concept, along with a few other little nuances I'm happy to have forgotten, and I think the algorithm here is the "basic" version which takes no measure into account for worst case scenarios - but you might not ever present worst case data such that it's not as important.

Do you have performance goals you might let us in on? They can be highly relative to the data/storage/nature of the challenge your working on. How, for example, have you measured that it's not as fast as you expected?

[Lindley]

You are right. its because the stack will grow bigger faster right? cause of the registers taking more space?and with partition in a function they will release sooner?

Nah, nothing to do with that. It's just always easier to verify correctness of a small function than a large one. So wrapping up the most tricky part of an algorithm in a function and then verifying *that* is correct is the best way to get the entire algorithm correct.