digitalmars.D - Idea: customizable array .sort() property
- Jarrett Billingsley (34/34) Apr 20 2005 The built-in .sort property is fine for most things. It uses qsort() an...
- Andrew Fedoniouk (89/89) Apr 20 2005 I've already published it here, but cannot find it in archive, anyway......
- Derek Parnell (64/65) Apr 20 2005 [snip]
- Andrew Fedoniouk (106/106) Apr 21 2005 Yep, it was my bug. And below is fixed version.
- Andrew Fedoniouk (4/4) Apr 22 2005 Derek, your e-mal address at b..p...com. is not working.
- Derek Parnell (11/13) Apr 22 2005 Its not?! I'm getting emails from others. Try again.
- TechnoZeus (3/37) Apr 20 2005 Shouldn't casting allow this automatically?
- Derek Parnell (8/10) Apr 20 2005 Much needed and overdue. I like it.
-
Stewart Gordon
(8/15)
Apr 21 2005
The built-in .sort property is fine for most things. It uses qsort() and
calls the opCmp. Good enough for most things.
But say you want to sort in more than one way. There is no way to overload
opCmp to compare two of the same type. So instead, we are stuck importing
std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function,
and passing in the array to qsort().
Instead, wouldn't it be cool if we could pass in a custom compare function
to .sort() that would be used instead of the default opCmp?
class A
{
int mX, mY;
int opCmp(A other)
{
if(this.mX<other.mX)
return -1;
else
return 1;
}
}
int mySort(A one, A other)
{
if(one.mY<other.mY)
return -1;
else
return 1;
}
..
A[] a;
// add some elements
// sort by X
a.sort;
// sort by Y
a.sort(mySort);
What do you think?
Apr 20 2005
I've already published it here, but cannot find it in archive, anyway....
// "smart" sort implementation, works 1.3 times faster than D builtin sort
template sort(T)
{
void sort(T[] arr, int function(in T l, in T r) cmp)
{
const int quick_sort_threshold = 9;
if(arr.length < 2) return;
void swap_if_less( inout T t1, inout T t2 )
{
if( cmp(t1, t2) < 0 ) { T t = t1; t1 = t2; t2 = t; }
}
void swap( inout T t1, inout T t2 )
{
T t = t1; t1 = t2; t2 = t;
}
int stack[80];
int* top = stack;
int limit = arr.length;
int base = 0;
for(;;)
{
int len = limit - base;
int i;
int j;
int pivot;
if(len > quick_sort_threshold)
{
// we use base + len/2 as the pivot
pivot = base + len / 2;
swap(arr[base], arr[pivot]);
i = base + 1;
j = limit - 1;
// now ensure that *i <= *base <= *j
swap_if_less(arr[j], arr[i]);
swap_if_less(arr[base],arr[i]);
swap_if_less(arr[j],arr[base]);
for(;;)
{
do i++; while( arr[i] < arr[base] );
do j--; while( arr[base] < arr[j] );
if( i > j )
{
break;
}
swap(arr[i], arr[j]);
}
swap(arr[base], arr[j]);
// now, push the largest sub-array
if(j - base > limit - i)
{
top[0] = base;
top[1] = j;
base = i;
}
else
{
top[0] = i;
top[1] = limit;
limit = j;
}
top += 2;
}
else
{
// the sub-array is small, perform insertion sort
j = base;
i = j + 1;
for(; i < limit; j = i, i++)
{
for(; cmp(arr[j + 1],arr[j]) < 0; j--)
{
swap(arr[j + 1],arr[j]);
if(j == base)
break;
}
}
if(top > stack)
{
top -= 2;
base = top[0];
limit = top[1];
}
else
break;
}
}
}
}
Apr 20 2005
On Wed, 20 Apr 2005 17:04:56 -0700, Andrew Fedoniouk wrote:I've already published it here, but cannot find it in archive, anyway....[snip] Hi Andrew, I just tried out your routine but it seems to have a bug for lengths > 9. Here is my code ... <code> import std.stdio; import sorts; // Andrew's template. int mycmp(char a, char b) { // Upper case is always sorted after than lowercase. int res; int simplecmp(char a, char b) { if (a < b) return -1; if (a > b) return 1; return 0; } if (a >= 'A' && a <='Z') { if (b >='A' && b <= 'Z') { // Both uppercase res = simplecmp(a,b); } else { // First is uppercase so it goes high. res = 1; } } else { if (b >='A' && b <= 'Z') { // First is lowercase so it goes low. res = -1; } else { // Both lowercase res = simplecmp(a,b); } } return res; } alias sorts.sort!(char) csort; void main(char[][] pArgs) { char[] a; if (pArgs.length == 1) a = "AbCdEfGhIjKlMnOpQrStUvWxYz".dup; else a = pArgs[1].dup; a.csort(&mycmp); writefln("%s", a); } </code> -- Derek Melbourne, Australia 21/04/2005 12:07:42 PM
Apr 20 2005
"Andrew Fedoniouk" <news terrainformatica.com>
Yep, it was my bug. And below is fixed version.
Thanks, Derek.
template sort(T)
{
void sort(T[] arr, int function(in T l, in T r) cmp)
{
const int quick_sort_threshold = 9;
if(arr.length < 2) return;
void swap_if_less( inout T t1, inout T t2 )
{
if( cmp(t1, t2) < 0 ) { T t = t1; t1 = t2; t2 = t; }
}
void swap( inout T t1, inout T t2 )
{
T t = t1; t1 = t2; t2 = t;
}
int stack[80];
int* top = stack.ptr;
int limit = arr.length;
int base = 0;
for(;;)
{
int len = limit - base;
int i;
int j;
int pivot;
if(len > quick_sort_threshold)
{
// we use base + len/2 as the pivot
pivot = base + len / 2;
swap(arr[base], arr[pivot]);
i = base + 1;
j = limit - 1;
// now ensure that *i <= *base <= *j
swap_if_less(arr[j], arr[i]);
swap_if_less(arr[base],arr[i]);
swap_if_less(arr[j],arr[base]);
for(;;)
{
do i++; while( cmp(arr[i],arr[base]) < 0 );
do j--; while( cmp(arr[base],arr[j]) < 0 );
if( i > j )
{
break;
}
swap(arr[i], arr[j]);
}
swap(arr[base], arr[j]);
// now, push the largest sub-array
if(j - base > limit - i)
{
top[0] = base;
top[1] = j;
base = i;
}
else
{
top[0] = i;
top[1] = limit;
limit = j;
}
top += 2;
}
else
{
// the sub-array is small, perform insertion sort
j = base;
i = j + 1;
for(; i < limit; j = i, i++)
{
for(; cmp(arr[j + 1],arr[j]) < 0; j--)
{
swap(arr[j + 1],arr[j]);
if(j == base)
break;
}
}
if(top > stack.ptr)
{
top -= 2;
base = top[0];
limit = top[1];
}
else
break;
}
}
}
}
------------------------------------------
Test:
int less(char a, char b)
{
// Upper case is always sorted after than lowercase.
int A = a; if(a >= 'A' && a <='Z') A <<= 8;
int B = b; if(b >= 'A' && b <='Z') B <<= 8;
return A - B;
}
int main(char[][] args)
{
char[] arr = "KlMnOpQrStUvWxYzAbCdEfGhIj".dup;
writef("%s\n",arr);
sort!(char)(arr,&less);
writef("%s\n",arr);
writef("done\n");
}
Apr 21 2005
Derek, your e-mal address at b..p...com. is not working. Do you have any other addresses out of the psych.ward ? "Derek Parnell" <derek psych.ward> wrote in message news:16zrq2tvts9vz.1ee6p4464fefz.dlg 40tude.net...
Apr 22 2005
On Fri, 22 Apr 2005 13:07:40 -0700, Andrew Fedoniouk wrote:Derek, your e-mal address at b..p...com. is not working. Do you have any other addresses out of the psych.ward ?Its not?! I'm getting emails from others. Try again. In any case, there are three addresses you could use ... ddparnell using the domain bigpond (ddot) com <-- Main one dpar8777 using the domain bigpond (ddot) net (ddot) au <-- cable one dparnell using the domain admerex (ddot) com <-- My office address -- Derek Parnell Melbourne, Australia http://www.dsource.org/projects/build 23/04/2005 10:25:52 AM
Apr 22 2005
Shouldn't casting allow this automatically?
TZ
"Jarrett Billingsley" <kb3ctd2 yahoo.com> wrote in message
news:d46q31$1j2b$1 digitaldaemon.com...
The built-in .sort property is fine for most things. It uses qsort() and
calls the opCmp. Good enough for most things.
But say you want to sort in more than one way. There is no way to overload
opCmp to compare two of the same type. So instead, we are stuck importing
std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function,
and passing in the array to qsort().
Instead, wouldn't it be cool if we could pass in a custom compare function
to .sort() that would be used instead of the default opCmp?
class A
{
int mX, mY;
int opCmp(A other)
{
if(this.mX<other.mX)
return -1;
else
return 1;
}
}
int mySort(A one, A other)
{
if(one.mY<other.mY)
return -1;
else
return 1;
}
..
A[] a;
// add some elements
// sort by X
a.sort;
// sort by Y
a.sort(mySort);
What do you think?
Apr 20 2005
On Wed, 20 Apr 2005 19:57:27 -0400, Jarrett Billingsley wrote:... wouldn't it be cool if we could pass in a custom compare function to .sort() that would be used instead of the default opCmp?Much needed and overdue. I like it. -- Derek Parnell Melbourne, Australia http://www.dsource.org/projects/build/ v2.03 released 20/Apr/2005 http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage 21/04/2005 10:46:23 AM
Apr 20 2005
Jarrett Billingsley wrote:The built-in .sort property is fine for most things. It uses qsort() and calls the opCmp. Good enough for most things. But say you want to sort in more than one way. There is no way to overload opCmp to compare two of the same type. So instead, we are stuck importing std.c.stdlib, declaring an extern(C) int compare(void* a, void* b) function, and passing in the array to qsort().<snip> *** This request has been marked as a duplicate of http://www.digitalmars.com/drn-bin/wwwnews?digitalmars.D/18851 *** Stewart. -- My e-mail is valid but not my primary mailbox. Please keep replies on the 'group where everyone may benefit.
Apr 21 2005