Znalezienie ilości zmian liczb w sortowaniu bombelkowym

Mamy tablicę n liczb naturalnych. Zaproponuj możliwie szybki algorytm, który obliczy, ile zamian
liczb dokonałby na tym ciągu algorytm sortowania bąbelkowego (porządek niemalejący).

Chodzi mi o to aby algorytm miał jak najmniejszą złożoność.
Macie jakieś podpowiedzi?
Słyszałem coś że trzeba policzyć ilość inwersji, ale to nadal "pętla w pętli".

Wstaw sobie licznik w algorytm, Bedziesz Mial zlozonosc taka sama, jak sortowanie.

Ha, robiłem to zadanie w tym roku :) da się policzyć to w czasie O(n log n).
zadanie jest dostępne tutaj:
https://www.hackerrank.com/challenges/ctci-merge-sort/problem
a cały myk polega na tym żeby odpowiednio zmodyfikować sortowanie przez scalanie do liczenia inwersji :)

spamgolden napisał(a):

Mamy tablicę n liczb naturalnych. Zaproponuj możliwie szybki algorytm, który obliczy, ile zamian
liczb dokonałby na tym ciągu algorytm sortowania bąbelkowego (porządek niemalejący).

Chodzi mi o to aby algorytm miał jak najmniejszą złożoność.
Macie jakieś podpowiedzi?
Słyszałem coś że trzeba policzyć ilość inwersji, ale to nadal "pętla w pętli".

Chyba można to wyliczyć na podstawie analizy samej metody.

1. małe klucze z końca tablicy są tu przenoszone na początek w jednym przejściu, co daje k=i-j przestawień;
   gdzie: i, j - pozycje elementu, początkowa i finalna
2. natomiast te wielkie klucze, z początku tablicy są przesuwane tylko o 1 w każdym przejściu, co i tak w sumie daje to samo: j-i.

Zatem algorytm który to wyliczy dokładnie miałby pewnie złożoność liniową, może 2n - jak w przypadku szukania mediany.