Simply Strange Sort (Codeforces 1561A)
Tags: Implement, sortings

You have a permutation: an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of distinct integers from $$$1$$$ to $$$n$$$. The length of the permutation $$$n$$$ is odd.Consider the following algorithm of sorting the permutation in increasing order.A helper procedure of the algorithm, $$$f(i)$$$, takes a single argument $$$i$$$ ($$$1 \le i \le n-1$$$) and does the following. If $$$a_i > a_{i+1}$$$, the values of $$$a_i$$$ and $$$a_{i+1}$$$ are exchanged. Otherwise, the permutation doesn't change.The algorithm consists of iterations, numbered with consecutive integers starting with $$$1$$$. On the $$$i$$$-th iteration, the algorithm does the following:   if $$$i$$$ is odd, call $$$f(1), f(3), \ldots, f(n - 2)$$$;  if $$$i$$$ is even, call $$$f(2), f(4), \ldots, f(n - 1)$$$. It can be proven that after a finite number of iterations the permutation will be sorted in increasing order.After how many iterations will this happen for the first time?

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 999$$$; $$$n$$$ is odd) — the length of the permutation.The second line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the permutation itself. It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$999$$$.

Output: For each test case print the number of iterations after which the permutation will become sorted in increasing order for the first time.If the given permutation is already sorted, print $$$0$$$.

Note: In the first test case, the permutation will be changing as follows:   after the $$$1$$$-st iteration: $$$[2, 3, 1]$$$;  after the $$$2$$$-nd iteration: $$$[2, 1, 3]$$$;  after the $$$3$$$-rd iteration: $$$[1, 2, 3]$$$. In the second test case, the permutation will be changing as follows:   after the $$$1$$$-st iteration: $$$[4, 5, 1, 7, 2, 3, 6]$$$;  after the $$$2$$$-nd iteration: $$$[4, 1, 5, 2, 7, 3, 6]$$$;  after the $$$3$$$-rd iteration: $$$[1, 4, 2, 5, 3, 7, 6]$$$;  after the $$$4$$$-th iteration: $$$[1, 2, 4, 3, 5, 6, 7]$$$;  after the $$$5$$$-th iteration: $$$[1, 2, 3, 4, 5, 6, 7]$$$. In the third test case, the permutation is already sorted and the answer is $$$0$$$.

Sample Inputs:
3
3
3 2 1
7
4 5 7 1 3 2 6
5
1 2 3 4 5

Sample Outputs:
3
5
0

Solution (Python):
def sorting(numbers, need_numbers, size):
    total = 0
    while numbers != need_numbers:
        for i in range(total % 2, size - 1, 2):
            if numbers[i] > numbers[i + 1]:
                (numbers[i], numbers[i + 1]) = (numbers[i + 1], numbers[i])
        total += 1
    return total

def solve():
    size = int(input())
    numbers = list(map(int, input().split()))
    sorted_numbers = sorted(numbers)
    print(sorting(numbers, sorted_numbers, size))
if __name__ == '__main__':
    for test in range(int(input())):
        solve()

Solution (Python):
""""""

def slv():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    while not all((a[i] <= a[i + 1] for i in range(0, n - 1))):
        for i in range(ans % 2, n - 1, 2):
            if a[i] > a[i + 1]:
                (a[i], a[i + 1]) = (a[i + 1], a[i])
        ans += 1
    print(ans)
if __name__ == '__main__':
    t = 1
    t = int(input())
    while t > 0:
        slv()
        t -= 1

Solution (Python):
def sorted(v):
    for p in range(1, len(v)):
        if v[p - 1] > v[p]:
            return False
    return True

def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        cnt = 0
        while not sorted(a):
            for p in range(cnt % 2, n - 1, 2):
                if a[p] > a[p + 1]:
                    (a[p], a[p + 1]) = (a[p + 1], a[p])
            cnt += 1
        print(cnt)
if __name__ == '__main__':
    main()