1

このマージソートの実装の何が問題なのかを理解しようとしています。左と右の配列の残りを連結する場合に絞り込みました。再帰の 3 番目のループで、何かがおかしくなりました。

-(NSArray *)mergeSort:(NSArray *)unsortedArray
{
  //unsortedArray is 4,2,6,5,3,9
  if ([unsortedArray count] < 2)
 {
    return unsortedArray;
 }
   int middle = ([unsortedArray count]/2);
   NSRange left = NSMakeRange(0, middle);
   NSRange right = NSMakeRange(middle, ([unsortedArray count] - middle));
   NSArray *rightArr = [unsortedArray subarrayWithRange:right];
   NSArray *leftArr = [unsortedArray subarrayWithRange:left];
   return [self merge:[self mergeSort:leftArr] andRight:[self mergeSort:rightArr]];
}

-(NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
{
  NSMutableArray *result = [[NSMutableArray alloc]init];
  int right = 0;
  int left = 0;

  while (left < [leftArr count] && right < [rightArr count])
  {
    if ([leftArr objectAtIndex:left] < [rightArr objectAtIndex:right])
    {
        [result addObject:[leftArr objectAtIndex:left++]];
    }
    else
    {
        [result addObject:[rightArr objectAtIndex:right++]];
    }
 }
  NSRange leftRange = NSMakeRange(left, ([leftArr count] - left));
  NSRange rightRange = NSMakeRange(right, ([rightArr count] - right));
  NSArray *newRight = [rightArr subarrayWithRange:rightRange];
  NSArray *newLeft = [leftArr subarrayWithRange:leftRange];
  newLeft = [result arrayByAddingObjectsFromArray:newLeft];
  return [newLeft arrayByAddingObjectsFromArray:newRight];
}

ところで、これは宿題ではありません。私は少し CS を学ぼうとしている独学のプログラマーです。みんな、ありがとう。

4

2 に答える 2

8

<(より小さい) 演算子を使用して 2 つのオブジェクトを比較することはできません。compare:次の方法を使用します。

交換：

if ([leftArr objectAtIndex:left] < [rightArr objectAtIndex:right])

と：

NSComparsionResult result = [leftArr[left] compare:rightArr[right]];
if (result == NSOrderedAscending) // equivalent to <

「rob」が指摘しているように、次のように使用するとさらに良いでしょう。

if (result != NSOrderedDescending) // equivalent to <=

ところで-2<つのオブジェクトのポインターアドレスを比較しているため、2つのオブジェクトで使用すると問題が発生します。そのため、オブジェクトの値ではなく、メモリ内の位置に基づいてオブジェクトをソートすることになります。

もちろん、compare:メソッドを使用すると、配列内のオブジェクトが実際にcompare:メソッドを実装していると想定されます。NSStringこれは、NSNumber、 、 などに当てはまりますNSDate。これらがカスタム オブジェクトである場合は、同等のメソッドを実装する必要があります。

于 2013-08-17T03:32:27.063 に答える