QSort in D: is this best?

BCS none at anon.com
Sun Dec 20 17:18:13 PST 2009


Hello downs,

> Or are there any bugs/optimization opportunities I'm missing?
> 
> void qsort(T)(T[] array) {
> if (array.length < 2) return;
> static int i;
> auto pivot = array[i++%$];
> // from is base-0, to is base-1.
> int from = 0, to = array.length;
> while (from != to) {
> if (array[from] >= pivot && array[to-1] < pivot)
> swap(array[from], array[to-1]);
> if (array[from] < pivot)
> from ++;
> if (array[to-1] >= pivot)
> to --;
> }
> array[0 .. from].qsort();
> array[from .. $].qsort();
> }

The last 2 ifs get repeated for every loop even when you can know they don't 
need to be. It would take more code but you could get around that.





More information about the Digitalmars-d mailing list