Sort An Array According To The Order Defined By Another Array in C

Sorting arrays is a fundamental operation in programming, but sometimes the desired order isn't a simple ascending or descending sequence. What if the order is defined by the elements of another array? In this article, you will learn how to sort one array according to the custom order specified by a second array, exploring various practical approaches in C.

Problem Statement

The challenge is to rearrange the elements of a primary array, let's call it Array A, such that elements appearing in a secondary array, Order Array B, come first, in the exact sequence they appear in B. Any elements from A that are not present in B should follow afterwards, typically sorted in ascending order.

This problem is crucial in scenarios where data needs to be displayed or processed based on a specific, non-standard priority. For instance, in a task management system, you might want high-priority tasks (defined in Order Array B) to appear first, followed by regular tasks.

Example

Let's illustrate with an example:

Input Array A: [10, 30, 20, 50, 40, 20] Input Order Array B: [20, 10, 40]

Desired Output: [20, 20, 10, 40, 30, 50]

Explanation:

1. Elements 20, 10, 40 are in Order Array B. They should appear in A in this sequence.
2. 20 appears twice in A, so both instances come first.
3. Then 10.
4. Then 40.
5. Elements 30 and 50 are in A but not in B. They appear at the end, sorted in ascending order (30, 50).

 

Background & Knowledge Prerequisites

To effectively understand and implement the solutions presented, a basic understanding of the following C programming concepts is recommended:

• Variables, Data Types, and Operators: Fundamental building blocks of C programs.
• Arrays: How to declare, initialize, and access elements in one-dimensional arrays.
• Loops (for, while): Iterating over arrays and performing repetitive tasks.
• Functions: Defining and calling functions, especially understanding function pointers for qsort.
• Pointers: Essential for working with array elements and qsort's comparison function.
• Standard Library Functions: Familiarity with qsort for sorting, and potentially memset for initialization.
• Comparison Functions: How to write custom comparison logic for sorting algorithms.

 

Use Cases or Case Studies

This specific sorting problem finds applications in various real-world scenarios:

1. Custom UI Element Ordering: Displaying user interface components (e.g., tabs, menu items) in an order specified by a user's preferences, which might be stored as an array of IDs.
2. Prioritized Task Scheduling: In a system that processes tasks, certain task types might have higher priority. An Order Array B could define this priority, ensuring high-priority tasks are handled first.
3. Database Query Result Reordering: When fetching data from a database, the default sorting might not match a specific business logic requirement. This sorting method can reorder results based on a predefined list of primary keys or values.
4. Configuration File Processing: Processing configuration settings or application startup parameters in a precise sequence, where the order of processing for certain parameters is critical.
5. Network Protocol Packet Prioritization: In network traffic analysis or management, specific types of network packets might need to be processed before others, based on a predefined list of packet types or headers.

 

Solution Approaches

We will explore two distinct approaches to solve this problem, focusing on their implementation in C.

Approach 1: Using qsort with a Custom Comparator and Lookup Array

This approach leverages C's standard qsort function by providing a custom comparison logic. To achieve the custom order, we first create a "rank" or "priority" mapping for elements present in Order Array B.

One-line Summary: Create a lookup array (rank map) from Order Array B to assign priorities, then use qsort with a custom comparator that utilizes this rank map.

Code Example

// Sort Array by Another Array's Order (qsort with Lookup)
#include 
#include  // For qsort
#include  // For INT_MAX (to mark elements not in order array)
#include  // For memset

// A global array to store the ranks/priorities.
// We assume array elements are non-negative and within a reasonable range (e.g., 0-100).
// Adjust MAX_VAL based on the maximum possible value in your arrays.
#define MAX_VAL 101 // Assuming elements are 0-100
int rank_map[MAX_VAL];

// Comparison function for qsort
int compare(const void *a, const void *b) {
    int val1 = *(const int *)a;
    int val2 = *(const int *)b;

    int rank1 = (val1 >= 0 && val1 < MAX_VAL) ? rank_map[val1] : INT_MAX;
    int rank2 = (val2 >= 0 && val2 < MAX_VAL) ? rank_map[val2] : INT_MAX;

    // If ranks are different, sort by rank (lower rank first)
    if (rank1 != rank2) {
        return rank1 - rank2;
    } else {
        // If ranks are the same (either both are in order_array B and have same rank,
        // which means they are the same value, or both are NOT in order_array B),
        // then sort by their actual value in ascending order.
        return val1 - val2;
    }
}

int main() {
    int arr_A[] = {10, 30, 20, 50, 40, 20};
    int n_A = sizeof(arr_A) / sizeof(arr_A[0]);

    int order_B[] = {20, 10, 40};
    int n_B = sizeof(order_B) / sizeof(order_B[0]);

    // Step 1: Initialize rank_map.
    // Set all ranks to INT_MAX, indicating elements not in order_B.
    for (int i = 0; i < MAX_VAL; i++) {
        rank_map[i] = INT_MAX;
    }
    // Alternative: memset(rank_map, 0xFF, sizeof(rank_map)); // Sets to -1 if unsigned, or large positive if signed char

    // Step 2: Populate rank_map based on order_B.
    // Assign increasing ranks (0, 1, 2...) to elements in order_B.
    for (int i = 0; i < n_B; i++) {
        if (order_B[i] >= 0 && order_B[i] < MAX_VAL) {
            rank_map[order_B[i]] = i;
        }
    }

    // Step 3: Print original array for comparison.
    printf("Original Array A: [");
    for (int i = 0; i < n_A; i++) {
        printf("%d%s", arr_A[i], (i == n_A - 1) ? "" : ", ");
    }
    printf("]\\n");

    // Step 4: Sort arr_A using qsort with the custom comparator.
    qsort(arr_A, n_A, sizeof(int), compare);

    // Step 5: Print sorted array.
    printf("Sorted Array A:   [");
    for (int i = 0; i < n_A; i++) {
        printf("%d%s", arr_A[i], (i == n_A - 1) ? "" : ", ");
    }
    printf("]\\n");

    return 0;
}

Run

Sample Output

Original Array A: [10, 30, 20, 50, 40, 20]
Sorted Array A:   [20, 20, 10, 40, 30, 50]

 

Stepwise Explanation

1. Define MAXVAL and rankmap: We define MAXVAL to represent the maximum possible integer value an element can take (e.g., 100). The rankmap array, globally accessible, will store the "rank" or "priority" of each element. Its index corresponds to the element's value.
2. Initialize rankmap: All entries in rankmap are initially set to INTMAX. This high value signifies that an element is not present in Order Array B and thus has a lower priority (comes later) compared to elements that are in B.
3. Populate rankmap: We iterate through Order Array B. For each element orderB[i], we set rankmap[orderB[i]] = i. This assigns a lower rank (higher priority) to elements that appear earlier in Order Array B. For example, if 20 is orderB[0], rankmap[20] becomes 0.
4. Custom compare function:
   • This function is required by qsort. It receives two void pointers, which are cast to const int to access the integer values.

• For each value (val1, val2), it looks up its rank in rankmap. If the value is outside the MAXVAL range or its rankmap entry is still INTMAX, it means the element is not in Order Array B, so its effective rank remains INTMAX.
• Comparison Logic:
• If rank1 and rank2 are different, the element with the smaller rank comes first (rank1 - rank2).
• If rank1 and rank2 are the same:
• This means either both elements are from Order Array B and are the same value (e.g., two 20s), or both are not* in Order Array B.
• In this case, we fall back to sorting them by their actual integer value in ascending order (val1 - val2). This ensures elements not in B are sorted among themselves, and duplicates from B maintain a stable relative order (or are sorted if qsort is not stable for equal elements).

1. Call qsort: qsort(arrA, nA, sizeof(int), compare) is called to sort arrA using our custom compare function.

Approach 2: Brute-Force Placement

This method involves iterating through the Order Array B and explicitly placing elements into a new result array. It's conceptually simpler but can be less efficient for very large arrays.

One-line Summary: Iterate through the order array, find matching elements in the main array, place them into a result array, then append and sort any remaining elements.

Code Example

// Sort Array by Another Array's Order (Brute-Force)
#include 
#include  // For malloc, qsort
#include  // For bool type

// Comparison function for standard numeric sort of remaining elements
int compare_int(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr_A[] = {10, 30, 20, 50, 40, 20};
    int n_A = sizeof(arr_A) / sizeof(arr_A[0]);

    int order_B[] = {20, 10, 40};
    int n_B = sizeof(order_B) / sizeof(order_B[0]);

    // Step 1: Create a boolean array to track visited elements in arr_A.
    // Initialize all to false.
    bool visited[n_A];
    for (int i = 0; i < n_A; i++) {
        visited[i] = false;
    }

    // Step 2: Create a new array for the sorted result.
    int *result_arr = (int *)malloc(n_A * sizeof(int));
    if (result_arr == NULL) {
        perror("Failed to allocate memory");
        return 1;
    }
    int result_idx = 0;

    // Step 3: Iterate through order_B and populate result_arr.
    for (int i = 0; i < n_B; i++) {
        int target_val = order_B[i];
        for (int j = 0; j < n_A; j++) {
            if (!visited[j] && arr_A[j] == target_val) {
                result_arr[result_idx++] = arr_A[j];
                visited[j] = true; // Mark as visited
            }
        }
    }

    // Step 4: Collect remaining elements from arr_A (those not in order_B).
    int *remaining_elements = (int *)malloc(n_A * sizeof(int));
    if (remaining_elements == NULL) {
        perror("Failed to allocate memory");
        free(result_arr);
        return 1;
    }
    int remaining_count = 0;
    for (int i = 0; i < n_A; i++) {
        if (!visited[i]) {
            remaining_elements[remaining_count++] = arr_A[i];
        }
    }

    // Step 5: Sort the remaining elements.
    qsort(remaining_elements, remaining_count, sizeof(int), compare_int);

    // Step 6: Append sorted remaining elements to result_arr.
    for (int i = 0; i < remaining_count; i++) {
        result_arr[result_idx++] = remaining_elements[i];
    }

    // Step 7: Print original and sorted arrays.
    printf("Original Array A: [");
    for (int i = 0; i < n_A; i++) {
        printf("%d%s", arr_A[i], (i == n_A - 1) ? "" : ", ");
    }
    printf("]\\n");

    printf("Sorted Array A:   [");
    for (int i = 0; i < n_A; i++) {
        printf("%d%s", result_arr[i], (i == n_A - 1) ? "" : ", ");
    }
    printf("]\\n");

    // Step 8: Free dynamically allocated memory.
    free(result_arr);
    free(remaining_elements);

    return 0;
}

Run

Sample Output

Original Array A: [10, 30, 20, 50, 40, 20]
Sorted Array A:   [20, 20, 10, 40, 30, 50]

 

Stepwise Explanation

1. Initialize visited array: A boolean array visited of the same size as arrA is created and initialized to false. This helps track which elements from arrA have already been placed in the resultarr.
2. Initialize resultarr: A new array resultarr is dynamically allocated to store the final sorted output. resultidx tracks the current insertion point.
3. Process Order Array B:
   • We iterate through each targetval in orderB.

• For each targetval, we then iterate through arrA.
• If an element arrA[j] matches targetval and has not been visited yet, it's added to resultarr, and visited[j] is set to true. This ensures elements from B are placed in the correct order, including duplicates from A.

1. Collect Remaining Elements: After processing all elements defined by orderB, we iterate through arrA again. Any element arrA[i] for which visited[i] is still false is an element not specified in orderB. These are collected into a separate remainingelements array.
2. Sort Remaining Elements: The remainingelements array is then sorted in ascending order using qsort with a standard integer comparison function.
3. Append to Result: The sorted remainingelements are appended to the resultarr.
4. Output and Cleanup: The final resultarr is printed, and all dynamically allocated memory is freed.

Conclusion

Sorting an array according to the order defined by another array is a common problem with elegant solutions.

• Approach 1 (qsort with Lookup Array) is generally more efficient for larger datasets, especially when the range of element values is manageable for creating a lookup map. It leverages the highly optimized qsort algorithm and a constant-time lookup for priorities.
• Approach 2 (Brute-Force Placement) is simpler to understand and implement for smaller datasets or when the element values are very sparse (making a large lookup array inefficient). However, its nested loops can lead to O(N*M) complexity in the worst case (where N is size of A, M is size of B), plus additional passes for remaining elements.

 

Choosing the right approach depends on the size of your arrays, the range of element values, and performance requirements. For typical use cases in C, the qsort approach with a lookup array often provides a good balance of performance and clarity.

Summary

• Problem: Rearrange Array A based on the custom order of elements in Order Array B, followed by remaining elements from A (sorted).
• Approach 1 (Optimal for many cases):
• Create a rankmap array where rankmap[value] stores its index/priority from Order Array B.
• Elements not in Order Array B are assigned a very low priority (e.g., INTMAX).
• Use qsort with a custom comparison function that uses rankmap to determine the order.
• If ranks are equal, sort by actual value.
• Approach 2 (Simple, for smaller N):
• Use a visited array to track elements from A already placed.
• Iterate Order Array B, find matching unvisited elements in A, and place them into a result array.
• Collect all unvisited (remaining) elements from A.
• Sort the remaining elements.
• Append sorted remaining elements to result.
• Key Consideration: The range of values in Array A dictates the feasibility of rankmap size in Approach 1. If values are very large and sparse, a hash map (not directly covered in C here without additional data structures) might be more suitable than a direct array lookup.

---

Challenge Yourself!

Now that you've explored these sorting techniques, try to implement one of the following:

1. Refine Approach 1: Modify the rankmap to use a more dynamic data structure like a hash table if the MAXVAL assumption is not practical for your data.
2. Combine Concepts: Imagine Array A contains structs (e.g., struct Person { int id; char name[50]; }). How would you adapt the qsort approach if Order Array B contains id values?
3. Performance Test: Compare the execution time of both approaches for different array sizes (N) and different ranges of values. What do you observe?