/ / Określ, ile razy, jeśli instrukcja zostanie wykonana [algorytm sortowania bąbelkowego] - algorytm, sortowanie

Określ, ile razy, jeśli instrukcja zostanie wykonana [algorytm sortowania bąbelkowego] - algorytm, sortowanie

1. for i=1 to n-1 do
2.    for j=1 to n-i do
3.       if a[j]>A[j+1] then
4.          Change A[j] with A[j+1]


Powiedz ile razy instrukcja w trzeciej linii ( if oświadczenie) zostanie wykonane.

Myślę, że jest to pierwszy, pierwotny algorytm sortowania bąbelkowego bez modyfikacji.
Przede wszystkim rozważę trzy przypadki: najlepsze, średnie i najgorsze.

W najlepszy sposób, jeśli instrukcja if zostanie wykonana n-1 razy. Dane w tablicy będą już segregowane. Wystarczy przejść przez tablicę i zakończyć algorytm.

W najgorsze Jeśli instrukcja if zostanie wykonana:

<a href="http://www.codecogs.com/eqnedit.php?latex=sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" target="_blank"><img src="/images/http://latex.codecogs.com/gif.latex?sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" title="sum_{i=1}^{n-1}tfrac{n(n-1)}{2}" /></a>

czasy. Dane w tablicy nie będą segregowane i każda pozycja będzie zamieniona.

W Średnia Jeśli instrukcja if zostanie wykonana:

<a href="http://www.codecogs.com/eqnedit.php?latex=sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" target="_blank"><img src="/images/http://latex.codecogs.com/gif.latex?sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" title="sum_{i=1}^{n-1}tfrac{n(n-1)}{4}" /></a>

czasy? Myślę, że ponieważ to będzie najgorszy przypadek podzielony przez 2.

Chcę poprosić cię o sprawdzenie, czy dobrze myślę. Jeśli uważasz, że się mylę, popraw mnie.

Pozdrowienia,

Odpowiedzi:

1 dla odpowiedzi № 1

Nie ma sprawdzania - jeśli tablica jest już posortowana - w kodzie, więc liczba instrukcji if jest zawsze

Q = 1 + 2 + 3 + ... + n-1  = n * (n-1) / 2

Nie to Kod Wiki czeki

   ....
until not swapped

i może wykonać (n-1) instrukcje if w najlepszym przypadku (posortowana tablica)


0 dla odpowiedzi nr 2

Instrukcja if zawsze będzie wykonywana dokładnie taką samą liczbę razy, z grubsza n ^ 2/2.

Jak często będzie wykonywane zdanie 4, jest to interesujące pytanie, szczególnie w przypadku liczby średniej matematyka byłaby interesująca.