Position of an element after stable sort - GeeksforGeeks

Position of an element after stable sort - GeeksforGeeks
Given an array of integers which may contain duplicate elements, an element of this array is given to us, we need to tell the final position of this element in the array, if a stable sort algorithm is applied.

One easy way to solve this problem is to use any stable sorting algorithm like Insertion Sort, Merge Sort etc and then get the new index of given element but we can solve this problem without sorting the array.
As position of an element in a sorted array is decided by only those elements which are smaller than given element. We count all array elements smaller than given element and for those elements which are equal to given element, elements occurring before given elements’ index will be included in count of smaller elements this will insure the stability of the result’s index.

int getIndexInSortedArray(int arr[], int n, int idx)

{

    /*  Count of elements smaller than current

        element plus the equal element occurring

        before given index*/

    int result = 0;

    for (int i = 0; i < n; i++)

    {

        // If element is smaller then increase

        // the smaller count

        if (arr[i] < arr[idx])

            result++;

 

        // If element is equal then increase count

        // only if it occurs before

        if (arr[i] == arr[idx] && i < idx)

            result++;

    }

    return result;

}

Read full article from Position of an element after stable sort - GeeksforGeeks