Advanced Sorting and Searching in C Q&A

1. What are advanced sorting and searching algorithms?

Advanced sorting algorithms (e.g., Merge Sort, Quick Sort, Counting Sort, Radix Sort) offer better performance than basic sorts (e.g., Bubble Sort) for large datasets. Advanced searching typically involves optimized techniques like binary search variants or indexing, but this response focuses on sorting as per query.

2. Why use advanced sorting algorithms?

Advanced sorting algorithms provide better time complexity (e.g., O(n log n) or O(n) for special cases) and scalability for large datasets, making them suitable for performance-critical applications like databases or real-time systems in C.

3. What are key characteristics of advanced sorting algorithms?

4. What is Merge Sort?

Merge Sort is a divide-and-conquer sorting algorithm that recursively divides an array into two halves, sorts each half, and merges them into a sorted array. It's stable and guarantees O(n log n) time.

5. How does Merge Sort work?

6. Can you give an example of Merge Sort in C?

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1, n2 = r - m;
    int* L = (int*)malloc(n1 * sizeof(int));
    int* R = (int*)malloc(n2 * sizeof(int));

    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int i = 0; i < n2; i++) R[i] = arr[m + 1 + i];

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

    free(L);
    free(R);
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}

7. What are time and space complexities of Merge Sort?

Time Complexity:

Space Complexity: O(n) (temporary arrays for merging).

8. What are advantages and disadvantages of Merge Sort?

9. What is Quick Sort?

Quick Sort is a divide-and-conquer sorting algorithm that selects a pivot, partitions the array around it (smaller elements before, larger after), and recursively sorts the subarrays. It's in-place but not stable.

10. How does Quick Sort work?

11. Can you give an example of Quick Sort in C?

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(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++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    quickSort(arr, 0, n - 1);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 5 8 9
    return 0;
}

12. What are time and space complexities of Quick Sort?

Time Complexity:

Space Complexity: O(log n) (recursion stack, in-place for array).

13. What are advantages and disadvantages of Quick Sort?

14. How can you improve Quick Sort's performance?

15. What is Counting Sort?

Counting Sort is a non-comparison-based sorting algorithm that counts occurrences of each value in a range and uses these counts to place elements in sorted order. It's efficient for small integer ranges.

16. How does Counting Sort work?

17. Can you give an example of Counting Sort in C?

#include <stdio.h>
#include <stdlib.h>

void countingSort(int arr[], int n, int max) {
    int* count = (int*)calloc(max + 1, sizeof(int));
    int* output = (int*)malloc(n * sizeof(int));

    // Count occurrences
    for (int i = 0; i < n; i++) count[arr[i]]++;

    // Cumulative count
    for (int i = 1; i <= max; i++) count[i] += count[i - 1];

    // Build output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    // Copy to original array
    for (int i = 0; i < n; i++) arr[i] = output[i];

    free(count);
    free(output);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = 7, max = 8;
    countingSort(arr, n, max);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 1 2 2 3 3 4 8
    return 0;
}

18. What are time and space complexities of Counting Sort?

Time Complexity: O(n + k) (n = array size, k = range of values).

Space Complexity: O(n + k) (count and output arrays).

19. What are advantages and disadvantages of Counting Sort?

20. What is Radix Sort?

Radix Sort is a non-comparison-based sorting algorithm that sorts integers by processing digits (e.g., least significant digit to most significant) using a stable subroutine like Counting Sort.

21. How does Radix Sort work?

22. Can you give an example of Radix Sort in C?

#include <stdio.h>
#include <stdlib.h>

void countingSortByDigit(int arr[], int n, int exp) {
    int* output = (int*)malloc(n * sizeof(int));
    int count[10] = {0};

    // Count occurrences of digits
    for (int i = 0; i < n; i++) count[(arr[i] / exp) % 10]++;

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

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

    // Copy to original array
    for (int i = 0; i < n; i++) arr[i] = output[i];

    free(output);
}

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) if (arr[i] > max) max = arr[i];

    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, n, exp);
    }
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = 8;
    radixSort(arr, n);
    for (int i = 0; i < n; i++) printf("%d ", arr[i]); // Output: 2 24 45 66 75 90 170 802
    return 0;
}

23. What are time and space complexities of Radix Sort?

Time Complexity: O(d(n + k)) (d = number of digits, n = array size, k = digit range, usually 10).

Space Complexity: O(n + k) (output and count arrays).

24. What are advantages and disadvantages of Radix Sort?

25. How do Merge Sort, Quick Sort, Counting Sort, and Radix Sort compare?

26. What are the time complexities for best, worst, and average cases?

Merge Sort:

Quick Sort:

Counting Sort:

Radix Sort:

27. When to use each sorting algorithm?

28. Are these algorithms stable or in-place?