CODEWITHSUNDEEP
arraysalgorithmsorting
Meekso
Meekso

Reputation: 75

An array with O(n) inversions

Trying to figure out what type of an array consists of at most n inversions with n being the array size. I was thinking an array that is nearly sorted would fall under this case and also an array that is almost completely sorted with the max element and min element switched, for instance..

9 2 3 4 5 6 7 8 1

So my thinking is that when an array has at most n inversions, is it safe to say that the array is nearly sorted? Or are there other cases where the array would have at most n inversions and not be nearly sorted.

Upvotes: 3

Views: 710

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55619

The 'least' sorted array (i.e. reverse sorted) has 1 + 2 + 3 + ... + n-1 = n(n-1)/2 inversions.

The less inversions an array has, the 'more' sorted it is.

And, since n is quite a bit smaller than n(n-1)/2, one can probably call an array with n inversions 'nearly sorted'.

This array has n-1 inversions:

9 1 2 3 4 5 6 7 8

In response to your comment, insertion sort's complexity is O(n + d), where d is the number of inversions, thus it will run in O(n) for O(n) inversions.

Upvotes: 4

Related Questions