Prosim za HITRO POMOČ pri algoritmu

2 naročnika

Imam spodnji algoritem (insertion sort)

A=(array številk)

for j = 2:n
---key = A(j)
---i = j - 1
---while i > 0 and A(i) > key
-------A(i+1) = A (i)
-------i = i - 1
---A (i+1) = key

Vprašanje je, koliko številskih primerjav se v postopku izvede (za podan niz ampak to ni pomembno)? Definicija številskega primerjanja: je vsak izraz oblike x>y,x=y,y<y za neka števila x,y. Zdaj me pa zanima ali štejem le primerjanja za for (j=2:n) ter pri (while i > 0 and A(i) > key) ali štejem tudi key = A(j), i = j - 1 itd. A se to tudi šteje pod številsko primerjanje? Ma meni to pomeni, da zapišemo v spremenljivko vrednost, ne pa da jo primerjamo ali se motim?

(časa za oddajo imam le še 2h zato prosim, da mi čimprej svetujete)

Tako kot se mi je zdlo, niso to primerjave ampak ziher je ziher, zato sem raje vprašal.

Tisto drugo se kličejo prirejanja. Tudi število teh (in drugih) operacij je "približno" toliko kot primerjanj (znotraj konstantnega faktorja).

V splošnem je število primerjav enako številu inverzij, če gledaš na A=(a1,...,an) kot na permutacijo (ki je podana implicitno). (To je res, če so v A sama različna števila; velja pa podoben razmislek, če se števila ponavljajo.) Če ima A n elementov in če so "narobe" urejeni, potem je vsak par elementov v inverziji, kar pokaže, da lahko insertion sort naredi n*(n-1)/2 primerjav (po domače, da ima kvadratno časovno zahtevnost).