Just a simple bubble sort question

Revision en1, by Danzev, 2020-04-10 17:14:50

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)$$$?

Tags bubble sort

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Danzev 2020-04-10 17:14:50 279 Initial revision (published)