Sort An Array According To The Order Defined By Another Array In

Sorting an array based on a predefined order from another array is a common challenge in programming, requiring careful consideration of element priority and arrangement. This task often arises when specific items need to appear first or in a particular sequence, followed by other elements sorted naturally. In this article, you will learn how to sort an array according to the order defined by another array in C, exploring various approaches to tackle this specific sorting challenge.

Problem Statement

The problem requires sorting a primary array (arraytosort) based on the order of elements in a secondary array (orderarray). Elements present in orderarray should appear first in the sorted arraytosort, maintaining the relative order defined by orderarray. Any elements in arraytosort that are not found in orderarray should appear after all the ordered elements, sorted in their natural (ascending) order. This specific sorting can be crucial in scenarios where certain data points need to be prioritized and presented in a custom sequence.

For example, given: arraytosort = {10, 20, 11, 4, 20, 4, 10, 30} orderarray = {4, 10, 20}

The desired output after sorting arraytosort would be: {4, 4, 10, 10, 20, 20, 11, 30}

Notice that 4 appears twice, then 10 twice, then 20 twice—all in the order specified by orderarray. The elements 11 and 30, which are not in orderarray, appear at the end, sorted naturally (11 before 30).

• Custom Data Display: Displaying items in a user interface (e.g., product categories, menu items) where a specific set of categories needs to be shown first in a predefined sequence.
• Task Prioritization: Sorting a list of tasks where certain critical tasks (defined in orderarray) must appear at the top in a specific order, followed by other tasks sorted by their urgency or due date.
• Log File Analysis: Ordering log entries based on a set of critical event types (e.g., ERROR, WARNING, INFO) so that severe events are analyzed first, followed by less critical ones.
• Database Query Results: Implementing custom ORDER BY clauses for database query results where the default alphabetical or numerical sort isn't sufficient, and a specific order of certain values is required.
• Network Packet Processing: Prioritizing network packets based on their type or protocol, processing high-priority packets first.

Solution Approaches

We will explore two distinct approaches to solve this problem, each with its own advantages and suitable scenarios.

Approach 1: Frequency Counting and Direct Placement (Suitable for limited value ranges)

This approach is efficient when the values in arraytosort and orderarray are positive integers within a manageable range. It involves counting the occurrences of each number in arraytosort and then reconstructing the sorted array based on orderarray and the remaining elements.

• One-line summary: Use a frequency array to count elements in the primary array, then iterate through the order array to place corresponding elements, and finally append remaining elements in sorted order.

• Code Example:

// Sort Array by Order Array - Frequency Counting
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <string.h> // For memset

#define MAX_VAL 1001 // Assuming values are between 0 and 1000

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

void sortByOrderArray_Frequency(int arr[], int n, int order_arr[], int m) {
    int freq[MAX_VAL];
    memset(freq, 0, sizeof(freq)); // Initialize frequency array to zeros

    // Step 1: Count frequencies of all elements in arr
    for (int i = 0; i < n; i++) {
        if (arr[i] >= 0 && arr[i] < MAX_VAL) {
            freq[arr[i]]++;
        }
    }

    int current_index = 0;

    // Step 2: Place elements according to order_arr
    for (int i = 0; i < m; i++) {
        int val = order_arr[i];
        if (val >= 0 && val < MAX_VAL) {
            while (freq[val] > 0) {
                arr[current_index++] = val;
                freq[val]--;
            }
        }
    }

    // Step 3: Collect remaining elements and sort them
    int remaining_elements[n]; // Max possible remaining elements
    int remaining_count = 0;
    for (int i = 0; i < MAX_VAL; i++) {
        while (freq[i] > 0) {
            remaining_elements[remaining_count++] = i;
            freq[i]--;
        }
    }

    // Sort the remaining elements
    qsort(remaining_elements, remaining_count, sizeof(int), compare_integers);

    // Step 4: Append sorted remaining elements to arr
    for (int i = 0; i < remaining_count; i++) {
        arr[current_index++] = remaining_elements[i];
    }
}

int main() {
    // Step 1: Define arrays
    int arr[] = {10, 20, 11, 4, 20, 4, 10, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    int order_arr[] = {4, 10, 20};
    int m = sizeof(order_arr) / sizeof(order_arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\nOrder array: ");
    for (int i = 0; i < m; i++) {
        printf("%d ", order_arr[i]);
    }
    printf("\\n\\n");

    // Step 2: Sort the array
    sortByOrderArray_Frequency(arr, n, order_arr, m);

    // Step 3: Print the sorted array
    printf("Sorted array (Frequency Counting): ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Another example
    int arr2[] = {5, 2, 8, 5, 6, 3, 2};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int order_arr2[] = {2, 5};
    int m2 = sizeof(order_arr2) / sizeof(order_arr2[0]);

    printf("\\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\nOrder array 2: ");
    for (int i = 0; i < m2; i++) {
        printf("%d ", order_arr2[i]);
    }
    printf("\\n\\n");

    sortByOrderArray_Frequency(arr2, n2, order_arr2, m2);

    printf("Sorted array 2 (Frequency Counting): ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");

    return 0;
}

Run

• Sample Output:

Original array: 10 20 11 4 20 4 10 30 
Order array: 4 10 20 

Sorted array (Frequency Counting): 4 4 10 10 20 20 11 30 

Original array 2: 5 2 8 5 6 3 2 
Order array 2: 2 5 

Sorted array 2 (Frequency Counting): 2 2 5 5 3 6 8

• Stepwise Explanation:

1. Initialize Frequency Array: A freq array (or hash map for larger/non-integer values) is created and initialized to zeros. Its size (MAXVAL) should cover the maximum possible value in arr.
2. Count Occurrences: Iterate through arr and increment the count for each element in the freq array. This builds a tally of how many times each number appears.
3. Place Ordered Elements: Iterate through orderarr. For each element val in orderarr, repeatedly place val into arr as many times as its count in freq, decrementing freq[val] with each placement. This ensures elements specified in orderarr are placed first and in the correct sequence.
4. Collect Remaining Elements: Iterate through the freq array (from index 0 to MAXVAL-1). Any elements that still have a count greater than zero are those that were in arr but not in orderarr. Collect these into a temporary remainingelements array.
5. Sort Remaining Elements: Use qsort to sort the remainingelements array in ascending order.
6. Append Remaining Elements: Append the sorted remainingelements to arr, starting from where the ordered elements left off.

This approach is more flexible as it does not rely on a limited range of integer values and can be adapted for custom data types. It involves creating a mapping that assigns a "rank" or "priority" to elements based on their position in orderarray. This mapping is then used within a custom comparison function for qsort.

• One-line summary: Create a lookup table (map) for the order array elements to assign them a priority, then use qsort with a custom comparison function that prioritizes elements based on this map.

• Code Example:

// Sort Array by Order Array - Custom qsort
#include <stdio.h>
#include <stdlib.h> // For qsort
#include <limits.h> // For INT_MAX

// Define a maximum value for the order map if elements are integers within a range.
// For very large or sparse integers, a hash map structure would be needed.
#define MAP_SIZE 1001 
int order_map[MAP_SIZE]; // Global or passed for simplicity, stores rank

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

    // Get the rank/priority of val1
    int rank1 = (val1 >= 0 && val1 < MAP_SIZE && order_map[val1] != INT_MAX) ? order_map[val1] : INT_MAX;

    // Get the rank/priority of val2
    int rank2 = (val2 >= 0 && val2 < MAP_SIZE && order_map[val2] != INT_MAX) ? order_map[val2] : INT_MAX;

    // If both are in order_arr, compare by their ranks
    if (rank1 != INT_MAX && rank2 != INT_MAX) {
        return rank1 - rank2;
    }
    // If only val1 is in order_arr, val1 comes first
    else if (rank1 != INT_MAX) {
        return -1;
    }
    // If only val2 is in order_arr, val2 comes first
    else if (rank2 != INT_MAX) {
        return 1;
    }
    // If neither is in order_arr, compare naturally (ascending)
    else {
        return val1 - val2;
    }
}

void sortByOrderArray_qsort(int arr[], int n, int order_arr[], int m) {
    // Step 1: Initialize order_map
    for (int i = 0; i < MAP_SIZE; i++) {
        order_map[i] = INT_MAX; // Use INT_MAX to signify not in order_arr
    }

    // Step 2: Populate order_map with ranks
    for (int i = 0; i < m; i++) {
        if (order_arr[i] >= 0 && order_arr[i] < MAP_SIZE) {
            order_map[order_arr[i]] = i; // Store index as rank
        }
    }

    // Step 3: Sort arr using the custom comparison function
    qsort(arr, n, sizeof(int), compare_custom_order);
}

int main() {
    // Step 1: Define arrays
    int arr[] = {10, 20, 11, 4, 20, 4, 10, 30};
    int n = sizeof(arr) / sizeof(arr[0]);
    int order_arr[] = {4, 10, 20};
    int m = sizeof(order_arr) / sizeof(order_arr[0]);

    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\nOrder array: ");
    for (int i = 0; i < m; i++) {
        printf("%d ", order_arr[i]);
    }
    printf("\\n\\n");

    // Step 2: Sort the array
    sortByOrderArray_qsort(arr, n, order_arr, m);

    // Step 3: Print the sorted array
    printf("Sorted array (Custom qsort): ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Another example
    int arr2[] = {5, 2, 8, 5, 6, 3, 2};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    int order_arr2[] = {2, 5};
    int m2 = sizeof(order_arr2) / sizeof(order_arr2[0]);

    printf("\\nOriginal array 2: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\nOrder array 2: ");
    for (int i = 0; i < m2; i++) {
        printf("%d ", order_arr2[i]);
    }
    printf("\\n\\n");

    sortByOrderArray_qsort(arr2, n2, order_arr2, m2);

    printf("Sorted array 2 (Custom qsort): ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");

    return 0;
}

Run

• Sample Output:

Original array: 10 20 11 4 20 4 10 30 
Order array: 4 10 20 

Sorted array (Custom qsort): 4 4 10 10 20 20 11 30 

Original array 2: 5 2 8 5 6 3 2 
Order array 2: 2 5 

Sorted array 2 (Custom qsort): 2 2 5 5 3 6 8

• Stepwise Explanation:

1. Initialize Order Map: A ordermap array is created. Each index in this map represents a possible value from arr. It is initialized with a default "high priority" value (like INTMAX) to indicate that an element is not in orderarr.
2. Populate Order Map: Iterate through orderarr. For each element orderarr[i], set ordermap[orderarr[i]] = i. This assigns a lower "rank" (smaller index means higher priority) to elements that appear earlier in orderarr.
3. Custom Comparison Function (comparecustomorder):
   • When qsort needs to compare two elements (val1, val2) from arr, this function is called.

1. Sort with qsort: Call qsort on arr, providing comparecustomorder as the custom comparison function. qsort will use this logic to arrange the elements.

• The problem involves sorting a primary array (arraytosort) based on the element order in a secondary array (orderarray).
• Elements in orderarray take precedence and maintain their relative order.
• Elements not in orderarray are placed at the end, sorted naturally.
• Approach 1 (Frequency Counting): Suitable for positive integers within a limited range. Involves counting element frequencies, placing ordered elements, then sorting and appending remaining elements.
• Approach 2 (Custom qsort): More general. Creates an ordermap to assign priorities (ranks) to elements from orderarray. Uses qsort with a custom comparison function that leverages these priorities, falling back to natural sorting for elements not in the order_array.
• The choice of approach depends on data characteristics (value range, type) and performance needs.