selection sort swap formula code example

Example: The number of swaps required in selection sort

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
ll a[111111], tmp[111111], ans;
 
void merge_sort(ll a[], ll b[], ll lo, ll hi)
{
    ll i, j, k;
 
    if (lo >= hi)
        return;
 
    ll mid = (lo + hi) / 2;
 
    merge_sort(a, b, lo, mid);
    merge_sort(a, b, mid + 1, hi);
 
    i = lo;
    j = mid + 1;
 
    for (k = lo; k <= hi; k++)
        if (j > hi)
            b[k] = a[i++];
        else if (i > mid)
            b[k] = a[j++];
        else if (a[i] <= a[j])
            b[k] = a[i++];
        else
        {
            b[k] = a[j++];
            ans += mid - i + 1;
        }
 
    for (i = lo; i <= hi; i++)
        a[i] = b[i];
}
 
int main(void)
{
    ll t;
 
    scanf("%lld", &t);
 
    while (t--)
    {
        ll n, i;
 
        scanf("%lld", &n);
        for (i = 1; i <= n; i++)
            scanf("%lld", &a[i]);
 
        ans = 0;
        merge_sort(a, tmp, 1, n);
 
        printf("%lld\n", ans);
    }
    return 0;
}