Sorting algorithms are the backbone of data manipulation, allowing you to arrange data in a specific order efficiently. In this exploration, we'll delve into four sorting algorithms: Selection Sort, Bubble Sort, Insertion Sort, and Quick Sort, along with understanding the concept of Big O notation for evaluating algorithm performance.

Selection Sort: Sorting with Precision

Objective: Learn how Selection Sort arranges elements by repeatedly finding the minimum element and placing it at the beginning of the unsorted portion.

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        int temp = arr[minIndex];
        arr[minIndex] = arr[i];
        arr[i] = temp;
    }
}

Bubble Sort: Bubbling Up Order

Objective: Understand Bubble Sort's approach of repeatedly swapping adjacent elements if they are in the wrong order.

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

Insertion Sort: Inserting with Precision

Objective: Grasp how Insertion Sort builds the final sorted array by repeatedly inserting elements into the already sorted portion.

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

Quick Sort: Dividing and Conquering

Objective: Explore Quick Sort's strategy of choosing a pivot element and partitioning the array into subarrays that are recursively sorted.

Lomuto Partition Scheme

int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; 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 quickSortLomuto(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = lomutoPartition(arr, low, high);
        quickSortLomuto(arr, low, pivotIndex - 1);
        quickSortLomuto(arr, pivotIndex + 1, high);
    }
}

Hoare Partition Scheme

int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low - 1;
    int j = high + 1;

    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);

        do {
            j--;
        } while (arr[j] > pivot);

        if (i >= j) {
            return j;
        }

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

void quickSortHoare(int arr[], int low, int high) {
    if (low < high) {
        int pivotIndex = hoarePartition(arr, low, high);
        quickSortHoare(arr, low, pivotIndex);
        quickSortHoare(arr, pivotIndex + 1, high);
    }
}

Big O Notation: Quantifying Performance

Objective: Understand how Big O notation measures an algorithm's efficiency based on its input size.

• O(1) – Constant Time: Operations with fixed execution time.

• O(n) – Linear Time: Operations linearly proportional to input size.

• O(n^2) – Quadratic Time: Operations that grow quadratically with input size.

• O(log n) – Logarithmic Time: Operations that grow logarithmically with input size.

• O(n log n) – Linearithmic Time: Common for efficient sorting algorithms.

Conclusion

By mastering these sorting algorithms and comprehending Big O notation, you gain the ability to tackle data manipulation challenges with elegance and efficiency. From selecting the right algorithm for the task to evaluating its time complexity, this journey empowers you to orchestrate the symphony of sorting algorithms in C.

Remember, practice is key to mastering these techniques. By integrating them into your programming endeavors, you'll create solutions that resonate with the precision and beauty of C programming.

---