okibi wrote:
> I couldn't get your function to compile. I get the following error:
> 
> Error: need 'this' to access member getNumericPart
> 
> On the line:
> 
> return getNumericPart(a)>getNumericPart(b);
> 
> Any ideas?

That's odd. Try this instead, maybe there's a conflict with the sort attribute.

   sort(array, function(char[] a, char[] b) {
     return getNumericPart(a)>getNumericPart(b);
   });

Same issue.


torhu Wrote:

> okibi wrote:
> > I couldn't get your function to compile. I get the following error:
> > 
> > Error: need 'this' to access member getNumericPart
> > 
> > On the line:
> > 
> > return getNumericPart(a)>getNumericPart(b);
> > 
> > Any ideas?
> 
> That's odd. Try this instead, maybe there's a conflict with the sort attribute.
> 
>     sort(array, function(char[] a, char[] b) {
>       return getNumericPart(a)>getNumericPart(b);
>     });

okibi wrote:
> Well, the following comment made it seem like it won't work:
> 
>>>    // comparing sorting algorithm goes here. See wikipedia for examples.
>>>    // Quicksort should do nicely and is easy to implement.

Oops, sorry, yeah that code isn't using the builtin array sort operation.

import std.c.stdlib;

and you should be able to call the C qsort() function.  That can be a bit of a nightmare in itself so give it a go and post if you have trouble.

Regan

okibi wrote:
> I couldn't get your function to compile. I get the following error:
> 
> Error: need 'this' to access member getNumericPart
> 
> On the line:
> 
> return getNumericPart(a)>getNumericPart(b);
> 
> Any ideas?
> 
> downs Wrote:
> 
> 
>>okibi wrote:
>>
>>>Is there an easy way to sort an array with elements such as "12 - Some text" or "241 - Other Text"?
>>>
>>>I want to sort in order of the numbers. Is this possible?
>>>
>>>Thanks!
>>
>>// Sort array via comparison operator.
>>// 'bigger' returns if 'value' is bigger than 'than'.
>>void sort(T)(ref T[] array, bool function(T value, T than) bigger) {
>>   // comparing sorting algorithm goes here. See wikipedia for examples.
>>   // Quicksort should do nicely and is easy to implement.
>>}
>>
>>long getNumericPart(char[] inp) {
>>   if (!input.length) return long.max+1; // no number is very small.
>>   size_t numlen=0;
>>   while (numlen<inp.length)&&(inp[numlen]>='0')&&(inp[numlen]<='9'))
>>     ++numlen;
>>   return inp[0..numlen];
>>}
>>
>>void main() {
>>   char[][] array=getArray(); // array is read
>>   array.sort(function(char[] a, char[] b) {
>>     return getNumericPart(a)>getNumericPart(b);
>>   });
>>}
>>
>>Didn't try, obviously, but it should work.
>>Have fun! :D
>>  --downs
> 
> 

I think the problem is that getNumericPart is outside the scope of that function literal, so it needs a context to access it. That's a screw-up on GDC/DMD's part though, since global functions should be unambiguous.
void main() {
   char[][] array=getArray(); // array is read
   array.sort(function(char[] a, char[] b) {
     long getNumericPart(char[] inp) {
       if (!input.length) return long.max+1; // no number is very small.
       size_t numlen=0;
       while (numlen<inp.length)&&(inp[numlen]>='0')&&(inp[numlen]<='9'))
         ++numlen;
       return inp[0..numlen];
     }
     return getNumericPart(a)>getNumericPart(b);
   });
}

should work.
Oh also, here's quicksort ^^

/* From Wikipedia
 function partition(array, left, right, pivotIndex)
     pivotValue := array[pivotIndex]
     swap( array, pivotIndex, right) // Move pivot to end
     storeIndex := left
     for i  from  left to right-1
         if array[i] <= pivotValue
             swap( array, storeIndex, i)
             storeIndex := storeIndex + 1
     swap( array, right, storeIndex) // Move pivot to its final place
     return storeIndex
*/
void swap(ref T a, ref T b) { T c=a; a=b; b=c; }
size_t partition(T)(T[] array, size_t left, size_t right, size_t pivotIndex,
	bool function(T a, T than) comp) {
	auto pivotValue=array[pivotIndex];
	swap(array[pivotIndex], array[right]);  // move pivot to end
	auto storeIndex=left;
	foreach (inout value; array[left..right]) {
		if (!comp(value, pivotValue)) swap(array[storeIndex++], value);
	swap(array[right], array[storeIndex]); // move pivot to its final place
	return storeIndex;
}

/* Actual algorithm from Wikipedia
 function quicksort(array, left, right)
     if right > left
         select a pivot index (e.g. pivotIndex = left)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex-1)
         quicksort(array, pivotNewIndex+1, right)
*/
import std.random;
void quicksort(T)(T[] array, size_t left, size_t right,
	bool function(T a, T than) comp) {
	if (right>left) {
		// select random pivot index
		size_t pivotIndex=rand%(right-left)+left;
		auto pivotNewIndex=array.partition(left, right, pivotIndex, comp);
		array.quicksort(left, pivotNewIndex-1, comp);
		array.quicksort(pivotNewIndex+1, right, comp);
}

I didn't test it, but it should work.  ... I hope.
Good luck! :D
 --downs

okibi skrev:
> This does seem like the best way, but I'm not sure how I would go about implement Quicksort into that code. Could you please give me some pointers?

http://www.csc.kth.se/~ol/array.d
http://www.csc.kth.se/~ol/array.html

contains a quicksort implementation like that.


-- 
Oskar

> void swap(ref T a, ref T b) { T c=a; a=b; b=c; }
Oopsie. Should be void swap(T)(ref T a, ref T b)

Thanks! I got it working now and have a better understanding of how arrays work.

Thanks for everyone's help!

downs Wrote:

> > void swap(ref T a, ref T b) { T c=a; a=b; b=c; }
> Oopsie. Should be void swap(T)(ref T a, ref T b)

torhu wrote:
> okibi wrote:
>> This does seem like the best way, but I'm not sure how I would go about implement Quicksort into that code. Could you please give me some pointers?
> 
> I often use C's quicksort, found in std.c.stdlib.
> 
> void sort(T)(T[] array, bool function(T a, T b) compare) {
> 
>      // wrap compare in a C function
>      static extern(C) int cmp(void* a, void* b) {
>          return compare(*cast(T*)a, *cast(T*)b);
>      }
> 
>      qsort(array.ptr, array.length, array[0].sizeof, &cmp);
> }
> 
> compare has to return a negative number if a is smaller, positive is b is smaller, or zero if they are equal.

Someone pointed out that this example doesn't work, since cmp can't access sort's arguments directly.  So I had to fix it.  cmp could obviously call compare through a local, static pointer, but for performance reasons I made qsort call the comparison function directly.  A quick test showed that this matters a whole lot in this case.


This code is tested, no worries.
---
import std.c.stdlib;
import std.stdio;


extern (C) void sort(T)(T[] array, int function(T* a, T* b) compare)
{
	alias extern (C) int function (void* a, void* b) ftype;

	qsort(array.ptr, array.length, array[0].sizeof, cast(ftype)compare);
}


extern(C) int compareInts(int* a, int* b) {
		return *a - *b;
}


void main()
{
	int[] a = [3, 14, 1];

	a.sort(&compareInts);

	writefln(a);  // prints '[1,3,14]'
}
---