iOS 개발(OC) - 정렬 알고리즘

iOS 개발 AC 팜: 301058503
1. 거품 정렬(1) 알고리즘 원리: (승차순) n-1회의 인접 비교를 하고 큰 것은 오른쪽에 놓고 한 번에 최대치를 얻으면 가장 오른쪽에 놓는다(2) 시간 복잡도: n(n-1)/2(3) 코드

+ (NSMutableArray *)mapaoSort:(NSMutableArray *)array {
    NSInteger count = 0;
    for (int i=0; i [array[j+1] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
            count++;
        }
    }
    NSLog(@"count=%zu",count);
    return array;
}

2. 칵테일 서열(1) 알고리즘 원리: (승차순) 가장 작은 숫자를 먼저 찾아서 그를 1위에 놓고 가장 큰 숫자를 찾아서 마지막에 놓는다.그리고 두 번째 작은 숫자를 찾아서 두 번째, 두 번째 큰 숫자를 찾아서 밑에서 두 번째.이런 식으로 추론하면 낮은 위치가 높은 위치보다 클 때까지(2) 시간 복잡도: n(n-1)/2(3) 코드

+ (NSMutableArray *)jiweijiuSort:(NSMutableArray *)array {
    NSInteger count = 0;
    NSInteger low = 0;
    NSInteger high = array.count-1;
    while (low < high) {
        for (NSInteger i=low+1; i<=high; i++) {
            if ([array[low] integerValue] > [array[i] integerValue]) {
                [array exchangeObjectAtIndex:low withObjectAtIndex:i];
            }
            count++;
        }
        low++;
        
        for (NSInteger j=high-1; j>=low; j--) {
            if ([array[high] integerValue] < [array[j] integerValue]) {
                [array exchangeObjectAtIndex:high withObjectAtIndex:j];
            }
            count++;
        }
        high--;
    }
    NSLog(@"count=%zu",count);
    return array;
}

3. 선택 정렬(1) 알고리즘 원리: n-1회를 진행하고 매 번에 최값을 찾아낸다(2) 시간 복잡도: n(n-1)/2(3) 코드

+ (NSMutableArray *)selectSort:(NSMutableArray *)array {
    NSInteger count = 0;
    for (int i=0; i [array[j] integerValue]) {
                min = [array[j] integerValue];
                index = j;
            }
            count++;
        }
        [array exchangeObjectAtIndex:index withObjectAtIndex:i];
    }
    NSLog(@"count=%zu",count);
    return array;
}

4. 정렬 삽입 (1) 알고리즘 원리: 질서정연한 대기열에 새 값 증가 (2) 시간 복잡도: (3) 코드

+ (NSMutableArray *)insertSort:(NSMutableArray *)array {
    if (array.count == 0) {
        return array;
    }
    NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];
    NSInteger count = 0;
    for (NSInteger i=1; i= [results[results.count-1] integerValue]) {
                [results addObject:array[i]];
                break;
            }
            if (j+1 < results.count && [array[i] integerValue] >= [results[j] integerValue] && [array[i] integerValue] <= [results[j+1] integerValue]) {
                 [results insertObject:array[i] atIndex:j+1];
                break;
            }
        }
       
    }
    NSLog(@"count=%zu",count);
    return results;
}

5. 2분 삽입 정렬(1) 알고리즘 원리: 삽입 정렬을 바탕으로 한다.삽입 정렬은 질서정연한 대기열에 삽입되기 때문에 질서정연한 대기열에서 우리는 더욱 효율적인 이분법으로 위치를 찾을 수 있으며 처음부터 끝까지 반복할 필요가 없다(2) 시간 복잡도: (3) 코드

+ (NSMutableArray *)halfInsertSort:(NSMutableArray *)array {
    if (array.count == 0) {
        return array;
    }
    NSMutableArray *results = [NSMutableArray arrayWithObject:array[0]];
    NSInteger count = 0;
    for (NSInteger i=1; i= [results[mid] integerValue]) {
                low = mid+1;
            } else {
                high = mid-1;
            }
            count++;
        }
        
        [results insertObject:array[i] atIndex:low];
    }
    NSLog(@"count=%zu",count);
    return results;
}