Sort an array by value and index in C

Question

Your task is to sort an array of integer numbers by the product of the value and the index of the positions.

For sorting the index starts at 1, NOT at 0! The sorting has to be ascending. The array will never be null and will always contain numbers.

My solution

int* sortByValueAndIndex(int* array, int arrayLength) {
  int* extraArray = malloc(arrayLength * sizeof(int)); 

  for (int index = 0; index < arrayLength; index++) {
    extraArray[index] = array[index] * (index + 1);
  }

  /* Bubble sort */
  for (int firstIndex = 0; firstIndex < arrayLength - 1; firstIndex++) {
    for (int secondIndex = 0; secondIndex < arrayLength - firstIndex - 1; secondIndex++) {
      if (extraArray[secondIndex] > extraArray[secondIndex + 1]) {

        int tmp = array[secondIndex];
        array[secondIndex] = array[secondIndex + 1];
        array[secondIndex + 1] = tmp;

        tmp = extraArray[secondIndex];
        extraArray[secondIndex] = extraArray[secondIndex + 1];
        extraArray[secondIndex + 1] = tmp;
      }
    }
  }

  free(extraArray);

  return array;
}

Answer 1

Well, your code works, though it needs \$O(n)\$ space and \$O(n^2)\$ time.

It's also quite cleanly implemented, so kudos.

Still, there's naturally something which can be improved:

1. If you need a generic loop-index, the natural name is i. If you need a second one, ask for j. Yes, they are short, but they are the standard names, so you cannot get more descriptive.

2. Your additional array's name should reflect its use: Call it keys.

3. You have a general tendency for long names. Try to keep it as brief as you can without sacrificing clarity.

4. Avoid using a type with sizeof. If the receiving variable ever changes its type, you have to keep it in sync manually, and its not idiomatic. Use:

   int* keys = malloc(arrayLength * sizeof *keys);
   

5. You assume that malloc() won't fail. You know assume makes an ass out of u and me?

6. Do you know that signed integer-overflow is Undefined Behavior? I didn't find anywhere in the problem-description a guarantee that array[i] * (i + 1) won't overflow, so you might want to use a bigger type for the keys.

7. Should you really write your own sub-standard sorting-algorithm, or can you use the one in the standard-library?

The following trades more extra-space for using qsort(), which should have \$O(n * \log(n))\$ runtime:

typedef struct pair {
    long long key;
    int value;
} pair;

static int sortByValueAndIndex_comp(const void* pa, const void* pb) {
    long long a = ((pair*)pa)->key;
    long long b = ((pair*)pb)->key;
    return (a > b) - (a < b);
}

int* sortByValueAndIndex(int* arr, int n) {
    assert(arr || !n);
    assert(INT_MAX <= LLONG_MAX / INT_MAX);
    pair* kv = malloc(n * sizeof *kv);
    if (!kv)
        return 0;

    for (int i = n; i-- > 0;) {
        kv[i].key = arr[i] * (i + 1LL);
        kv[i].value = arr[i];
    }

    qsort(kv, n, sizeof *kv, sortByValueAndIndex_comp);

    for (int i = n; i-- > 0;)
        arr[i] = kv[i].value;

    free(kv);
    return arr;
}