Sorted Adjacent Differences (Codeforces 1339B)
Tags: Others, sortings

You have array of $$$n$$$ numbers $$$a_{1}, a_{2}, \ldots, a_{n}$$$. Rearrange these numbers to satisfy $$$|a_{1} - a_{2}| \le |a_{2} - a_{3}| \le \ldots \le |a_{n-1} - a_{n}|$$$, where $$$|x|$$$ denotes absolute value of $$$x$$$. It's always possible to find such rearrangement.Note that all numbers in $$$a$$$ are not necessarily different. In other words, some numbers of $$$a$$$ may be same.You have to answer independent $$$t$$$ test cases.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.The first line of each test case contains single integer $$$n$$$ ($$$3 \le n \le 10^{5}$$$) — the length of array $$$a$$$. It is guaranteed that the sum of values of $$$n$$$ over all test cases in the input does not exceed $$$10^{5}$$$.The second line of each test case contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$-10^{9} \le a_{i} \le 10^{9}$$$).

Output: For each test case, print the rearranged version of array $$$a$$$ which satisfies given condition. If there are multiple valid rearrangements, print any of them.

Note: In the first test case, after given rearrangement, $$$|a_{1} - a_{2}| = 0 \le |a_{2} - a_{3}| = 1 \le |a_{3} - a_{4}| = 2 \le |a_{4} - a_{5}| = 2 \le |a_{5} - a_{6}| = 10$$$. There are other possible answers like "5 4 5 6 -2 8".In the second test case, after given rearrangement, $$$|a_{1} - a_{2}| = 1 \le |a_{2} - a_{3}| = 2 \le |a_{3} - a_{4}| = 4$$$. There are other possible answers like "2 4 8 1".

Sample Inputs:
2
6
5 -2 4 8 6 5
4
8 1 4 2

Sample Outputs:
5 5 4 6 8 -2
1 2 4 8

Solution (Python):
t = ''
for _ in range(int(input())):
    a = int(input())
    A = sorted(list(map(int, input().split())))
    b = a // 2
    B = []
    for i in range(a):
        if i % 2 == 0:
            b += i
        else:
            b -= i
        B += [str(A[b])]
    t += ' '.join(B) + '\n'
print(t)

Solution (Python):
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = []
    (i, j) = (0, 0)
    if len(a) % 2:
        ans.append(a[len(a) >> 1])
        i = (len(a) >> 1) - 1
        j = (len(a) >> 1) + 1
    else:
        i = len(a) - 1 >> 1
        j = len(a) >> 1
    while i >= 0:
        ans.append(a[j])
        ans.append(a[i])
        i -= 1
        j += 1
    print(' '.join(map(str, ans)))

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    s = sorted(list(map(int, input().split())))
    mid = n // 2
    ans = []
    if n % 2:
        mid = mid
        ans.append(s[mid])
        i = mid - 1
        j = mid + 1
        while i >= 0:
            ans.append(s[i])
            ans.append(s[j])
            i -= 1
            j += 1
    else:
        mid -= 1
        ans.append(s[mid])
        ans.append(s[mid + 1])
        i = mid - 1
        j = mid + 2
        while i >= 0:
            ans.append(s[i])
            ans.append(s[j])
            i -= 1
            j += 1
    print(*ans)