• okibi (3/3) Jul 10 2007 Is there an easy way to sort an array with elements such as "12 - Some t...
• Sean Kelly (5/8) Jul 10 2007 You need a sort routine with a custom comparator. Tango has one in
• gogamza (26/31) Jul 10 2007 how about this method?
• Frits van Bommel (11/16) Jul 10 2007 That'll start going wrong once the difference between the integers
• downs (23/28) Jul 10 2007 // Sort array via comparison operator.
• okibi (3/34) Jul 10 2007 This does seem like the best way, but I'm not sure how I would go about ...
• Regan Heath (4/42) Jul 10 2007 I believe the array.sort routine uses Quicksort. So, the code below
• okibi (2/48) Jul 10 2007
• Regan Heath (6/10) Jul 11 2007 Oops, sorry, yeah that code isn't using the builtin array sort operation...
• torhu (11/12) Jul 10 2007 I often use C's quicksort, found in std.c.stdlib.
• torhu (25/42) Jul 11 2007 Someone pointed out that this example doesn't work, since cmp can't
• Oskar Linde (6/7) Jul 11 2007 http://www.csc.kth.se/~ol/array.d
• okibi (6/37) Jul 10 2007 I couldn't get your function to compile. I get the following error:
• torhu (6/15) Jul 10 2007 That's odd. Try this instead, maybe there's a conflict with the sort
• okibi (2/19) Jul 10 2007
• downs (63/111) Jul 11 2007 I think the problem is that getNumericPart is outside the scope of that ...
• downs (1/2) Jul 11 2007 Oopsie. Should be void swap(T)(ref T a, ref T b)
• okibi (3/5) Jul 11 2007 Thanks! I got it working now and have a better understanding of how arra...

okibi <okibi ratedo.com> writes:

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!

Sean Kelly <sean f4.ca> writes:

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?

You need a sort routine with a custom comparator.  Tango has one in 
tango.core.Array.  Unfortunately, I don't think there is such a routine 
in Phobos.


Sean

gogamza <madjakarta gmail.com> writes:

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!


how about this method?


---------------------------------------------------------------------------------------------------
import std.stdio;
import std.string;
import std.conv;

struct keyvalue{
	char[] str;
	
	int opCmp(keyvalue* s){
		char[][] paramKV = split(s.str, "-");
		char[][] thisKV = split(this.str, "-");		
		return toInt(thisKV[0]) - toInt(paramKV[0]);
	}
}



void main(){
	static keyvalue keyval = {"12-Some text"};
	static keyvalue keyval2 = {"6-Other Text"};
	static keyvalue keyval3 = {"7-Other Text2"};

	keyvalue[] keyvals = [keyval, keyval2, keyval3];

	keyvalue[] keyvals2 = keyvals.sort;

	foreach(keyvalue kv;keyvals2){
		writefln(kv.str);
	}
}

----------------------------------------------------------------------------------------------------

Frits van Bommel <fvbommel REMwOVExCAPSs.nl> writes:

gogamza wrote:
     int opCmp(keyvalue* s){
         char[][] paramKV = split(s.str, "-");
         char[][] thisKV = split(this.str, "-");
         return toInt(thisKV[0]) - toInt(paramKV[0]);
     }

That'll start going wrong once the difference between the integers 
starts to get over int.max. The safest way to return an opCmp value for 
integers and larger basic types is with things like:
---
auto val1 = toInt(thisKV[0]);
auto val2 = toInt(paramVK[0]);
return typeid(int).compare(&val1, &val2);
---
(Optionally, replace 'int' with 'typeof(val1)' in that last line if 
you're not sure the type returned by toInt will always be an int)

downs <default_357-line yahoo.de> writes:

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

okibi <okibi ratedo.com> writes:

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?

Thanks!

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

Regan Heath <regan netmail.co.nz> writes:

I believe the array.sort routine uses Quicksort.  So, the code below 
already implements it.

Regan

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?
 
 Thanks!
 
 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

 

okibi <okibi ratedo.com> writes:

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.



Regan Heath Wrote:

 I believe the array.sort routine uses Quicksort.  So, the code below 
 already implements it.
 
 Regan
 
 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?
 
 Thanks!
 
 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

 

Regan Heath <regan netmail.co.nz> writes:

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

torhu <fake address.dude> writes:

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.

torhu <fake address.dude> writes:

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]'
}
---

Oskar Linde <oskar.lindeREM OVEgmail.com> writes:

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

okibi <okibi ratedo.com> writes:

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

torhu <fake address.dude> writes:

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 <okibi ratedo.com> writes:

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);
     });

downs <default_357-line yahoo.de> writes:

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

downs <default_357-line yahoo.de> writes:

 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)

okibi <okibi ratedo.com> writes:

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)