Inversion SwapSort (Codeforces 1375E)
Tags: Greedy, sortings

Madeline has an array $$$a$$$ of $$$n$$$ integers. A pair $$$(u, v)$$$ of integers forms an inversion in $$$a$$$ if:  $$$1 \le u < v \le n$$$.  $$$a_u > a_v$$$. Madeline recently found a magical paper, which allows her to write two indices $$$u$$$ and $$$v$$$ and swap the values $$$a_u$$$ and $$$a_v$$$. Being bored, she decided to write a list of pairs $$$(u_i, v_i)$$$ with the following conditions:  all the pairs in the list are distinct and form an inversion in $$$a$$$.  all the pairs that form an inversion in $$$a$$$ are in the list.  Starting from the given array, if you swap the values at indices $$$u_1$$$ and $$$v_1$$$, then the values at indices $$$u_2$$$ and $$$v_2$$$ and so on, then after all pairs are processed, the array $$$a$$$ will be sorted in non-decreasing order. Construct such a list or determine that no such list exists. If there are multiple possible answers, you may find any of them.

Input: The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the array.Next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(1 \le a_i \le 10^9)$$$  — elements of the array.

Output: Print -1 if no such list exists. Otherwise in the first line you should print a single integer $$$m$$$ ($$$0 \le m \le \dfrac{n(n-1)}{2}$$$) — number of pairs in the list.The $$$i$$$-th of the following $$$m$$$ lines should contain two integers $$$u_i, v_i$$$ ($$$1 \le u_i < v_i\le n$$$).If there are multiple possible answers, you may find any of them.

Note: In the first sample test case the array will change in this order $$$[3,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]$$$.In the second sample test case it will be $$$[1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]$$$.In the third sample test case the array is already sorted.

Sample Inputs:
3
3 1 2

4
1 8 1 6

5
1 1 1 2 2

Sample Outputs:
2
1 3
1 2

2
2 4
2 3

0

Solution (Python):
from collections import defaultdict
import sys, math
f = None
try:
    f = open('q1.input', 'r')
except IOError:
    f = sys.stdin
if 'xrange' in dir(__builtins__):
    range = xrange
sys.setrecursionlimit(10 ** 2)

def print_case_iterable(case_num, iterable):
    print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
    print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
    print(' '.join(A))

def read_int():
    return int(f.readline().strip())

def read_int_array():
    return [int(x) for x in f.readline().strip().split(' ')]

def rns():
    a = [x for x in f.readline().split(' ')]
    return (int(a[0]), a[1].strip())

def read_string():
    return list(f.readline().strip())

def ri():
    return int(f.readline().strip())

def ria():
    return [int(x) for x in f.readline().strip().split(' ')]

def rns():
    a = [x for x in f.readline().split(' ')]
    return (int(a[0]), a[1].strip())

def rs():
    return list(f.readline().strip())

def bi(x):
    return bin(x)[2:]
from collections import deque
import math
NUMBER = 10 ** 9 + 7

def factorial(n):
    M = NUMBER
    f = 1
    for i in range(1, n + 1):
        f = f * i % M
    return f

def mult(a, b):
    return a * b % NUMBER

def minus(a, b):
    return (a - b) % NUMBER

def plus(a, b):
    return (a + b) % NUMBER

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        (g, y, x) = egcd(b % a, a)
        return (g, x - b // a * y, y)

def modinv(a):
    m = NUMBER
    (g, x, y) = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def choose(n, k):
    if n < k:
        assert false
    return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER
from collections import deque, defaultdict
import heapq
from types import GeneratorType

def bootstrap(f, stack=[]):

    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc

def dfs(g, timeIn, timeOut, depths, parents):
    cnt = 0
    stack = [[1, 0, 0, 0]]
    while stack:
        (v, neig_i, parent, depth) = stack[-1]
        parents[v] = parent
        depths[v] = depth
        if neig_i == 0:
            timeIn[v] = cnt
            cnt += 1
        while neig_i < len(g[v]):
            u = g[v][neig_i]
            if u == parent:
                neig_i += 1
                continue
            stack[-1][1] = neig_i + 1
            stack.append([u, 0, v, depth + 1])
            break
        if neig_i == len(g[v]):
            stack.pop()
            timeOut[v] = cnt
            cnt += 1
cnt = 0

@bootstrap
def dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):
    global cnt
    parents[v] = parent
    depths[v] = depth
    timeIn[v] = cnt
    cnt += 1
    for u in adj[v]:
        if u == parent:
            continue
        yield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)
    timeOut[v] = cnt
    cnt += 1
    yield

def gcd(a, b):
    if a == 0:
        return b
    return gcd(b % a, a)

def lcm(a, b):
    return a * b / gcd(a, b)

def get_num_2_5(n):
    twos = 0
    fives = 0
    while n > 0 and n % 2 == 0:
        n //= 2
        twos += 1
    while n > 0 and n % 5 == 0:
        n //= 5
        fives += 1
    return (twos, fives)

def shift(a, i, num):
    for _ in range(num):
        (a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def find_mex(a, m):
    b = sorted([x - m for x in a])
    if b[0] > 0:
        return m
    last = 0
    for i in range(len(b)):
        if b[i] > last + 1:
            return last + 1 + m
        last = b[i]
    return b[len(b) - 1] + m + 1

def solution(a, n):
    sol = []
    b = sorted([(a[i], i) for i in range(n)], reverse=True)
    for (x, i) in b:
        for j in range(i):
            if a[j] > a[i]:
                sol.append(f'{j + 1} {i + 1}')
    sol = [f'{len(sol)}'] + sol
    return '\n'.join(sol)

def main():
    T = 1
    for i in range(T):
        n = ri()
        a = ria()
        x = solution(a, n)
        if 'xrange' not in dir(__builtins__):
            print(x)
        else:
            (print >> output, str(x))
    if 'xrange' in dir(__builtins__):
        print(output.getvalue())
        output.close()
if 'xrange' in dir(__builtins__):
    import cStringIO
    output = cStringIO.StringIO()
if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = tuple(map(int, input().split()))
psorted = sorted(((j, -a[i], -i) for i in range(n) for j in range(i) if a[i] < a[j]))
print(len(psorted))
for (i, _, j) in psorted:
    print(i + 1, -(j - 1))

Solution (Python):
n = int(input())
a = tuple(map(int, input().split()))
psorted = sorted(((j, -a[i], -i) for i in range(n) for j in range(i) if a[i] < a[j]))
print(len(psorted))
for (i, _, j) in psorted:
    print(i + 1, -(j - 1))