How to sort a string of characters in objective-C?

Question

I'm looking for an Objective-C way of sorting characters in a string, as per the answer to this question.

Ideally a function that takes an NSString and returns the sorted equivalent.

Additionally I'd like to run length encode sequences of 3 or more repeats. So, for example "mississippi" first becomes "iiiimppssss", and then could be shortened by encoding as "4impp4s".

I'm not expert in Objective-C (more Java and C++ background) so I'd also like some clue as to what is the best practice for dealing with the memory management (retain counts etc - no GC on the iphone) for the return value of such a function. My source string is in an iPhone search bar control and so is an NSString *.

Answer 1

int char_compare(const char* a, const char* b) {
    if(*a < *b) {
        return -1;
    } else if(*a > *b) {
        return 1;
    } else {
        return 0;
    }
}

NSString *sort_str(NSString *unsorted) {
    int len = [unsorted length] + 1;
    char *cstr = malloc(len);
    [unsorted getCString:cstr maxLength:len encoding:NSISOLatin1StringEncoding];
    qsort(cstr, len - 1, sizeof(char), char_compare);
    NSString *sorted = [NSString stringWithCString:cstr encoding:NSISOLatin1StringEncoding];
    free(cstr);
    return sorted;
}

The return value is autoreleased so if you want to hold on to it in the caller you'll need to retain it. Not Unicode safe.

Answer 2

With a bounded code-set, radix sort is best:

NSString * sortString(NSString* word) {
    int rads[128];
    const char *cstr = [word UTF8String];
    char *buff = calloc([word length]+1, sizeof(char));
    int p = 0;
    for(int c = 'a'; c <= 'z'; c++) {
        rads[c] = 0;
    }
    for(int k = 0; k < [word length]; k++) {
        int c = cstr[k];
        rads[c]++;
    }
    for(int c = 'a'; c <= 'z'; c++) {
        int n = rads[c];
        while (n > 0) {
            buff[p++] = c;
            n--;
        }
    }
    buff[p++] = 0;
    return [NSString stringWithUTF8String: buff];
}

Note that the example above only works for lowercase letters (copied from a specific app which needs to sort lowercase strings). To expand it to handle all of the ASCII 127, just do for(c=0; c <= 127; c++).