Add your own alternative version
Stats
119.1K views 221 downloads 48 bookmarked
Posted
19 Jan 2004

Comments and Discussions



I found it was a medium sort (instead of quick) and, more annoyingly for me, it did unnecessary swapping.
So I look on Wikipedia and write this new algorithm based on the Wikipedia implementation http://en.wikipedia.org/wiki/Quicksort
faster and no unnecessary swapping:  /* nums[]  the array whose elements are to be sorted * first  index of the first element to be sorted * last  index of the last element to be sorted */ static void QuickSort<T>(IList<T> nums, int first, int last, Comparison<T> comparison, Swap<T> swap) { int i, left, right, mid; int passes = last  first;
/* Do not run if there is only one element */ if (passes > 0) { /* The following if check and the next loop * set the lowest element at the beginning * and the greatest at the end of the array. */ if (comparison(nums[first], nums[last]) > 0) swap(nums, first, last);
if (passes > 1) { for (i = first + 1; i < last; i++) { if (comparison(nums[i], nums[first]) < 0) swap(nums, i, first); else if (comparison(nums[i], nums[last]) > 0) swap(nums, i, last); }
if (passes > 2) { // choose some arbitrary pivotal value T pivot = nums[(first + last) / 2];
left = first + 1; right = last  1;
/* After following loop (one quicksort pass), * "right" shows the location of pivot element... */ while (left < right) { while (left < right && comparison(nums[left], pivot) <= 0) left++;
while (left < right && comparison(nums[right], pivot) >= 0) right;
if (left < right) swap(nums, left, right);
if (comparison(nums[left], pivot) == 0 && comparison(nums[right], pivot) == 0) left++; }
/* ...and that's why the quicksort is used recursively * on array nums from point "first + 1" to "right  1" and * from point "right + 1" to "last  1". */ QuickSort<T>(nums, first + 1, right  1, comparison, swap); QuickSort<T>(nums, right + 1, last  1, comparison, swap); } } } }





Good morning,
You have done some very good work here Gents!
Very often I do not need to sort an array but I need to get instead the Rank of each element. This is important when I have several other dependant arrays related to the "key" array. So as an example I will have:
X  Rank of X  Y 2  2 (1 is the first element)  2.30 5  0 (2 is the second element)  1.50 1  1 (5 is the third element)  1.10
I often want to sort (X, Y) using X as the sorted element or get the Rank of X so that I know how to get ranked Y.
Then if I do X[Rank[0]] I get the X[2] which is 1 and Y[Rank[0]] = Y[2] = 1.10 X[Rank[1]] I get the X[0] which is 2 and Y[Rank[1]] = Y[0] = 2.30 X[Rank[2]] I get the X[1] which is 5 and Y[Rank[2]] = Y[1] = 1.50
and my data are accessed this way.
Now it seems I cannot do this using your framework very easily. It looks like I have to either duplicate the data into big objects and implement an IComparable interface or alternatively to create a 2D array X, RankX such as
X  Rank[X] 2  0 5  1 1  2 3  3 0  4
and sort the pair using your framework which will give Sorted X  Rank[X]  X[Rank[X]] 1  2  X[Rank[0]] = X[2] = 1 0  4  X[Rank[1]] = X[4] = 0 2  0  X[Rank[2]] = X[0] = 2 3  3  X[Rank[3]] = X[3] = 3 5  1  X[Rank[4]] = X[4] = 4
and then I can use the Rank[] array to access any dependant arrays.
Could you suggest a best way to do this under your current design please? I would like to avoid the duplication of data as much as possible.
Thanks, Michael
 modified at 5:08 Tuesday 24th January, 2006





I would like to note that while quicksort is O(nlogn) this implementation has O(n2) complexity when used on an already sorted array. A random pivot point would solve this problem.





Although reducing the complexity for an already sorted array a random pivot point would make the more likely case of unsorted data slower (although the complexity remains the same). When the project is updated with new algorithms one could probably add this special case as an extension to the quicksort algorithm.







About delegates:
I don't think we should use delegates for a number of reasons:  they are multicasts, which could lead to some strange result  they are a slower than interface function call and sorting is usually a time critical task
Marc Clifton wrote: And thanks for the "nonstatic" version code! I'd actually like to post an updateshall I make you a coauthor?
Yes, of course. I've also added an interface ISorter that defines the sort method. Therefore, we could implement QuickSorter, HeapSorter, RadixSorter, etc...
public interface ISorter
{
void Sort(IList list);
}
Cheers
Jonathan de Halleux.
www.dotnetwiki.org





From what i can find about delegates (mshelp): A delegate is either multicast (combinable) or singlecast (noncombinable). Singlecast or noncombinable delegates invoke exactly one method and cannot be used in combining operations. The invocation list of a singlecast delegate A contains a single element: a reference to A
I understand from this that a delegate is not per definition multicast.
Also by using .Net Reflector I found that:
private static void Invoke(ADelegate tester, int[] array) { tester.Invoke(array); }
and
private static void Invoke(ITester tester, int[] array) { tester.TestInvokation(array); }
produce roughly the same IL:
.maxstack 2 L_0000: ldarg.0 L_0001: ldarg.1 L_0002: callvirt ADelegate.Invoke L_0007: ret
and
.maxstack 2 L_0000: ldarg.0 L_0001: ldarg.1 L_0002: callvirt ITester.TestInvokation L_0007: ret
From the explaination in the help i understand that the Invoke method just holds a reference to the delegate. So if the code is any slower it won't be much.
Robert





I can't find any doc on SingleCastDelegate. To my knowledge, by default inC#, delegate is of MultiCastDelegate type ???
Jonathan de Halleux.
www.dotnetwiki.org







Hi Jonathan,
wow!
Send the classes and unit tests to:
webmaster@knowledgeautomation.com
This'll be a really article, given the additional sorting algorithms! Thanks so much for your efforts. I'll put the revised article together with you as coauthor in a day or two.
Marc
Latest AAL Article My blog Join my forum!





I've inserted the sort algorithms in my QuickGraph library. It would be easier for me if you could download it from my server (http://www.dotnetwiki.org[^]).
The source are in the QuickGraph.Collections.Sort namespace and the tests in the QuickGraphNUnit.Collections namespace.
Cheers
Jonathan de Halleux.
www.dotnetwiki.org





Hi,
I've integrated your quicksort in my QuickGraph application and I've made it nonstatic:
using System;
using System.Collections;
using System.IO;
namespace QuickGraph.Collections
{
public interface ISwap
{
void Swap(IList array, int left, int right);
}
public class DefaultSwap : ISwap
{
public void Swap(IList array, int left, int right)
{
object swap=array[left];
array[left]=array[right];
array[right]=swap;
}
}
public class DefaultComparer : IComparer
{
public int Compare(IComparable x, Object y)
{
return x.CompareTo(y);
}
#region IComparer Members
int IComparer.Compare(Object x, Object y)
{
return this.Compare((IComparable)x,y);
}
#endregion
}
public class QuickSorter
{
private IComparer comparer;
private ISwap swapper;
public QuickSorter()
{
this.comparer = new DefaultComparer();
this.swapper = new DefaultSwap();
}
public QuickSorter(IComparer comparer, ISwap swapper)
{
if (comparer == null)
throw new ArgumentNullException("comparer");
if (swapper==null)
throw new ArgumentNullException("swapper");
this.comparer = comparer;
this.swapper = swapper;
}
public ISwap Swapper
{
get
{
return this.swapper;
}
set
{
if (value==null)
throw new ArgumentNullException("swapper");
this.swapper = value;
}
}
public void Sort(IList array)
{
Sort(array, 0, array.Count1);
}
public void Sort(IList array, int lower, int upper)
{
if (lower < upper)
{
int split=Pivot(array, lower, upper);
Sort(array, lower, split1);
Sort(array, split+1, upper);
}
}
#region Internal
internal int Pivot(IList array, int lower, int upper)
{
int left=lower+1;
object pivot=array[lower];
int right=upper;
while (left <= right)
{
while ( (left <= right) && (comparer.Compare(array[left], pivot) <= 0) )
{
++left;
}
while ( (left <= right) && (comparer.Compare(array[right], pivot) > 0) )
{
right;
}
if (left < right)
{
swapper.Swap(array, left, right);
++left;
right;
}
}
swapper.Swap(array, lower, right);
return right;
}
#endregion
}
}
Jonathan de Halleux.
www.dotnetwiki.org





This is a good candidate for delegates. Instead of forcing the ISwap interface on all your callees/children, simply require a function matching the definition of swap(), passed as a delegate. This would also make thread safety a bit easier to implement, in theory.
Typically, I use interfaces as type contracts only, and delegates for pluggable functionality like custom userdefinable functions. The best thing about delegates is that your class can provide a default delegate, or a direct call when delegate==null.
I guess using interfaces is better OO design, so it's mainly a matter of taste.






Another nice underrated article.
What about multithreading? is it safe?
Jonathan de Halleux.
www.dotnetwiki.org





Jonathan de Halleux wrote: Another nice underrated article.
Well there, I just voted a 5 for myself. Helps to balance the negative effect, right?
Jonathan de Halleux wrote: What about multithreading? is it safe?
Hmmm. An interesting question. I'd say no. The comparer and swapper are stored in static members. I didn't want to deal with instantiating the class everytime I use it, but obviously, the current implementation won't work in a multithreaded environment.
Maybe I'll post another article on making it thread safe. See how low the ratings can get on that one.
Marc
Latest AAL Article My blog Join my forum!





Marc Clifton wrote: I just voted a 5 for myself.
I think everybody does.
Marc Clifton wrote: I didn't want to deal with instantiating the class everyt
You lazy!
Another question: quicksort is O(nlogn), what about other sorts (comparaison based: heap, shear, etc...) or radix based (ABCsort)
Jonathan de Halleux.
www.dotnetwiki.org





Jonathan de Halleux wrote: You lazy!
Indeed. I do miss C's global function capability. I think declaring methods as static is a silly workaround, and the singleton pattern is a kludge for the same effect. There are cases where I simply don't want to instantiate an object! But this may not have been a good one, as you pointed out the problem with multithreading.
Jonathan de Halleux wrote: Another question: quicksort is O(nlogn), what about other sorts (comparaison based: heap, shear, etc...) or radix based (ABCsort)
I have no idea. I'm definitely not, by an stretch of the imagination, well informed regarding sorting algorithms. I seemed to have missed all that cool stuff in college. Oh wait, I didn't go to college! That explains it!
Marc
Latest AAL Article My blog Join my forum!





There is no (known) sort algorithm with less complexity than n*logn. But there are algorithms which are better suited for most/some/a few sorting problems. For example Bubble Sort will do much better than Quicksort if the array to sort is already partly sorted (if you change only a small part of an sorted array BubbleSort will resort in much quicker than most other sorting algorithms). One Algorithm which is almost always better than the normal Quicksort (at least for larger Arrays) is the FastQuickSort algorithm. The best algorithm is heavily dependant on the data you sort. Some algorithms are optimized to sort arrays with many equal numbers, some are good when the swap/euqaltest run very slow/fast.
I have 13 sotring algorithms running in a testproject. I never bothered to post them on CodeProject but this could be the right time to do it. @Marc Clifton: What about extending your code so it supports different sorting algorithms? I'll deliver the algorithms...





What about extending your code so it supports different sorting algorithms? I'll deliver the algorithms...
Funny you should ask! I've got an article ready to go that includes several additional algorithms that Jonathan ported from Java. He also made some significant improvements to the class structure. He implemented FastQuickSort, BubbleSort, ShearSort, and OddEvenTransportSort.
I'd certainly welcome additional algorithms. All three of us will be authors on the new article!
Marc
Latest AAL Article My blog Join my forum!






I read that parallelization using a separate thread to sort each list partition at the same time. Would this cause large speed increase? maybe using the 25 threads available in thread pool class in c#?





abcdefgqwerty wrote: I read that parallelization using a separate thread to sort each list partition at the same time. Would this cause large speed increase? maybe using the 25 threads available in thread pool class in c#?
Threads don't increase performance, processors do.
The point of threads is to do something while other threads are idle. If you distribute the processing of nonidle work among many threads each busy, you don't gain anything. You actually make the system slower.
Marc
Thyme In The CountryPeople are just notoriously impossible. DavidCrow There's NO excuse for not commenting your code.  John Simmons / outlaw programmer People who say that they will refactor their code later to make it "good" don't understand refactoring, nor the art and craft of programming.  Josh Smith







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

