Replace Each Element Of The Array By Its Rank In The Array

An array's elements often carry intrinsic value, but sometimes their relative standing—their "rank"—is more informative.

Understanding how to replace actual values with their ranks can simplify analysis and data representation.

In this article, you will learn how to replace each element of an array with its rank, where identical values share the same rank and ranks are 1-based.

Problem Statement

The task is to transform an array by replacing each numerical element with its "rank" within the array. The rank is defined as the 1-based position an element would have if the array were sorted. If multiple elements have the same value, they should all be assigned the same rank.

This problem is crucial in scenarios like competitive scoring, data compression, or when you need to understand the relative position of data points rather than their absolute magnitudes. For instance, knowing that a student scored in the "top 10%" (rank-based) might be more insightful than just knowing their raw score.

Example

Let's consider an input array: [10, 20, 10, 30, 5]

The desired output, after replacing elements with their 1-based ranks, would be: [2, 3, 2, 4, 1]

Here's why:

• The smallest distinct value is 5, so it gets rank 1.
• The next distinct value is 10. Both 10s get rank 2.
• The next distinct value is 20, so it gets rank 3.
• The largest distinct value is 30, so it gets rank 4.

 

Background & Knowledge Prerequisites

To follow along with the solutions, you should have a basic understanding of:

• C Language Fundamentals: Variables, data types, arrays, loops, and functions.
• Structures (structs): How to define and use custom data structures in C.
• Pointers: Basic pointer arithmetic and how they are used with arrays and functions.
• Sorting Algorithms: Specifically, familiarity with the qsort standard library function and how to provide a custom comparison function.

 

Use Cases or Case Studies

1. Competitive Ranking: In a competition, raw scores might vary wildly, but converting them to ranks (e.g., 1st, 2nd, 3rd) provides a standardized way to evaluate performance relative to others.
2. Data Analysis and Visualization: When dealing with skewed data distributions, ranking can normalize the data, making it easier to compare different datasets or visualize trends without extreme outliers dominating the view.
3. Sparse Data Representation: In some algorithms, the absolute values of data points are less important than their relative ordering. Replacing values with ranks can sometimes simplify algorithms or reduce memory usage if ranks can be stored more compactly.
4. Feature Engineering in Machine Learning: Ranking numerical features can sometimes improve model performance by making the features less sensitive to outliers and preserving the ordinal relationship between values.

Solution Approaches

We will explore a robust method that effectively handles duplicate values by assigning them the same rank.

Approach 1: Using Value-Index Pairs and Sorting

This approach involves creating temporary data structures to keep track of the original positions while sorting values. This ensures that ranks are correctly mapped back to their original array positions.

One-line Summary: Create auxiliary pairs of (value, original index), sort them by value, and then iterate to assign 1-based ranks back to the original positions, handling duplicates appropriately.

Code Example:

// Replace Array Elements by Rank
#include <stdio.h>
#include <stdlib.h> // Required for qsort

// Structure to hold an element's value and its original index
typedef struct {
    int value;
    int original_index;
} Element;

// Comparison function for qsort: sorts Element structs by their 'value'
int compareElements(const void *a, const void *b) {
    return ((Element *)a)->value - ((Element *)b)->value;
}

// Function to replace array elements by their ranks
void replaceWithRanks(int arr[], int n) {
    // Step 1: Create an array of Element structs
    Element *elements = (Element *)malloc(n * sizeof(Element));
    if (elements == NULL) {
        fprintf(stderr, "Memory allocation failed!\\n");
        return;
    }

    // Step 2: Populate the elements array with values and original indices
    for (int i = 0; i < n; i++) {
        elements[i].value = arr[i];
        elements[i].original_index = i;
    }

    // Step 3: Sort the elements array based on their values
    qsort(elements, n, sizeof(Element), compareElements);

    // Step 4: Create a temporary array to store ranks based on original indices
    int *ranks = (int *)malloc(n * sizeof(int));
    if (ranks == NULL) {
        fprintf(stderr, "Memory allocation failed!\\n");
        free(elements);
        return;
    }

    // Step 5: Assign ranks to the original positions
    int current_rank = 1;
    for (int i = 0; i < n; i++) {
        // If it's not the first element and current value is different from previous
        if (i > 0 && elements[i].value != elements[i-1].value) {
            current_rank++;
        }
        // Store the current_rank at the original position of this element
        ranks[elements[i].original_index] = current_rank;
    }

    // Step 6: Replace the original array elements with their calculated ranks
    for (int i = 0; i < n; i++) {
        arr[i] = ranks[i];
    }

    // Step 7: Free dynamically allocated memory
    free(elements);
    free(ranks);
}

int main() {
    // Original array
    int arr[] = {10, 20, 10, 30, 5, 20};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    // Replace elements with their ranks
    replaceWithRanks(arr, n);

    printf("Array with ranks: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Another example
    int arr2[] = {7, 3, 7, 1, 9, 3};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);

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

    replaceWithRanks(arr2, n2);

    printf("Array 2 with ranks: ");
    for (int i = 0; i < n2; i++) {
        printf("%d ", arr2[i]);
    }
    printf("\\n");

    return 0;
}

Run

Sample Output:

 

Stepwise Explanation:

1. Define Element Structure: A struct Element is created to store both the value of an array element and its originalindex. This is crucial because sorting will change the order of elements, but we need to know where each element originally came from.
2. Comparison Function: compareElements is a standard comparison function required by qsort. It takes two void pointers, casts them to Element, and returns the difference of their value fields for ascending order sorting.
3. Allocate and Populate elements Array: Dynamic memory is allocated for an array of Element structs, equal to the size of the input array. This elements array is then populated by iterating through the original arr, storing each value and its index.
4. Sort elements Array: The qsort function is called to sort the elements array. This arranges all elements based on their value in ascending order, while keeping their originalindex intact within each Element struct.
5. Allocate ranks Array: Another dynamic array ranks is allocated. This array will temporarily hold the calculated ranks, mapped to their original indices, before updating the input array.
6. Assign Ranks:
   • A currentrank variable is initialized to 1.

• We iterate through the sorted* elements array.
• For each element:
• If it's not the first element and its value is different from the previous element's value (in the sorted list), it means we've encountered a new distinct value, so currentrank is incremented.
• The currentrank is then stored in the ranks array at the position indicated by elements[i].originalindex. This ensures the rank goes to the correct spot.

1. Update Original Array: Finally, we iterate through the ranks array and copy its values back into the original arr, effectively replacing each element with its calculated rank.
2. Free Memory: Dynamically allocated memory for elements and ranks is freed to prevent memory leaks.

 

Conclusion

Replacing array elements with their ranks is a common and useful transformation in data processing. The detailed approach using auxiliary value-index pairs and sorting, as demonstrated, provides a robust and efficient way to achieve this, correctly handling duplicate values by assigning them the same rank. This method ensures that the relative ordering of elements is captured, offering a foundation for further analysis or specific algorithm requirements.

Summary

• Problem: Replace array elements with their 1-based ranks, where identical values share the same rank.
• Key Idea: Use a temporary data structure to store both element value and original index to preserve mapping during sorting.
• Steps for Solution:

1. Create (value, originalindex) pairs for each array element.
2. Sort these pairs based on their values.
3. Iterate through the sorted pairs to assign ranks: increment rank only when a new distinct value is encountered.
4. Store the assigned rank back into a result array at the originalindex.
5. Update the original array with the calculated ranks.
   • Use Cases: Competitive ranking, data normalization, sparse data representation, feature engineering.

• Prerequisites: C language basics, structs, qsort, dynamic memory allocation.

---

Challenge Your Understanding!

1. Modify the replaceWithRanks function to assign "skip ranks". This means if there are three elements with rank 2, the next unique value would get rank 5 (1 + 3 + 1). For example, [10, 20, 10, 30] would become [2, 4, 2, 5] (10 gets rank 2, 20 gets rank 4 because 10 appears twice, 30 gets rank 5).
2. What would happen if you skipped step 7 (freeing memory) in the replaceWithRanks function? Why is it important in C?
3. Consider an array with negative numbers or zero. Will the provided solution work correctly? Why or why not?