1. 버블 정렬 (Bubble Sort)

이 알고리즘은 반복적으로 인접한 요소를 비교하고, 필요 시 교환하여 최댓값(또는 최솟값)을 배열의 끝으로 이동시킨다. 각 단계마다 하나의 정렬된 요소가 확정되며, 전체적으로 정렬된 상태가 되기까지 O(n²)의 시간 복잡도를 가진다. 최적화된 경우, 이미 정렬된 배열에 대해 O(n)까지 가능하지만, 추가적인 플래그 변수를 사용해야 한다.

- (void)bubbleSort:(NSMutableArray *)arr {
    for (int i = 0; i < arr.count - 1; i++) {
        BOOL swapped = NO;
        for (int j = 0; j < arr.count - 1 - i; j++) {
            if ([arr[j + 1] intValue] < [arr[j] intValue]) {
                [arr exchangeObjectAtIndex:j withObjectAtIndex:j + 1];
                swapped = YES;
            }
        }
        if (!swapped) break;
    }
}

2. 선택 정렬 (Selection Sort)

정렬되지 않은 범위에서 가장 작은 값을 찾아 첫 번째 위치와 교환한다. 이 과정을 반복하며, 매 단계마다 하나의 최소값이 고정된다. 완전히 정렬되기 전까지 모든 요소를 검사하므로 시간 복잡도는 항상 O(n²).

- (void)selectionSort:(NSMutableArray *)arr {
    for (int i = 0; i < arr.count - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.count; j++) {
            if ([arr[j] intValue] < [arr[minIndex] intValue]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            [arr exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
        }
    }
}

3. 삽입 정렬 (Insertion Sort)

정렬된 부분과 아직 정렬되지 않은 부분을 구분하여, 새로운 요소를 적절한 위치에 삽입하는 방식이다. 이미 정렬된 배열에서는 매우 효율적이며, 최선의 경우 O(n)의 성능을 보인다. 그러나 최악의 경우 O(n²)의 시간이 소요된다.

- (void)insertionSort:(NSMutableArray *)arr {
    for (int i = 1; i < arr.count; i++) {
        int key = [arr[i] intValue];
        int j = i - 1;
        while (j >= 0 && [arr[j] intValue] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = @key;
    }
}

4. 쉘 정렬 (Shell Sort)

삽입 정렬의 개선형으로, 간격을 점차 줄이며 여러 그룹 내에서 삽입 정렬을 수행한다. 초기에는 큰 간격으로 분할하여 요소들을 대략적으로 정렬한 후, 점점 더 좁은 간격으로 조정하며 최종적으로 전체 배열을 정렬한다. 평균적으로 O(n log n)의 성능을 기대할 수 있다.

- (void)shellSort:(NSMutableArray *)arr {
    int gap = arr.count / 2;
    while (gap > 0) {
        for (int i = gap; i < arr.count; i++) {
            int temp = [arr[i] intValue];
            int j = i;
            while (j >= gap && [arr[j - gap] intValue] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = @temp;
        }
        gap /= 2;
    }
}

5. 힙 정렬 (Heap Sort)

완전 이진 트리 구조를 활용해 최댓값(또는 최솟값)을 루트 노드로 유지하면서 정렬한다. 먼저 주어진 배열을 대규모 힙(최대 힙)으로 변환한 후, 루트와 마지막 요소를 교환하고, 힙 크기를 줄여가며 다시 정렬한다. 이 과정을 반복하여 전체 배열을 오름차순으로 정렬한다. 시간 복잡도는 O(n log n).

- (void)heapSort:(NSMutableArray *)arr {
    NSInteger size = arr.count;
    // 최대 힙 구성
    for (NSInteger i = size / 2 - 1; i >= 0; i--) {
        [self heapify:arr size:size index:i];
    }
    // 힙 정렬
    while (size > 0) {
        [arr exchangeObjectAtIndex:0 withObjectAtIndex:size - 1];
        size--;
        [self heapify:arr size:size index:0];
    }
}

- (void)heapify:(NSMutableArray *)arr size:(NSInteger)size index:(NSInteger)root {
    NSInteger left = 2 * root + 1;
    NSInteger right = left + 1;
    NSInteger largest = root;

    if (left < size && [arr[left] intValue] > [arr[largest] intValue]) {
        largest = left;
    }
    if (right < size && [arr[right] intValue] > [arr[largest] intValue]) {
        largest = right;
    }

    if (largest != root) {
        [arr exchangeObjectAtIndex:root withObjectAtIndex:largest];
        [self heapify:arr size:size index:largest];
    }
}

6. 합병 정렬 (Merge Sort)

분할 정복 전략을 기반으로 하며, 배열을 두 부분으로 나누고, 각 부분을 재귀적으로 정렬한 후, 두 정렬된 배열을 합쳐서 하나의 정렬된 배열을 만든다. 모든 비교 연산에서 안정성(같은 값의 순서 유지)을 보장하며, 항상 O(n log n)의 시간 복잡도를 가진다.

- (NSArray *)mergeSort:(NSArray *)arr {
    if (arr.count <= 1) return arr;

    NSInteger mid = arr.count / 2;
    NSArray *left = [arr subarrayWithRange:NSMakeRange(0, mid)];
    NSArray *right = [arr subarrayWithRange:NSMakeRange(mid, arr.count - mid)];

    left = [self mergeSort:left];
    right = [self mergeSort:right];

    return [self merge:left right:right];
}

- (NSArray *)merge:(NSArray *)left right:(NSArray *)right {
    NSMutableArray *result = [NSMutableArray array];
    NSInteger i = 0, j = 0;

    while (i < left.count && j < right.count) {
        if ([left[i] floatValue] <= [right[j] floatValue]) {
            [result addObject:left[i++]];
        } else {
            [result addObject:right[j++]];
        }
    }

    while (i < left.count) [result addObject:left[i++]];
    while (j < right.count) [result addObject:right[j++]];

    return result;
}

7. 퀵 정렬 (Quick Sort)

피벗 값을 기준으로 배열을 두 부분으로 나누고, 왼쪽은 피벗보다 작고 오른쪽은 피벗보다 큰 요소들로 구성한다. 이후 각 부분에 대해 동일한 과정을 재귀적으로 반복하여 전체 배열을 정렬한다. 평균적인 성능은 O(n log n)이나, 최악의 경우 O(n²)가 될 수 있다.

- (void)quickSort:(NSMutableArray *)arr low:(int)low high:(int)high {
    if (low < high) {
        int pivotIndex = [self partition:arr low:low high:high];
        [self quickSort:arr low:low high:pivotIndex - 1];
        [self quickSort:arr low:pivotIndex + 1 high:high];
    }
}

- (int)partition:(NSMutableArray *)arr low:(int)low high:(int)high {
    int pivot = [arr[low] intValue];
    int left = low + 1;
    int right = high;

    while (YES) {
        while (left <= right && [arr[left] intValue] <= pivot) left++;
        while (left <= right && [arr[right] intValue] > pivot) right--;
        if (left > right) break;
        [arr exchangeObjectAtIndex:left withObjectAtIndex:right];
    }
    [arr exchangeObjectAtIndex:low withObjectAtIndex:right];
    return right;
}