Objective

Sort a in place with selection sort and return the exact number of comparisons between array elements that the sort performed.

Steps

• a points at n integers. Sort them in place, smallest first, and return how many times you compared one element against another.
• Selection sort, no other algorithm. For each position i from 0 up to n - 2, scan every element after i, remember the index of the smallest one, then swap that element into position i.
• The scan at position i tests a[j] against the current minimum once for every j after i, which is n - 1 - i comparisons. Over the whole sort that adds up to n * (n - 1) / 2. The count is decided by n alone: a shuffled input and an already sorted input of the same size return the same number.
• Swap unconditionally at the end of every outer step, including when the smallest remaining element already sits at i. Do not add a guard that skips the swap.
• n of 0 returns 0 and leaves the buffer alone. n of 1 returns 0 as well. Watch n - 1 when n is 0: size_t is unsigned, so that subtraction wraps to a huge value instead of going negative.
• Equal values stay in the output, do not collapse them. Any int can show up, INT_MIN and INT_MAX included. Never read or write outside a[0] through a[n - 1].
• Grademe grades the returned count and the array together. Up to ten values it prints the count then every element, like cost=10 [-4, -1, 0, 3, 7]. From a hundred values up, printing the buffer would be unreadable, so it prints the count then a fingerprint: the first element, the last, the sum, and whether the buffer came out in order. Returning n * (n - 1) / 2 without sorting anything turns sorted=yes into sorted=no.
• One test calls your function at n of 10, 100, 1000 and 10000 and prints the four counts one under the other. Multiply n by ten and the count grows by roughly a hundred. Read that table once the tests are green, it is the point of the exercise.

Objective

Sort a in place with selection sort and return the exact number of comparisons between array elements that the sort performed.

Steps

• a points at n integers. Sort them in place, smallest first, and return how many times you compared one element against another.
• Selection sort, no other algorithm. For each position i from 0 up to n - 2, scan every element after i, remember the index of the smallest one, then swap that element into position i.
• The scan at position i tests a[j] against the current minimum once for every j after i, which is n - 1 - i comparisons. Over the whole sort that adds up to n * (n - 1) / 2. The count is decided by n alone: a shuffled input and an already sorted input of the same size return the same number.
• Swap unconditionally at the end of every outer step, including when the smallest remaining element already sits at i. Do not add a guard that skips the swap.
• n of 0 returns 0 and leaves the buffer alone. n of 1 returns 0 as well. Watch n - 1 when n is 0: size_t is unsigned, so that subtraction wraps to a huge value instead of going negative.
• Equal values stay in the output, do not collapse them. Any int can show up, INT_MIN and INT_MAX included. Never read or write outside a[0] through a[n - 1].
• Grademe grades the returned count and the array together. Up to ten values it prints the count then every element, like cost=10 [-4, -1, 0, 3, 7]. From a hundred values up, printing the buffer would be unreadable, so it prints the count then a fingerprint: the first element, the last, the sum, and whether the buffer came out in order. Returning n * (n - 1) / 2 without sorting anything turns sorted=yes into sorted=no.
• One test calls your function at n of 10, 100, 1000 and 10000 and prints the four counts one under the other. Multiply n by ten and the count grows by roughly a hundred. Read that table once the tests are green, it is the point of the exercise.