Bubble Sort - O(N²)

Concept

Bubble sort works by repeatedly compairng adjcaent elements and swapping them if they're in wrong order. For ascending order, each pass moves the largest unsorted element to its correct position at the end of the array.

Implementation

void bubble_sort(int* arr, int size) {
    for (int round = 0; round < size - 1; round++) {
        for (int idx = 0; idx < size - 1 - round; idx++) {
            if (arr[idx] > arr[idx + 1]) {
                int temp = arr[idx];
                arr[idx] = arr[idx + 1];
                arr[idx + 1] = temp;
            }
        }
    }
}

The time complexity remains O(N²).

Selection Sort - O(N²)

Concept

Selection sort finds the minimum element in the unsorted portion and places it at the beginning. An optimized version finds both minimum and maximum in each pass, placing them at both ends.

Implementation

void selection_sort(int* arr, int size) {
    int start = 0, finish = size - 1;
    
    while (start < finish) {
        int min_idx = start, max_idx = start;
        
        for (int current = start; current <= finish; current++) {
            if (arr[current] < arr[min_idx]) {
                min_idx = current;
            }
            if (arr[current] > arr[max_idx]) {
                max_idx = current;
            }
        }
        
        // Swap minimum to start
        int temp = arr[start];
        arr[start] = arr[min_idx];
        arr[min_idx] = temp;
        
        // Handle case where max was originally at start position
        if (finish == min_idx) {
            max_idx = min_idx;
        }
        
        // Swap maximum to end
        temp = arr[finish];
        arr[finish] = arr[max_idx];
        arr[max_idx] = temp;
        
        start++;
        finish--;
    }
}

Time complexity is O(N²).

Insertion Sort - O(N²)

Concept

Insertion sort builds the sorted array one element at a time. It takes each element and inserts it into its correct position among the already sorted elements.

Implementation

void insertion_sort(int* arr, int size) {
    for (int boundary = 0; boundary < size - 1; boundary++) {
        int next_val = arr[boundary + 1];
        int pos = boundary;
        
        while (pos >= 0 && arr[pos] > next_val) {
            arr[pos + 1] = arr[pos];
            pos--;
        }
        
        arr[pos + 1] = next_val;
    }
}

Time complexity is O(N²).

Shell Sort

Concept

Shell sort improves insertion sort by allowing exchanges of elemants far apart. It uses a gap sequence that starts large and reduces to 1, effectively making it an optimized insertion sort.

Implementation

void shell_sort(int* arr, int size) {
    int gap = size;
    
    while (gap > 1) {
        gap = gap / 3 + 1;
        
        for (int start = 0; start < gap; start++) {
            for (int current = start; current < size - gap; current += gap) {
                int next_val = arr[current + gap];
                int pos = current;
                
                while (pos >= 0 && arr[pos] > next_val) {
                    arr[pos + gap] = arr[pos];
                    pos -= gap;
                }
                
                arr[pos + gap] = next_val;
            }
        }
    }
}

Time complexity is approximately O(N^1.3).

Heap Sort - O(N log N)

Concept

Heap sort builds a max heap from the array, then repeatedly extracts the maximum element (root) and places it at the end of the array.

Implementation

void heapify_down(int* arr, int size, int root) {
    int parent = root;
    int child = parent * 2 + 1;
    
    while (child < size) {
        if (child + 1 < size && arr[child] < arr[child + 1]) {
            child++;
        }
        
        if (arr[child] > arr[parent]) {
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
            
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

void heap_sort(int* arr, int size) {
    // Build max heap
    for (int i = (size - 2) / 2; i >= 0; i--) {
        heapify_down(arr, size, i);
    }
    
    // Extract elements from heap
    for (int end = size - 1; end > 0; end--) {
        int temp = arr[0];
        arr[0] = arr[end];
        arr[end] = temp;
        
        heapify_down(arr, end, 0);
    }
}

Time complexity is O(N log N).

Quick Sort - O(N log N)

Hoare Partition Method

Quick sort selects a pivot element and partitions the array so that elements smaller than the pivot come before it, and larger elements come after it.

int hoare_partition(int* arr, int low, int high) {
    int pivot = arr[low];
    int left = low, right = high;
    
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            right--;
        }
        while (left < right && arr[left] <= pivot) {
            left++;
        }
        
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }
    
    int temp = arr[low];
    arr[low] = arr[left];
    arr[left] = temp;
    
    return left;
}

void quick_sort_hoare(int* arr, int low, int high) {
    if (low >= high) return;
    
    int partition_idx = hoare_partition(arr, low, high);
    quick_sort_hoare(arr, low, partition_idx - 1);
    quick_sort_hoare(arr, partition_idx + 1, high);
}

Three-Way Median Optimization

int median_of_three(int* arr, int low, int high) {
    int mid = low + (high - low) / 2;
    
    if (arr[low] > arr[mid]) {
        if (arr[mid] > arr[high]) {
            return mid;
        } else if (arr[low] > arr[high]) {
            return high;
        } else {
            return low;
        }
    } else {
        if (arr[low] > arr[high]) {
            return low;
        } else if (arr[mid] > arr[high]) {
            return high;
        } else {
            return mid;
        }
    }
}

Merge Sort - O(N log N)

Concept

Merge sort divides the array into halves recursively until single elements remain, then merges the sorted halves back together.

Implementation

void merge_arrays(int* arr, int* temp, int left, int mid, int right) {
    int i = left, j = mid + 1, k = left;
    
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

void merge_sort_recursive(int* arr, int* temp, int left, int right) {
    if (left >= right) return;
    
    int mid = left + (right - left) / 2;
    merge_sort_recursive(arr, temp, left, mid);
    merge_sort_recursive(arr, temp, mid + 1, right);
    merge_arrays(arr, temp, left, mid, right);
}

void merge_sort(int* arr, int size) {
    int* temp = malloc(size * sizeof(int));
    if (!temp) return;
    
    merge_sort_recursive(arr, temp, 0, size - 1);
    free(temp);
}

Counting Sort

Concept

Counting sort counts occurrences of each value and reconstructs the sorted array based on these counts. It's efficient when the range of values is not significantly greater than the number of elements.

Implementation

void counting_sort(int* arr, int size) {
    int max_val = arr[0], min_val = arr[0];
    
    for (int i = 1; i < size; i++) {
        if (arr[i] > max_val) max_val = arr[i];
        if (arr[i] < min_val) min_val = arr[i];
    }
    
    int range = max_val - min_val + 1;
    int* count = calloc(range, sizeof(int));
    if (!count) return;
    
    for (int i = 0; i < size; i++) {
        count[arr[i] - min_val]++;
    }
    
    int index = 0;
    for (int val = 0; val < range; val++) {
        while (count[val]-- > 0) {
            arr[index++] = val + min_val;
        }
    }
    
    free(count);
}