Сортировка слияния в Objective C

Question

Я пытаюсь реализовать сортировку слияния в объективе -C.

Это аналогичный вопрос, заданный по следующей ссылке, не нашел ответа, так что создавал новый вопрос.

Merge sort in Objective-C

Это то, что я пытался,

-(NSArray *)mergeSort:(NSArray *)unsortedArray { 

    if ([unsortedArray count] < 2) 
     return unsortedArray; 

    long mid = [unsortedArray count]/2; 
    NSRange left = NSMakeRange(0, mid); 
    NSRange right = NSMakeRange(mid, [unsortedArray count] - mid); 

    NSArray *rightArray = [unsortedArray subarrayWithRange:right]; 
    NSArray *leftArray = [unsortedArray subarrayWithRange:left]; 

    NSArray *resultArray = [self merge:leftArray andRight:rightArray]; 
    return resultArray; 
} 

-(NSArray *)merge:(NSArray *)leftArray andRight:(NSArray *)rightArray { 

    NSMutableArray *result = [NSMutableArray array]; 
    int right = 0; 
    int left = 0; 

    while (left < [leftArray count] && right < [rightArray count]) { 

     NSComparisonResult comparisonResult = [leftArray[left] compare:rightArray[right]]; 

     if (comparisonResult != NSOrderedDescending) { 
      [result addObject:[leftArray objectAtIndex:left++]]; 
     } else { 
      [result addObject:[rightArray objectAtIndex:right++]]; 
     } 

     /*if ([[leftArray objectAtIndex:left] intValue] < [[rightArray objectAtIndex:right] intValue]) { 
      [result addObject:[leftArray objectAtIndex:left++]]; 
      //left++; 
     } else { 
      [result addObject:[rightArray objectAtIndex:right++]]; 
      //right++; 
     }*/ 
    } 

    NSRange leftRange = NSMakeRange(left, [leftArray count] - left); 
    NSRange rightRange = NSMakeRange(right, [rightArray count] - right); 
    NSArray * newRight = [rightArray subarrayWithRange:rightRange]; 
    NSArray * newLeft = [leftArray subarrayWithRange:leftRange]; 
    newLeft = [result arrayByAddingObjectsFromArray:newLeft]; 

    return [newLeft arrayByAddingObjectsFromArray:newRight]; 
} 

Пожалуйста, дайте мне знать, если у кого есть какие-либо другие подходы для сортировки слиянием.

Answer 1

Я не понимаю, почему вы хотите, люди длинный путь .. Даже если уже есть простой способ сделать это ...

Я сделал один я надеюсь, что это поможет ..

- (NSArray *)arrayMergeSort:(NSArray *)targetArray 
{ 
    if (targetArray.count < 2) 
     return targetArray; 

    long midIndex = targetArray.count/2; 

    NSArray *arrayLeft = [targetArray subarrayWithRange:NSMakeRange(0, midIndex)]; 

    NSArray *arrayRight= [targetArray subarrayWithRange:NSMakeRange(midIndex, targetArray.count - midIndex)]; 

    return [self arrayMerge: [self arrayMergeSort:arrayLeft] : [self arrayMergeSort:arrayRight]]; 
} 

Для организовать слияние:

- (NSArray *)arrayMerge:(NSArray *)arrayLeft :(NSArray *)arrayRight 
{ 
    NSMutableArray *resultArray = [[NSMutableArray alloc] init]; 

    int i = 0, j = 0; 

    while (i < arrayLeft.count && j < arrayRight.count) 
     [resultArray addObject:([arrayLeft[i] intValue] < [arrayRight[j] intValue]) ? arrayLeft[i++] : arrayRight[j++]]; 

    while (i < arrayLeft.count) 
     [resultArray addObject:arrayLeft[i++]]; 

    while (j < arrayRight.count) 
     [resultArray addObject:arrayRight[j++]]; 

    return resultArray; 
} 

И используя это нравится:

//Sample array 
NSArray *activeArray = @[@101,@201,@301,@121,@11,@123,@21,@14,@32,@76,@89,@987,@65]; 

NSLog(@"arrayMergeSort %@",[self arrayMergeSort:activeArray]); 

выход будет:

А также этот вид пузыря, если вам нужно это:

- (NSArray *)arrayBubbleSort:(NSArray *)targetArray 
{ 
    NSMutableArray *resultArray = [targetArray mutableCopy]; 

    for (int k = 0; k < resultArray.count; k++) 
    { 
     for (int l = 0; l < resultArray.count; l++) 
     { 
      if ([resultArray[k] intValue] < [resultArray[l] intValue]) 
      { 
       [resultArray exchangeObjectAtIndex:k withObjectAtIndex:l]; 
      } 
     } 
    } 

    return resultArray; 
} 

Надежда я помог вам .. Ура ..

Answer 2

You» ве сделала простую ошибку. Merge sort работает с моим разбиением массива, сортировка на две половины, затем слияние результатов.

Ваш метод mergeSort: делает раскол, не сортирует две половинки, а затем вызывает merge: объединить два (к сожалению) половинки без сортировки.

Перед тем как позвонить merge:, вам необходимо сделать рекурсивные звонки mergeSort:, чтобы отсортировать две половинки - это простой шаг, который вы пропустили.

Я угадываю это в учебном упражнении, поэтому никакого кода, но вы почти там (исправьте его, и он работает).

BTW После исправления вы можете подумать о том, почему вам не нужно создавать новые массивы для разделенной части (но гораздо проще создать новый массив для слияний).

HTH