Maqseti: Maǵlıwmatlardiń sazlanǵan hám payda qılı’natuǵIn túrlerin úyrenıw hám olardı ızertlew. Qoyılǵan másele

Saralawdıń eki túri ámelde: ishki hám sırtqı:
- ishki saralaw;
- operativ yaddaǵı saralaw;
- sırtqı saralaw sırtqı yadta saralaw.
Eger saralanıp atırǵan jazıwlar yadta úlken kólemdi iyelese, ol halda olardı almastırıwlar úlken sarp etiw (waqıt hám yad mánisinde) talap etedi. Usı sarptı kemeytiw maqsetinde, saralaw giltler adresi kestesinde ámelge asırıladı. Bunda tek ǵana maǵlıwmat korsatkishleri almastırılıp, dızbek az jayında qaladı. Bul usıl adresler kestesin saralaw usılı dep ataladı. Saralanıp atırģanda birdey giltler dús keliwi múmkin, bul halda saralanģannan keyin birdey giltliler baslanǵısh tártipte qanday jaylasqan bolsa, sol tártipte qaldırılıwı maqsetke muwapıq boladı (Birdey giltler azlarına salıstırǵanda). Bunday usılǵa turģın saralaw dep ataladı.
Saralaw natiyjeliligin bir neshe kriteryalar boyinsha bahalaw múmkin:
- saralawǵa ketken waqıt;
-saralaw ushın talap etilgen operativ yad;
- programmanı islep shıǵıwǵa ketken waqıt.

Birinshi kriteryanı qarap shıǵayıq. Saralaw orınlanǵanda salıstırıwlashlar yamasa almastırıwlar sanın esaplaw múmkin.

Oylap qarayıq, N = 0, 01n2 + 10n salıstırıwlashlar sanı.
Eger n < 1000 bolsa, ol jaģdayda ekinshi qosılıwshı úlken, bolmasa yaǵnıy, n > 1000 bolsa, birinshi qosılıwshı úlken boladi.
Demek, kishkene n larda salıstırıwlashılar sanı n ģa teń boladı, úlken n larda bolsa n2 ge teń boladı.
Saralawda salıstırıwlashılar sanı tómendegi aralıqlarda boladı:
…den ge shekem; ideal jaǵdayda.
Saralawdıń tómendegishe usılları bar:
- qatań (tuwrıdan-tuwrı) usıllar;
- jaqsılanǵan usıllar.
Qatań usıllardıń abzallıqların kórip shıǵayıq:
1. Bilgenimizdey, programmalardıń azları da yadta jay iyeleydi. Tuwrıdan-tuwrı saralaw usıllarınıń programmaları qısqa bolıp, olar túsiniwge ańsat.
2. Tuwrıdan-tuwrı saralaw usılları arqalı saralaw printsplarınıń tiykarǵı qásiyetlerin túsindiriw qolay.
3. Quramalılastırılgan usıllarda onsha kop ámellerdi orınlaw talap etilmesede, usı ámellerdiń azları da talay quramalı bolıp tabıladı. Eger jetkiliklishe úlken n larda olardan paydalanıw usınıs etilmesede, kishi n larda usı usıllar tezirek isleydi. Sol orınnıń ózinde qatań usıllardı islew printsplarına kóre 3 dane kategoriyaǵa dastıq múmkin:
1.Tuwrıdan-tuwrı qosıw usılı (by insertion);
2. Tuwrıdan-tuwrı tańlaw usılı (by selection);
3. Tuwrıdan-tuwrı almastırıw usılı (by exchange).
Tuwrıdan-tuwrı qosıw usılı menen saralaw algoritmı bunday usıl karta házirde keń qollanıladı. Elementler (kartalar) oyda tayın a (1),.. ., a (i-1) hám baslanǵısh izbe-izliklerge bólinedi. Hár bir qádemde (i=2 den baslanıp, hár bir qádemde bir birlikke arttırıp barıladı) baslanǵısh izbe-izlikden i-shi element ajıratıp alınıp tayın izbe-izliginiń kerekli orayına qoyıladı. Tuwrıdan-tuwrı qosıw arqalı saralaw algoritmi tómendegishe boladi:
for (int i=1;i
x=a[i];
x ni a[0]...a[i] aralıqdıń uyqas jayına qosıw
}
Kerekli orındı izlew procesin tómendegi tártipte aparıw qolaylı boladi. 2-elementten baslap hár bir elementti qarap shıǵamız, yaǵnıy hár bir element ózinen aldın turǵan element menen salıstırıladı. Eger qaralıp atırģan element kishi bolsa, aldında turǵan element penen orın almasadı hám taǵı ozinen aldında turǵan element penen salıstırıladı, process sol sıyaqlı dawam etedi. Bul process tómendegi shártlerdiń qandayda-biri orınlanǵanda toqtatıladı: 1. x elementi aldında onıń giltidan kishi giltli a (j) elementi shıqqanda.2. x elementi aldında element qalmaǵanda.
1. x elementi aldında onıń giltidan kishi giltli a (j) elementi shıqqanda.
2. x elementi aldında element qalmaǵanda.
for (int i=1;iwhile(a[j]int t=a[j-1];
a[j-1]=a[j];
a[j]=t;
j=j-1;
}
}
Algoritm natiyjeliligi shama menen oylayıq, salıstırıwlar sanı C, ornalastırıwshılar sanı M bolsın. Eger dizbek elementleri azayıw rejiminde bolsa, ol halda salıstırıwlar sanı eń úlken bolıp, soģan teń boladı. Ornalastırıwlar sanı bolsa soģan teń boladı. Eger berilgen dızbek osiw rejiminde saralanǵan bolsa, ol halda salıstırıwlar hám ornalastırıwshılar sanı eń kishi boladı.