Quicksort Error when sorting large array

Question

I get an error message when I try to sort an array of one hundred thousand ints(I've tested the sort and it works for fifty thousand):

warning: could not load any Objective-C class information. This will significantly reduce the quality of type information available.

I also have the compare method iteratively and the same error appears

Why is this error message happening?

Is it possible to sort that list and if so how to fix it?

-(void) quickSort{
   return [self quickSort:0 pivot:[self.toSort count]-1 right: [self.toSort count]-1];
}

-(void) quickSort:(int) left pivot:(int) pivot right:(int) right {
    if(left < right){
        pivot = [self compareToPivot:[[self.toSort objectAtIndex:right] intValue] start:left finish:right position:left];
        [self quickSort:pivot+1 pivot:pivot right:right];
        [self quickSort:left pivot:pivot right:pivot-1];
    }

}

-(int) compareToPivot:(int) pivot start:(int)start finish:(int)finish position:(int)pos{
    if(pos == finish){
        [self switchNums:start second:finish];
        return start;
    }
     if([[self.toSort objectAtIndex:pos] intValue] <= pivot){
     [self switchNums:pos second:start];
     return [self compareToPivot:pivot start:start+1 finish:finish position:pos+1];
}
return [self compareToPivot:pivot start:start finish:finish position:pos+1];
}

-(void) switchNums:(int)first second:(int)second{
    id temp = [self.toSort objectAtIndex:second];
    [self.toSort replaceObjectAtIndex:second withObject:[self.toSort objectAtIndex:first]];
    [self.toSort replaceObjectAtIndex:first withObject:temp];
}

Iterative Compare and this runs fine:

-(int) compareToPivot:(int) pivot start:(int)start finish:(int)finish position:(int)pos{

while(pos != finish){
    if([[self.toSort objectAtIndex:pos] intValue] <= pivot){
        [self switchNums:pos second:start];
        start+=1;
    }
        pos++;
}
[self switchNums:start second:finish];
return start;

}

Answer 1

While Quicksort itself is considered a recursive algorithm, the partition step (your comparetoPivot method) is not meant for recursion. And your implementation of this method is not only recursive, but it also is O(N) as far as stack space is concerned. You only recurse with one less element than before with each recursion into compareToPivot. Blowing up (running out stack) at around 100K elements sounds is to be expected as the default stack is around 500KB.

I used your question as an excuse to practice my Obj-C, which I'm a bit rusty on. But here's the implementation of recursive Quicksort straight out of the classic Algorithms (Cormen et. al.) book and adapted for your toSort array. I haven't tested it all out yet, but you can certainly give it a whirl.

-(int)partition: (NSMutableArray*)arr pivot:(int)pivot  right:(int)right
{
    int x = [[arr objectAtIndex: pivot] intValue];

    int i = pivot;
    int j = right;

    while (true)
    {

        while ([[arr objectAtIndex: j] intValue] > x)
        {
            j--;
        }

        while ([[arr objectAtIndex: i] intValue] < x)
        {
            i++;
        }

        if (i < j) {
            id objI = [arr objectAtIndex: i];
            id objJ = [arr objectAtIndex: j];
            [arr replaceObjectAtIndex:i withObject:objJ];
            [arr replaceObjectAtIndex:j withObject:objI];
            j--;
            i++;
        }
        else
        {
            return j;
        }
    }

}

-(void)quickSort
{
    int len = (int)[self.toSort count];
    [self quicksort:self.toSort left:0 right:(len-1)];
}

-(void)quicksort: (NSMutableArray*)arr left:(int)left  right:(int)right
{
    if (left< right)
    {
        int q = [self partition:arr pivot:left right:right];
        [self quicksort: arr left:left  right:q];
        [self quicksort: arr left:(q+1) right:right];
    }
}