Given an array $$$a_1,a_2,\dots,a_n$$$, $$$a_i=i$$$ and a permutation of this array $$$p_1,p_2,\dots,p_n$$$. We sort this permutation to get initial array using bubble sort.
Question: how to calculate a number of swaps in $$$O(n)$$$ instead $$$O(n^2)$$$?