Official Analysis (C++)

Explanation

For any $i$, the value $i - a_i$ represents a lower bound on the total number of bubble passes required to sort the array. If $i - a_i$ is positive, it indicates that the element needs to move left by at least that amount. If it is negative, it is still a valid lower bound since the element does not need to move further left.

To understand why max($i - a_i$) is correct, consider any element $a_i$ where $i - a_i$ is positive (meaning it is to the right of its correct position). For this to happen, there must be some larger element to the left of $a_i$. Due to how bubble sort works, $a_i$ will necessarily move left in every pass until it reaches its correct position, and its $i - a_i$ value decreases by $1$ with each pass.

Now consider an element $a_i$ where $i - a_i$ equals $0$ (the element is already in its correct position). Such an element may or may not move left, but it will not move right. For it to move right, the element immediately to its right would need to be smaller, which implies there is a larger element to its left, causing $a_i$ to move left instead. Thus, $i - a_i$ equals $0$ remains unchanged or decreases.

As a result, max($i - a_i$), if positive, decreases by $1$ during each bubble sort iteration. After counting the number of iterations needed to sort the array, we add $1$ to account for the final iteration performed by the algorithm, as indicated in the pseudocode.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

struct Entry {

Copy
import java.io.*;
import java.util.*;

public class Sort {
 	Code Snippet: Array Element Class (Click to expand)

	public static void main(String[] args) throws Exception {
		Kattio io = new Kattio("sort");
		int n = io.nextInt();
		Entry[] entries = new Entry[n];

Copy
from typing import NamedTuple
from functools import cmp_to_key


class Entry(NamedTuple):
	val: int
	index: int


with open("sort.in") as read: