1. O(n) 시간 복잡도로 정렬하기 주어진 배열은 1부터 n까지의 서로 다른 정수로 구성되어 있으며, 각 요소는 1 ≤ a[i] ≤ n 범위에 있다. 이 조건을 활용하여, 보조 배열에 직접 위치를 매핑함으로써 O(n) 시간 내에 오름차순 정렬을 수행할 수 있다.

void sortToPosition(int src[], int size, int dest[]) {
    for (int idx = 0; idx < size; idx++) {
        dest[src[idx] - 1] = src[idx];
    }
}

2. 양방향 버블 정렬 (Bidirectional Bubble Sort) 정렬 과정에서 앞뒤로 번갈아가며 스캔하며 최솟값과 최댓값을 각각 맨 앞으로, 맨 뒤로 이동시키는 방식이다. 이로 인해 반복 횟수가 줄어들고 성능이 개선된다.

void bidirectionalBubbleSort(ElemType arr[], int length) {
    int left = 0, right = length - 1;
    bool hasSwapped = true;

    while (hasSwapped) {
        hasSwapped = false;

        // 왼쪽에서 오른쪽으로 스캔: 최대값을 우측 끝으로 이동
        for (int i = left; i < right; i++) {
            if (arr[i].key > arr[i + 1].key) {
                swap(arr[i], arr[i + 1]);
                hasSwapped = true;
            }
        }
        right--;

        // 오른쪽에서 왼쪽으로 스캔: 최솟값을 좌측 끝으로 이동
        for (int i = right; i > left; i--) {
            if (arr[i].key < arr[i - 1].key) {
                swap(arr[i], arr[i - 1]);
                hasSwapped = true;
            }
        }
        left++;
    }
}

3. 상위 m개 원소 선택 (단순 선택 정렬 기반) 전체 정렬 없이, 가장 큰 m개 요소만 선택하여 정렬하는 알고리즘. 단순 선택 정렬을 활용하여 각 단계에서 최댓값을 찾아 앞부분에 배치한다.

void selectTopM(ElemType data[], int total, int m) {
    for (int i = 0; i < m; i++) {
        int maxIndex = i;
        for (int j = i + 1; j < total; j++) {
            if (data[j].key > data[maxIndex].key) {
                maxIndex = j;
            }
        }
        if (maxIndex != i) {
            swap(data[i], data[maxIndex]);
        }
    }
}

4. 퀵선택 알고리즘: 제 k번째 작은 원소 찾기 퀵소트의 분할 전략을 이용해 전체 정렬 없이도 특정 순서의 원소를 효율적으로 찾을 수 있다. 재귀적 분할을 통해 타겟 인덱스에 도달할 때까지 좌우 부분을 탐색한다.

int quickSelect(ElemType* array, int start, int end, int k) {
    if (start >= end) {
        return array[start].key;
    }

    int pivotIdx = start;
    ElemType pivot = array[pivotIdx];

    int left = start + 1;
    int right = end;

    while (left <= right) {
        while (left <= right && array[left].key <= pivot.key) left++;
        while (left <= right && array[right].key >= pivot.key) right--;
        if (left < right) {
            swap(array[left], array[right]);
        }
    }

    swap(array[start], array[right]);

    if (k - 1 == right) {
        return array[right].key;
    } else if (k - 1 < right) {
        return quickSelect(array, start, right - 1, k);
    } else {
        return quickSelect(array, right + 1, end, k);
    }
}

5. 0, 1, 2 값만 포함된 배열의 기수 정렬 키 값이 0, 1, 2뿐인 경우, 기수 정렬을 사용하여 선형 시간에 정렬 가능하다. 각 값에 따라 세 개의 연결 리스트(큐)로 나누고, 순차적으로 합쳐서 결과를 생성한다.

typedef struct Node {
RecType record;
struct Node* next;
} ListNode;

void radixSortThreeValues(RecType arr[], int n) {
ListNode* heads[3] = {NULL};
ListNode* tails[3] = {NULL};

// 각 요소를 키 값에 따라 적절한 리스트에 추가
for (int i = 0; i < n; i++) {
int key = arr[i].key;
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->record = arr[i];
newNode->next = NULL;

if (heads[key] == NULL) {
heads[key] = newNode;
tails[key] = newNode;
} else {
tails[key]->next = newNode;
tails[key] = newNode;
}
}

// 리스트들을 순서대로 연결
ListNode* resultHead = NULL;
ListNode* resultTail = NULL;

for (int i = 0; i < 3; i++) {
if (heads[i] != NULL) {
if (resultHead == NULL) {
resultHead = heads[i];
resultTail = tails[i];
} else {
resultTail->next = heads[i];
resultTail = tails[i];
}
}
}

// 결과를 원본 배열로 복사
ListNode* curr = resultHead;
int idx = 0;
while (curr != NULL) {
arr[idx++] = curr->record;
curr = curr->next;
}
}