Quicksort Ошибка при сортировке большого массива

Question

я получаю сообщение об ошибке при попытке отсортировать массив ста тысяч Интс (я проверил сорт и он работает на пятьдесят тысяч):

предупреждение: может не загружать информацию о классе Objective-C. Это значительно снизит качество имеющейся информации о типе.

У меня также есть метод сравнения итеративно и появляется та же ошибка

Почему происходит это сообщение об ошибке?

Возможно ли отсортировать этот список, и если да, то как его исправить?

-(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]; 
} 

Итерационный Сравните и это прекрасно работает:

-(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

Хотя сам Quicksort считается рекурсивный алгоритм, шаг раздела (ваш comparetoPivot метод) не предназначен для рекурсии. И ваша реализация этого метода не только рекурсивна, но и O (N) в отношении пространства стека. Вы рекурсируете только с меньшим количеством элементов, чем раньше, с каждой рекурсией в compareToPivot. Выдувание (истекающий стек) при звуках около 100 тыс. Элементов следует ожидать, поскольку стек по умолчанию составляет около 500 КБ.

Я использовал ваш вопрос в качестве предлога для практики моего Obj-C, с которым я немного ржав. Но вот реализация рекурсивного Quicksort прямо из классического Algorithms (Cormen et. al.) book и адаптирована для вашего массива toSort. Я еще не проверял все это, но вы, безусловно, можете дать ему вихрь.

-(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]; 
    } 
}