Objective-C에서 병합 정렬

이 병합 정렬 구현의 문제점을 파악하려고합니다. 나는 왼쪽과 오른쪽 배열의 나머지 부분을 연결할 때까지 좁혔습니다. 재귀의 세 번째 루프에서 뭔가 잘못되었습니다.Objective-C에서 병합 정렬

-(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를 조금 배우려고합니다. 모두에게 감사드립니다.

출처

2013-08-17 Michael Leveton

"무언가가 잘못되었습니다"란 무엇을 의미합니까? 잘못된 행동은 무엇입니까? – Fred

출력이 주어진 배열에 대해 오름차순이 아닙니다. –

< (보다 작음) 연산자를 사용하여 두 개체를 비교할 수 없습니다. compare: 방법을 사용 :

은 교체 :

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

로 :

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

"강탈"가 지적 하듯이,하는 것이 더 좋다 :

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

BTW - 두 개의 객체가있는 <을 사용하면 점을 비교하기 때문에 문제가 발생합니다. r 두 주소의 주소. 따라서 객체의 가치에 의한 것이 아닌 메모리상의 위치에 따라 객체를 정렬하게됩니다.

물론 compare: 메서드를 사용하면 배열의 객체가 실제로 compare: 메서드를 구현한다고 가정합니다. NSString, NSNumber 및 NSDate과 같은 경우에도 마찬가지입니다. 이러한 객체가 사용자 정의 객체 인 경우 동일한 메소드를 구현해야합니다. 교체

: 대한

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

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

도 작동합니다

출처

2013-08-17 03:32:27 rmaddy

'result! = NSOrderedDescending'을 확인하여 대신 안정된 정렬로 만드십시오. –

확실히 문제는 비교입니다.

출처

2014-04-22 23:13:41

Objective-C에서 병합 정렬

답변

관련 문제