www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorting an Array

reply 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!
Jul 10 2007
next sibling parent 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
Jul 10 2007
prev sibling next sibling parent reply 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); } } ----------------------------------------------------------------------------------------------------
Jul 10 2007
parent 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)
Jul 10 2007
prev sibling parent reply 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!

// '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
Jul 10 2007
next sibling parent reply 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!

// '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

Jul 10 2007
next sibling parent reply 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!

// '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


Jul 10 2007
parent reply 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!

// '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



Jul 10 2007
parent 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
Jul 11 2007
prev sibling next sibling parent reply 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.
Jul 10 2007
parent 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]' } ---
Jul 11 2007
prev sibling parent 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
Jul 11 2007
prev sibling parent reply 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!

// '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

Jul 10 2007
next sibling parent reply 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); });
Jul 10 2007
parent 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); });

Jul 10 2007
prev sibling parent reply 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
Jul 11 2007
parent reply downs <default_357-line yahoo.de> writes:
 void swap(ref T a, ref T b) { T c=a; a=b; b=c; }

Jul 11 2007
parent 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; }


Jul 11 2007