CODEWITHSUNDEEP
sortingd
new299
new299

Reputation: 814

In-place radix sort in D programming language

I'm trying to get the in-place radix sort example from In-Place Radix Sort working. So far I have this:

import std.random;

void swap(ref string i,ref string j) {

  string tmp = i;
  i = j;
  j = tmp;
}

void radixSort(ref string[] seqs, size_t base = 0) {
    if(seqs.length == 0)
        return;

    size_t TPos = seqs.length, APos = 0;
    size_t i = 0;
    while(i < TPos) {
        if(seqs[i][base] == 'A') {
             swap(seqs[i], seqs[APos++]);
             i++;
        }
        else if(seqs[i][base] == 'T') {
            swap(seqs[i], seqs[--TPos]);
        } else i++;
    }

    i = APos;
    size_t CPos = APos;
    while(i < TPos) {
        if(seqs[i][base] == 'C') {
            swap(seqs[i], seqs[CPos++]);
        }
        i++;
    }
    if(base < seqs[0].length - 1) {
        radixSort(seqs[0..APos], base + 1);
        radixSort(seqs[APos..CPos], base + 1);
        radixSort(seqs[CPos..TPos], base + 1);
        radixSort(seqs[TPos..seqs.length], base + 1);
   }
}

void main(string[] args) {

  string [] sequences;

  for(int n=0;n<10;n++) {
    string seq;
    for(int i=0;i<10;i++) {
      int r = rand()%4;
      if(r == 0) seq = seq ~ "A";
      if(r == 1) seq = seq ~ "C";
      if(r == 2) seq = seq ~ "G";
      if(r == 3) seq = seq ~ "T";
    }
    sequences = sequences ~ seq;
  }

  writefln("Unsorted");
  for(size_t n=0;n<10;n++) {
    writefln(sequences[n]);
  }

  radixSort(sequences,0);

  writefln("Sorted");
  for(size_t n=0;n<10;n++) {
    writefln(sequences[n]);
  }
}

However, this fails with:

radix.d(36): Error: slice expression seqs[0u..APos] is not a modifiable lvalue
radix.d(37): Error: slice expression seqs[APos..CPos] is not a modifiable lvalue
radix.d(38): Error: slice expression seqs[CPos..TPos] is not a modifiable lvalue
radix.d(39): Error: slice expression seqs[TPos..seqs.length] is not a modifiable lvalue

Under the Digital Mars D Compiler v1.066. I guess slices are not mutable, but... how should I go about fixing this?

I'm new to D and largely just interested in getting this example working.

Upvotes: 6

Views: 403

Answers (2)

Nordl&#246;w
Nordl&#246;w

Reputation: 12138

I have an implementation that's pretty complete at https://github.com/nordlow/phobos-next/blob/master/src/nxt/integer_sorting.d#L38.

Feel free to borrow whatever you need.

Upvotes: 1

FeepingCreature
FeepingCreature

Reputation: 3788

You only need ref if you want to modify the reference itself. For an array, that means changing the length or reallocating. Since your radix sort is in-place, I'm not sure why you'd want that.

Upvotes: 8

Related Questions