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

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ı S_max eń kóp boladı.
S_max = (N - 1) + (N - 2) + (N - 3) + ... + 1 arifmetik progressiya aǵzaları qosındısına teń, yaǵnıy S_max = = 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ı S_min = N - 1. Salıstırıwlardıń ortasha sanı 0,25N² 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 A_i, tártipge salınǵan izbe-izlik elementlerini B_j menen belgileymiz..
Dástlepki A izbe-izliktiń birinshi elementi A_i yadtıń bos maydanında birinshi poziciyanı iyeleydi, yaǵnıy B izbe-izliktiń birinshi elementi B₁ bolıp qaladı. A₂ element B₁ menen salıstırıladı. Eger salıstırıw nátiyjesinde A₂ < B₁ bolsa, B₁ element birinshi poziciyaǵa jıljıtıladı, A₂ 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 B₁ hám B₂ elementi jaylasqan boladı.
Saralaw processiniń hár bir i-basqıshinde A_i element náwbeti menen B izbe-izliktiń B₁ elementinen baslap barlıq elementleri menen salıstırıladı. A_i den úlken bolǵan B_j anıqlanganda B_j, B_j+1, B_j+2, ... B_j-1 elementleri bir poziciyaǵa jıljıtıladı hám j-poziciyanı iyeleytuǵın A_i elementi ushın orın bosatadı.