Bubble Sort

Bubble Sort is a simple comparison-based algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted.

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

Selection Sort

Selection Sort divides the input list into a sorted and an unsorted region. It repeatedly selects the smallest (or largest, depending on sorting order) element from the unsorted region and moves it to the end of the sorted region.

void selection_sort(int *arr, int size) {
    for (int i = 0; i < size - 1; ++i) {
        int min_index = i;
        for (int j = i + 1; j < size; ++j) {
            if (arr[j] < arr[min_index]) {
                min_index = j;
            }
        }
        if (min_index != i) {
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }
    }
}

Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms like quicksort, heapsort, or merge sort.

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

Shell Sort

Shell Sort is a generalization of insertion sort that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every h-th element produces a sorted list.

void shell_sort(int *arr, int size) {
    for (int gap = size / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < size; ++i) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

Merge Sort

Merge Sort is an efficient, stable, comparison-based, divide and conquer algorithm. It divides the input array into two halves, recursively sorts them, and then merges the sorted halves.

void merge(int *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }

    free(L);
    free(R);
}

void merge_sort(int *arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

Quick Sort

Quick Sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.

int partition(int *arr, int low, int high) {
    // Median-of-three pivot selection to improve performance
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }
    if (arr[mid] > arr[high]) {
        int temp = arr[mid];
        arr[mid] = arr[high];
        arr[high] = temp;
    }
    if (arr[low] > arr[mid]) {
        int temp = arr[low];
        arr[low] = arr[mid];
        arr[mid] = temp;
    }
    int pivot = arr[mid];

    int i = low - 1;
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}

void quick_sort(int *arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

Heap Sort

Heap Sort is a comparison-based sorting technique based on a Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place it at the end. We repeat the same process for the remaining elements.

static inline int left_child(int i) { return 2 * i + 1; }
static inline int right_child(int i) { return 2 * i + 2; }
static inline int parent(int i) { return (i - 1) / 2; }

void max_heapify(int *arr, int size, int i) {
    int largest = i;
    int left = left_child(i);
    int right = right_child(i);

    if (left < size && arr[left] > arr[largest])
        largest = left;

    if (right < size && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        max_heapify(arr, size, largest);
    }
}

void build_max_heap(int *arr, int size) {
    for (int i = size / 2 - 1; i >= 0; --i)
        max_heapify(arr, size, i);
}

void heap_sort(int *arr, int size) {
    build_max_heap(arr, size);
    for (int i = size - 1; i > 0; --i) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        max_heapify(arr, i, 0);
    }
}

Counting Sort

Counting Sort is an integer sorting algorithm, not a comparison-based algorithm. It operates by counting the number of objects that have each distinct key value.

void counting_sort(int *arr, int size, int max_val) {
    int *output = (int *)malloc(size * sizeof(int));
    int *count = (int *)calloc(max_val + 1, sizeof(int));

    for (int i = 0; i < size; ++i)
        ++count[arr[i]];

    for (int i = 1; i <= max_val; ++i)
        count[i] += count[i - 1];

    for (int i = size - 1; i >= 0; --i) {
        output[count[arr[i]] - 1] = arr[i];
        --count[arr[i]];
    }

    for (int i = 0; i < size; ++i)
        arr[i] = output[i];

    free(count);
    free(output);
}

Radix Sort

Radix Sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.

int max_element(int *arr, int size) {
    int max = arr[0];
    for (int i = 1; i < size; ++i)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

void radix_sort(int *arr, int size) {
    int max = max_element(arr, size);
    int *output = (int *)malloc(size * sizeof(int));
    int *count = (int *)calloc(10, sizeof(int));

    for (int exp = 1; max / exp > 0; exp *= 10) {
        memset(count, 0, 10 * sizeof(int));

        for (int i = 0; i < size; ++i)
            ++count[(arr[i] / exp) % 10];

        for (int i = 1; i < 10; ++i)
            count[i] += count[i - 1];

        for (int i = size - 1; i >= 0; --i) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            --count[(arr[i] / exp) % 10];
        }

        for (int i = 0; i < size; ++i)
            arr[i] = output[i];
    }

    free(output);
    free(count);
}

Bucket Sort

Bucket Sort is a comparison sort algorithm that operates on elements by dividing them into different buckets and then sorting these buckets individually, either using a different sorting algorithm or recursively applying the bucket sorting algorithm.

void bucket_sort(int *arr, int size, int max_val) {
    int *buckets = (int *)calloc(max_val + 1, sizeof(int));
    for (int i = 0; i < size; ++i)
        buckets[arr[i]] = arr[i];

    int index = 0;
    for (int i = 0; i <= max_val; ++i) {
        if (buckets[i] != 0) {
            arr[index++] = buckets[i];
        }
    }
    free(buckets);
}

Algorithm Comparison

Sorting algorithms can be categorized as either comparison-based or non-comparison-based.

• Comparison Sorts (e.g., Quick Sort, Merge Sort, Heap Sort, Insertion Sort, Shell Sort, Selection Sort, Bubble Sort) rely on comparing elements to determine their order. In the worst case, any comparison sort requires at least O(n log n) comparisons.
• Non-Comparison Sorts (e.g., Radix Sort, Counting Sort, Bucket Sort) do not compare elements directly. They can achieve linear time complexity O(n) but have restrictions, such as requiring integer keys and additional space.

Comparison sorts offer greater flexibility, as the comparision function can be customized to sort various data types and orders. Non-comparison sorts are often faster for specific data types but less adaptable.

Stability

A sorting algorithm is stable if it preserves the relative order of equal elements. Stability is important when sorting data that has multiple keys.

• Stable Sorts: Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Radix Sort, Bucket Sort.
• Unstable Sorts: Selection Sort, Shell Sort, Heap Sort, Quick Sort.

Performance Summary