3-tema. Tańlaw hám jaylastırıw gruppaındaǵı quramalılıqǵa iye saralaw algoritmları Reje


Download 36.18 Kb.
bet4/5
Sana04.02.2023
Hajmi36.18 Kb.
#1159367
1   2   3   4   5
Bog'liq
3-tema. Tańlaw hám jaylastırıw gruppaındaǵı quramalılıqǵa iye saralaw algoritmları

2-mısal(Example). Berilgen massiv A={12,6,13,11,9,4} ti almastırıw usılında(kóbikshe) saralań.
Sheshiliwi(Decision). Nátiyje tablicada 5-basqishta kórsetilgen.

i

A(i)



1-basqish



2-basqish



3-basqish



4-basqish



5-basqish



1

12

6

6

6

6

4

2

6

12

11

9

4

6

3

13

11

9

4

9

9

4

11

9

4

11

11

11

5

9

4

12

12

12

12

6

4

13

13

13

13

13



Bul usıl ushın salıstırıwlar sanı saralaw ushın zárúr bolatuǵın basqıshlar sanına baylanıslı. Eń jaman jaǵdayda, yaǵnıy izbe-izlik keri tártipte bolsa, hár bir i-basqıshda almastırıwlar orınlanadı, basqıshlar sanı bolsa N – 1 ge teń. Bunda saralaw ushın almastırıwlar sanı Smax eń kóp boladı.
Smax = (N - 1) + (N - 2) + (N - 3) + ... + 1 arifmetik progressiya aǵzaları qosındısına teń, yaǵnıy Smax = = 0,5N(N-1).
Eń jaqsı jaǵdayda, dástlepki izbe-izlik tártipge salınǵanda bar-joǵı bir basqıshda hám N - 1 salıstırıw talap etiledi. Salıstırıwlardıń eń kem sanı Smin = N - 1. Salıstırıwlardıń ortasha sanı 0,25N2 ge teń.
Kóbikshe usılında saralawda almastırıwlar sanı dástlepki izbe-izliktiń tártipge salınǵanlıq dárejesine baylanıslı boladı. Eger dástlepki izbe-izlik tolıq tártipge salınǵan bolsa, almastırıwlar joq. Dástlepki izbe-izlik keri tártipte salınǵan bolsa, yaǵnıy giltiniń mánisi kemeyip barıw tártipte jaylasqan jazıwlardı giltiniń mánisi artıp barıw tártibinde saralaw zárúr bolǵanda, almastırıwlar sanı eń kóp boladı. Bul jaǵdayda almastırıw hár bir salıstırıwda boladı hám ulıwma almastırıwlar sanı 0,5N(N - 1) ge teń boladı. Ortasha almastırıwlar sanı 0,25N² ǵa jaqın.
Qoyu usılı. Saralawdıń bul usılınan paydalanıwda tártipge salınǵan izbe-izlik yadtıń bos maydanlarında jaratıladı. Saralaw ushın saralanǵan jazıwlar massivleri uzınlıǵına teń yad kólemi ajıratıladı. Dástlepki hám tártipge salınǵan izbe-izlik yadtıń turli maydanlarında jaylasqanlıǵı sebepli olardı belgilew ushın turli belgilerden paydalanamız. Dástlepki izbe-izlik elementlerini Ai, tártipge salınǵan izbe-izlik elementlerini Bj menen belgileymiz..
Dástlepki A izbe-izliktiń birinshi elementi Ai yadtıń bos maydanında birinshi poziciyanı iyeleydi, yaǵnıy B izbe-izliktiń birinshi elementi B1 bolıp qaladı. A2 element B1 menen salıstırıladı. Eger salıstırıw nátiyjesinde A2 < B1 bolsa, B1 element birinshi poziciyaǵa jıljıtıladı, A2 element onıń aldınǵı ornını iyeleydi. Endi yadtıń bos maydanında giltiniń mánisi artıp baratuǵın tártipte jaylasqan izbe-izlikti payda etetuǵın eki B1 hám B2 elementi jaylasqan boladı.
Saralaw processiniń hár bir i-basqıshinde Ai element náwbeti menen B izbe-izliktiń B1 elementinen baslap barlıq elementleri menen salıstırıladı. Ai den úlken bolǵan Bj anıqlanganda Bj, Bj+1, Bj+2, ... Bj-1 elementleri bir poziciyaǵa jıljıtıladı hám j-poziciyanı iyeleytuǵın Ai elementi ushın orın bosatadı.

Download 36.18 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling