Sorting an Array

downs default_357-line at yahoo.de
Wed Jul 11 05:35:38 PDT 2007


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


More information about the Digitalmars-d-learn mailing list