Znalezienie ilości zmian liczb w sortowaniu bombelkowym

Odpowiedz Nowy wątek
2018-11-24 12:24
0

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".

Pozostało 580 znaków

2018-11-24 13:09
0

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


tylko to chodzi aby tak wymyślić aby nie było złożoności n^2. - spamgolden 2018-11-24 13:17
to wtedy nie będzie sortowanie bąbelkowe... - Spine 2018-11-24 13:19
@spamgolden: nie widze mozliwosci. - lion137 2018-11-24 13:25
Można sprawdzać, czy nie było swapów. W pesymistycznym przypadku to nic nie da (nawet spowolni), ale można dużo zaoszczędzić, jeśli np. sortowanie się wykona w 10 przebiegach, a nie 15 ;) https://pl.wikipedia.org/wiki[...]oduj%C4%85ce_ulepszenie_czasu - Spine 2018-11-24 13:45

Pozostało 580 znaków

2018-11-24 17:48
2

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 :)


#Dżunior React Devloper wanna be#
edytowany 1x, ostatnio: neves, 2018-11-24 17:55

Pozostało 580 znaków

2018-11-25 20:28
exp
0
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.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0