Find how many numbers in an array are less than each number in the array

Question

#include <stdio.h>
int main(void) {
 int a[100],n,sum,i,j,b[100];
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
 scanf("%d",&a[i]);
 b[i]=0;
 for(j=0;j<i;j++)
 {
 if(a[i]>a[j]) b[i]++;
 else b[j]++;
 }
 }
 for(i=0;i<n;i++)
 printf("%d ",b[i]);
 return 0;
}

Here I'm trying to find how many numbers there are below a particular number.

This program takes the number of elements and the numbers themselves as the input. For example, n = 5 and the 5 numbers 2 8 6 1 5. This would give the output 1 4 3 0 2 since the number 2 is greater than 1, the number 8 is greater than 2, 6, 1 and 5, and so on.

• Annu: Its not a programming challenge question. Its a problem made by myself and i am curious to know whether we have optimised way to find that
• Annu: It takes the number of elements and the numbers as the input. For eg: n=5 and the elements are 2 8 6 1 5 then the output should be 1 4 3 0 2 because it gives the count of numbers less than a particular number.
• Gareth Rees: Where does the number 100 come from?
• Annu: Its just a number that i have taken for my array
• Gareth Rees: But why 100? Why not 200? Or 1000?

Answer 1

Spacing and good formatting is good for the soul. See:

#include <stdio.h>
int main(void) {
 int a[100];
 int b[100];
 int n;
 scanf("%d", &n);
 for (int i = 0; i < n; i++)
 {
 scanf("%d", &a[i]);
 b[i] = 0;
 for (int j = 0; j < i; j++)
 {
 if (a[i] > a[j])
 b[i]++;
 else
 b[j]++;
 }
 }
 for (int i = 0; i < n; i++)
 printf("%d ", b[i]);
 return 0;
}

(I am not personally a fan of dropping brackets on if or else, but it's somewhat wordy in this bracket style without doing so.)

Consider using zero initializer for b:

int b[100] = { 0 };

You can simplify the inner for by using an inline max:

for (int j = 0; j < i; j++)
 b[i > j ? i : j]++;

This does highlight a problem, though - you still increment one of them if they are equal. Try instead

for (int j = 0; j < i; j++)
 if (a[i] != a[j])
 b[a[i] > a[j] ? i : j]++;

I would also break this into two separate loops:

int main(void) {
 // Read input
 int n;
 scanf("%d", &n);
 int a[100];
 for (int i = 0; i < n; i++)
 scanf("%d", &a[i]);
 // Calculate
 int b[100] = { 0 };
 for (int i = 0; i < n; i++)
 for (int j = 0; j < i; j++)
 if (a[i] != a[j])
 b[a[i] > a[j] ? i : j]++;
 // Print output
 for (int i = 0; i < n; i++)
 printf("%d ", b[i]);
 return 0;
}

One should also use dynamic allocation if you want to support arbitrary-length input. Eg.

int *b = calloc(n, sizeof(int));
free(b)

This isn't as pretty, but doing all of this affords breaking it into separate functions.

#include <stdio.h>
#include <stdlib.h>
int *read_input(int *len) {
 scanf("%d", len);
 int *ret = malloc(*len * sizeof(int));
 for (int i = 0; i < *len; i++)
 scanf("%d", &ret[i]); 
 return ret; 
}
int *pairwise_lessthan_count(int *elems, int len) {
 int *ret = calloc(len, sizeof(int));
 for (int i = 0; i < len; i++)
 for (int j = 0; j < i; j++)
 if (elems[i] != elems[j])
 ret[elems[i] > elems[j] ? i : j]++;
 return ret;
}
void print_counts(int *elems, int len) {
 for (int i = 0; i < len; i++)
 printf("%d ", elems[i]);
 printf("\n");
}
int main(void) {
 int len;
 int *input = read_input(&len);
 int *output = pairwise_lessthan_count(input, len);
 print_counts(output, len);
 free(input);
 free(output);
}

This comes with a fair bit of boilerplate, but this should be more reusable and work in more general cases. To top it off, one might consider error checking (eg. the returns from malloc and scanf).

As a final blow, we might consider using janos' suggestion, hijacking off of JS1's implementation. To allow the comparison to work without globals, we can use pointers instead:

int ptr_cmp(const void *left, const void *right) {
 int a = **((int **)left);
 int b = **((int **)right);
 return (a > b) - (a < b);
}
int *pairwise_lessthan_count(int *elems, int len) {
 // Create an array of pointers
 int **indirect_array = malloc(len * sizeof(int *));
 for (int i = 0; i < len; i++)
 indirect_array[i] = elems + i;
 // Sort it through the indirection
 qsort(indirect_array, len, sizeof(*indirect_array), ptr_cmp);
 // Remove the indirection with pointer math
 int *ret = malloc(len * sizeof(int));
 for (int i = 0; i < len; i++)
 ret[i] = indirect_array[i] - elems;
 free(indirect_array);
 return ret;
}

Note that this is again going to have problems with duplicates, so that needs to be handled once again if it can arise.

• Annu: I have checked the code. Yours is not efficient than mine.
• Veedrac: @Annu None of my points are about efficiency. I did correct two potential errors though (the need to check if (a[i] != a[j]) and having n > 100). Are you actually worried about speed?
• Annu: Yup. Since i m talking about efficiency obviously its related to speed
• Toby Speight: Don't cast the result of malloc() and calloc() - as well as being ugly, it can mask a failure to include their header.
• Veedrac: @TobySpeight Fixed, thanks. I barely touch C, so this is as much a learning experience for me as it is for the OP.

Answer 2

You algorithm has \$O(N^2)\$ complexity: every number is compared to every other number.

And it's limited to distinct numbers: if 2 or more of the same number exist, the output will be incorrect.

You can improve the performance to \$O(N \log N)\,ドル by sorting the numbers and then iterating over the elements from small to big, and keeping track of the count.

• Annu: But how do i print the numbers in the order i mentioned... Its difficult rite??
• Veedrac: @Annu You'd probably want to sort a list of index-element pairs with an appropriate comparison function and use the indices to reconstruct the original order. But I'm not sure it's worth the bother unless you're actually worried about really large inputs.
• Annu: It would be of great help if you could provide the code and i want to test it for large data. :)
• twohundredping: @Annu \$[ 5, 2, 4, 7, 9, 8, 3] \Rightarrow \textrm{add indeces} \Rightarrow \\ [5 (0), 2(1), 4(2), 7(3), 9(4), 8(5), 3(6)] \Rightarrow \textrm{sort} \Rightarrow \\ [2(1), 3(6), 4(2), 5(0), 7(3), 8(5), 9(4)] \Rightarrow \textrm{calculate} \Rightarrow \\ [6, 5, 4, 3, 2, 1, 0] \Rightarrow \textrm{unsort} \Rightarrow \\ [-, 6, -, -, -, -, -] \Rightarrow \\ [-, 6, -, -, -, -, 5] \Rightarrow \\ [-, 6, 4, -, -, -, 5] \Rightarrow \\ [3, 6, 4, -, -, -, 5] \Rightarrow \\ [3, 6, 4, 2, -, -, 5] \Rightarrow \\ [3, 6, 4, 2, -, 1, 5] \Rightarrow \\ [3, 6, 4, 2, 0, 1, 5]\$

Answer 3

Example \$\mathcal{O}(n \log(n))\$ solution

This is a followup to Janos' review, and the question of "how do you actually sort the indices"? I wrote the following program to demonstrate how you could actually go about solving the problem in \$\mathcal{O}(n \log(n))\$ time. The comments in the program explain each step.

#include <stdio.h>
#include <stdlib.h>
#define MAXARRAY 100
int array[MAXARRAY];
int indexArray[MAXARRAY];
int outputArray[MAXARRAY];
int indexCompare(const void *i1, const void *i2);
int main(void)
{
 int i, n;
 scanf("%d",&n);
 if (n >= MAXARRAY)
 exit(1);
 for(i=0;i<n;i++) {
 scanf("%d",&array[i]);
 indexArray[i]=i;
 }
 // Initial state
 //
 // Index : [0] [1] [2] [3] [4]
 // Array : 2 8 6 1 5
 // IndexArray: 0 1 2 3 4
 // Now we want to sort the array. But instead of sorting the actual array,
 // we sort the index array. After we're done, indexArray will be sorted in
 // increasing order, such that:
 //
 // array[indexArray[0]] < array[indexArray[1]] < ... < array[indexArray[4]]
 qsort(indexArray, n, sizeof(array[0]), indexCompare);
 // After sorting indexArray
 //
 // Index : [0] [1] [2] [3] [4]
 // Array : 2 8 6 1 5
 // IndexArray: 3 0 4 2 1
 // IndexArray is useful because for each index, we know how many other
 // elements are less than it. For example, for index 2 (array[2] == 6),
 // we know that in the sorted indexArray, the value 2 appears in slot 3
 // (indexArray[3] == 2). That means that array[2] is bigger than 3 other
 // elements.
 //
 // In other words:
 //
 // array[indexArray[0]] is bigger than 0 elements.
 // array[indexArray[1]] is bigger than 1 elements.
 // ...
 //
 // Now we just need to print this information out in the original order.
 // So we create an output array where each slot holds how many numbers
 // the original number was bigger than.
 for (i=0;i<n;i++)
 outputArray[indexArray[i]] = i;
 // Index : [0] [1] [2] [3] [4]
 // Array : 2 8 6 1 5
 // IndexArray: 3 0 4 2 1
 // OutputArray: 1 4 3 0 2
 for(i=0;i<n;i++)
 printf("%d ", outputArray[i]);
 printf("\n");
 return 0;
}
int indexCompare(const void *i1, const void *i2)
{
 int index1 = *(int *) i1;
 int index2 = *(int *) i2;
 if (array[index1] < array[index2])
 return -1;
 if (array[index1] > array[index2])
 return 1;
 return 0;
}

Short review

As far as a review, I noticed that you must not have been compiling with warnings on because when I compiled your program I got a warning about sum being an unused variable. You should get in a habit of compiling with full warnings on.

Also, you can see that I changed your 100 into a #define. It's best to do that rather than copy and paste the number 100 all over the place. Or you could not have a fixed limit and just do everything dynamically.

• Veedrac: You can avoid globals if you use an array of pointers.
• JS1: @Veedrac I originally used qsort_r() to avoid globals, but I wasn't sure if that function existed everywhere. If you use pointers you have to do some pointer arithmetic later on to map back to the original index, which would require even more explanation. I'm trying to keep this as simple as possible for the OP.
• Annu: @JS1 I would appreciate if you could explain the compare function.
• JS1: @Annu The compare function is given pointers to two elements of indexArray. So for example, one pointer might point at the integer 0 and another at the integer 3. We want sort indexArray by the values of the original array. So we compare array[0] against array[3] in this example, and return 1, 0, or -1 depending on the comparison being greater, equal, or less than.