Example: Sorting-Based Subset Check in C

// Sorting-Based Subset Check
#include <stdio.h>
#include <stdlib.h> // For qsort

// Comparison function for qsort
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// Function to check if arr2 is a subset of arr1 using sorting
bool isSubsetSorted(int arr1[], int m, int arr2[], int n) {
    if (n > m) { // If arr2 is larger than arr1, it cannot be a subset
        return false;
    }

    // Step 1: Sort both arrays
    qsort(arr1, m, sizeof(int), compare);
    qsort(arr2, n, sizeof(int), compare);

    // Step 2: Use two pointers to compare elements
    int i = 0; // Pointer for arr1
    int j = 0; // Pointer for arr2

    while (i < m && j < n) {
        if (arr1[i] == arr2[j]) {
            // Elements match, move both pointers
            i++;
            j++;
        } else if (arr1[i] < arr2[j]) {
            // arr1[i] is smaller, so it cannot match arr2[j]
            // Move arr1 pointer to find a potentially matching element
            i++;
        } else { // arr1[i] > arr2[j]
            // arr2[j] is not found in arr1 from this point onwards
            // because arr1[i] is already larger, and both are sorted.
            return false;
        }
    }

    // If j reached the end, all elements of arr2 were found in arr1
    return (j == n);
}

int main() {
    // Step 1: Define test cases (same as brute-force for consistency)
    int arr1_a[] = {10, 5, 2, 23, 19};
    int m_a = sizeof(arr1_a) / sizeof(arr1_a[0]);
    int arr2_a[] = {19, 5, 2};
    int n_a = sizeof(arr2_a) / sizeof(arr2_a[0]);

    int arr1_b[] = {1, 2, 3, 4, 5, 6};
    int m_b = sizeof(arr1_b) / sizeof(arr1_b[0]);
    int arr2_b[] = {1, 2, 7};
    int n_b = sizeof(arr2_b) / sizeof(arr2_b[0]);
    
    int arr1_c[] = {1, 2, 2, 3};
    int m_c = sizeof(arr1_c) / sizeof(arr1_c[0]);
    int arr2_c[] = {1, 2, 2};
    int n_c = sizeof(arr2_c) / sizeof(arr2_c[0]);

    int arr1_d[] = {1, 2, 3};
    int m_d = sizeof(arr1_d) / sizeof(arr1_d[0]);
    int arr2_d[] = {1, 2, 2}; // arr2 has two 2s, arr1 has only one
    int n_d = sizeof(arr2_d) / sizeof(arr2_d[0]);

    // Step 2: Test the sorting-based function
    printf("Test Case A (Sorted): arr1={10,5,2,23,19}, arr2={19,5,2}\n");
    if (isSubsetSorted(arr1_a, m_a, arr2_a, n_a)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case B (Sorted): arr1={1,2,3,4,5,6}, arr2={1,2,7}\n");
    if (isSubsetSorted(arr1_b, m_b, arr2_b, n_b)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case C (Sorted Multiset Success): arr1={1,2,2,3}, arr2={1,2,2}\n");
    if (isSubsetSorted(arr1_c, m_c, arr2_c, n_c)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    printf("Test Case D (Sorted Multiset Failure): arr1={1,2,3}, arr2={1,2,2}\n");
    if (isSubsetSorted(arr1_d, m_d, arr2_d, n_d)) {
        printf("arr2 is a subset of arr1\n\n");
    } else {
        printf("arr2 is NOT a subset of arr1\n\n");
    }

    return 0;
}