Is there a method to sort an NSString?

Question

Does anyone know if there is a method to sort an NSString of ASCII characters? Ideally, I would like a method that checks to see if one string is a permutation of another, so my idea is to sort both strings in a canonical fashion and then compare them. Any ideas will be greatly appreciated. Thanks.

EDIT: Here is what I am after more precisely. I want a method that takes two NSStrings as input and returns a BOOL:

- (BOOL)isPermutation:(NSString *)string1 
             ofString:(NSString *)string2; 

The returned value should be YES if one string can be rearranged into the other string and NO otherwise.

The NSStrings are arbitrary strings with ASCII characters, not sentences or numbers or words. Just arbitrary strings with ASCII characters.

Answer 1

Do you really need to sort to check this? Consider the algorithm.

create 2 counter arrays, ac and bc, both of size 128
initialize them with 0
for each char c in string a make ac[c]++
for each char c in string b make bc[c]++
if all 128 counters in ac and bc are same, then they r permutation of one another

This may even run faster then sorting.

EDIT: This is a possible implementation. As I have not compiled the code, there might be minor errors.

- (BOOL)isPermutation:(NSString *)string1 ofString:(NSString *)string2 {
    if ([string1 length] != [string2 length]) {
        return FALSE;    
    }

    NSInteger counter1[128];
    NSInteger counter2[128];
    NSInteger i;
    NSInteger len = [string1 length];

    for (i = 0; i < 128; i++) {
        counter1[i] = counter2[i] = 0;
    }

    for (i = 0; i < len; i++) {
        unichar ch1 = [string1 characterAtIndex:i];
        unichar ch2 = [string2 characterAtIndex:i];
        counter1[ch1]++;
        counter2[ch2]++;
    }

    for (i = 0; i < 128; i++) {
        if (counter1[i] != counter2[i]) {
            return FALSE;
        }
    }

    return TRUE;
}

Answer 2

Do you mean, sorting the letters within a string? There's not a method on NSString, but it'd be pretty easy to create one. Here's a quick-and-dirty example (you might need to adapt it to your purposes):

#import <Foundation/Foundation.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

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

@interface NSString (Sorting)
- (NSString *)stringBySortingCharacters;
@end

@implementation NSString (Sorting)
- (NSString *)stringBySortingCharacters
{
    const char *s = [self UTF8String];
    char *s2 = (char *) calloc([self length]+1, 1);
    if (!s2) return nil;
    strncpy(s2, s, [self length]);
    qsort(s2, [self length], 1, compare_char);
    NSString *ret = [NSString stringWithUTF8String:s2];
    free(s2);
    return ret;
}
@end

int main(int argc, char **argv)
{
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    NSString *s1 = @"string";
    NSString *s2 = @"the quick brown fox jumps over the lazy dog";
    printf("Sorted: %s\n", [[s1 stringBySortingCharacters] UTF8String]);
    printf("Sorted: %s\n", [[s2 stringBySortingCharacters] UTF8String]);

    [pool release];
    return 0;
}