Q10041: Vito's family

/*
    Sorting first, and find the median.
    At last, calculating the distance.
    Run time: 0.060
*/
#include <stdio.h>
int sort(int *arr, int n);
int median(int n);
void swap(int &a, int &b);

int main()
{
    int num;
    int n; // number of neighbor
    int i;

    scanf("%d", &num);
    while (num--)
    {
        scanf("%d", &n);
        int arr[n];

        for ( i = 0; i < n; i++)
            scanf("%d", &arr[i]);

        printf("%d\n", sort(arr, n));
    }

    return 0;
}

int sort(int *arr, int n)
{
    int i, j;
    int max;
    int index;
    int sum = 0;

    // using selection sort
    for ( i = 0; i < n-1; i++)
    {
        max = arr[0];
        index = 0;
        for ( j = 0; j < n-i; j++)
        {
            if (arr[j] > max)
            {
                max = arr[j];
                index = j;
            }
        }
        swap(arr[index], arr[j-1]);
    }

    // find median
    index = median(n);

    for ( i = 0; i < n; i++)
        sum += (arr[i] >= arr[index]) ? arr[i]-arr[index] : arr[index] - arr[i];

    return sum;
}

int median(int n)
{
    return n%2 ? (n+1)/2-1 : n/2-1;
}

void swap(int &a, int &b)
{
    int tmp = a;
    a = b;
    b = tmp;
}