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

6	6	6	6
6
3	13	13	13	9	9	9
4	11	11	11	11	11	11
5	9	9	9	13	13	12
6	4	12	12	12	12	13

Tańlaw usılı menen saralaw úlgisi tablicada kórsetilgen. Saralawda jazıwlar tek gilt maydanınan ibarat bolıa tártipge salınatuǵın izbe-izlik elementleri jazıwlar giltiniń mánisleri esaplanadı. Tablicada belgilengen sanlar hárbir basqıshta giltiniń eń kishi mánisi boyınsha tańlap alınǵan jazıwlardı bildiredi. Massiv A elementleri bes basqıshta saralanıp boldı. Usı usıldıń sıpatını bahalaymız. N elementten ibarat izbe-izlikti saralaw ushın N - 1 basqısh talap etiledi, Sebebi hár bir basqıshta tártipge salınǵan izbe-izligitiń tiyisli poziciyasına tek bir element kiritiledi. I – basqısh ushın N - i salıstırıw talap etiledi. Demak, salıstırıwlardıń ulıwma sanı

S_max = = 0,5N(N-1)
Joqarıda kórip shıǵılǵan usıl menen saralawda salıstırıwlar sanı dástlepki izbe-izliktiń tártipge salınǵanlıq dárejesine baylanıslı bolmaydı. Sonıń ushın alınǵan ańlatpa salıstırıwlardıń eń kem, ortasha hám eń kóp sanını anıqlaydi. Salıstırıwlardıń ortasha sanını bahalaw ushın ańlatpalardıń tómendegi approksimaciyasınan paydalanıw mumkin: 0,5 N². Bunday approksimaciya N = 100 bolǵanda 1 % hám N = 1000 bolǵanda 0,1 % qátelikke jol qoyıwı mumkin. Tańlaw usılı menen saralawda salıstırıwlardıń ortasha sanı 0,5N² ge jaqın dep esaplaw mumkin. Elementlerdiń ornını almastırıw shaması dástlepki izbe-izlik elementleriniń jaylasıwına baylanıslı. Basqa qálegen jaǵdayda hám bir basqısh dawamında birden artıq bolmaǵan orın almastırıw talap etiledi; demak, orın almastırıwlardıń eń kóp sanı N – 1 ge teń. Eń jaqsı jaǵdayda, yaǵnıy dástlepki izbe-izlik tártipge salınǵan bolsa, bir hám orın almastırıw talap etilmeydi. Demek, orın almastırıwlar ortasha sanı N/2 ge jaqın boladı. Almastırıw usılı (kóbikshe). Bul usıl menen saralawda tártipge salınatuǵın izbe-izlik yadtıń dástlepki izbe-izlik jaylasqan jerinde dúziledi. Saralaw processinde qońsı elementler juplap salıstırıladı. Eger salıstırılıp atırǵan elementler ortasındaǵı tártip buzılǵan bolsa, olardıń orınları almastırıladı. Bul almastırıw usılı kóbinshe kóbikshe usılı dep hám ataladı, Sebebi eń kishi elementler hár bir basqıshde tap kóbikshelerge uqsap izbe-izliktiń birinshi poziciyasi jónelisinde «qalqıp» shıǵadı. Salıstırıw algoritmi tómendegishe. Birinshi basqısh dawamında A1 hám A2 elementler salıstırıladı. Eger A2 < A1 bolsa, elementlerdiń orınları almastırıladı, Bunda A2 element birinshi poziciyanı, A1 element bolsa ekinshi poziciyanı iyeleydi. Bul process A2 hám A3 , A3 hám A4 element jupları ushın qaytalanadı hám t.b. Birinshi basqıshdan soń eń úlken element N poziciyanı iyeleydi, eń kishi element bolsa bir poziciyaǵa joqarıǵa kóteriledi(«qalqıp shıǵadı»)
Hár bir keyingi basqıshta náwbettegi eń úlken elementler tiyisli N - 1,
N - 2 hám t.b. poziciyalardı iyeleydi, nátiyjeda tártipge salınǵan massiv dúziledi.
Hár bir basqıshdan soń usı basqısh dawamında orın almastırıwlar bolǵan-bolmaǵanlıǵını tekserip kóriw mumkin. Eger orın almastırıwlar bolmaǵan bolsa, bul izbe-izlik tártipke salınǵanlıǵı hám keyingi basqıshlar talap etilmesligini bildiredi. Basqıshlar dawamında almastırıwda qatnasatuǵın sońǵı element belgilenedi. Náwbettegi basqıshda astı sızılǵan element hám barlıq ondan keyingi elementler salıstırıwda qatnaspaydı, sebebi sol poziciyadan baslap izbe-izlik tártipge salınǵan boladı.