Reje: Algoritm natiyjeliligi Tańlaw arqalı saralaw algoritmı Kóbiksimon usıldı jaqsılaw

A’piwayi saralaw algoritmleri ha’m olardin’ nalizi
REJE:

1. 
   Algoritm natiyjeliligi
   
2. 
   Tańlaw arqalı saralaw algoritmı
   
3. 
   Kóbiksimon” usıldı jaqsılaw
   
4. 
   Quiksort - tez saralaw algoritmı
   

Kóbiksimon saralaw algoritmı

Saralawdıń eki túri ámeldegi: ishki hám sırtqı :
-ishki saralaw - operativ yad daǵı 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 ma‟nosida) talap etedi. Bul sarptı kemeytiw maqsetinde, saralaw giltler adresi kesteinde ámelge asıriladı. Bunda tek ǵana ma‟lumot kórsetkishleri almastırılıp, dızbek óz jayında qaladı. Bul usıl adresler kestein saralaw usılı dep ataladı. Saralanayotganda birdey giltler dús keliwi múmkin, bul halda saralangandan keyin birdey giltlilar baslanǵısh tártipte qanday jaylasqan bolsa, sol tártipte qaldırilishi maqsetke muwapıq boladı (Birdey giltlilar ózlerine salıstırǵanda ). Bunday usılǵa turaqlı saralaw dep ataladı.
Saralaw natiyjeliligin bir neshe kriteryalar boyınsha 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ı qaray shıǵayıq. Saralaw orınlanǵanda salıstırıwlashlar yamasa almastırıwlar sanın esaplaw múmkin.
Shama menen oylayıq, N = 0, 01 n2 + 10 n - salıstırıwlashlar sanı. Eger n < 1000 bolsa, ol halda ekinshi qosılıwshı úlken, keri jaǵdayda yaǵnıy, n > 1000 bolsa, birinshi qosılıwshı úlken boladı.
Sonday eken, kishkene n larda salıstırıwlashlar sanı n ga teń boladı, úlken n larda bolsa n2 ge teń boladı.
Saralawda salıstırıwlashlar sanı tómendegi aralıqlarda boladı :

1 den n 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ıń ózleri de 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 principleriniń tiykarǵı qásiyetlerin túsindiriw qolay.
3. Quramalılastırılgan usıllarda onsha kóp ámellerdi orınlaw talap etińmasada, bul ámellerdiń ózleri de talay quramalı bolıp tabıladı. Eger jetkiliklishe úlken n larda olardan paydalanıw usınıs etilmesada, kishi n larda usı usıllar tezirek isleydi.
Sol jaydı ózinde qat‟iy usıllardı islew principlerıge kóre 3 taypaǵa bolıw 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 oyınında keń qollanıladı. Elementler (kartalar ) hayolan “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 asırıp barıladı ) baslanǵısh izbe-izlilikden i -ne element ajıratıp alınıp tayın izbe-izliktiń kerekli jayına qóyıladı.
Tuwrıdan-tuwrı qosıw arqalı saralaw algoritmı tómendegishe boladı :

for (int i=1;i

x=a[i];
x ni a[0]... a[i] aralıqtıń uyqas jayına qosıw
}
Kerekli jaydı qıdırıw procesin tómendegi tártipte aparıw qolay boladı. 2-elementten baslap hár bir elementti qaray shıǵamız, ya‟ni hár bir element ózinden aldın turǵan element menen salıstırıladı. Eger qaralayotgan element kishi bolsa, aldında turǵan element menen orın almasadı hám taǵı ózinden aldında turǵan element menen salıstırıladı, process sol sıyaqlı dawam etedi. Bul process tómendegi shártlerdiń qandayda-birı 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ǵande.
for (int i=1;i
while (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ıwlashlar sanı C, orınlashtirishlar sanı M bolsın. Eger dızbek elementleri azayıw tártibinde bolsa, ol halda salıstırıwlashlar sanı eń úlken bolıp, ol ga teń boladı, ya‟ni. Orınlashtirishlar sanı bolsa ǵa teń boladı, ya‟ni. Eger berilgen dızbek ósiw tártibinde saralanǵan bolsa, ol halda salıstırıwlashlar hám orınlashtirishlar sanı eń kishi boladı, ya‟ni,.
Tańlaw arqalı saralaw algoritmı
Usı usıl tómendegi principlerge tiykarlanǵan :
1. Eń kishi giltga iye element saylanadı.
2. Bul element birinshi element menen orın almasinadi.
3. Keyin usı process qalǵan n-1, n-2 elementler menen tákirarlanıp, tap bir eń “úlken” element qolguncha dawam ettiriledi.
for (int i=0;i
for (int j=i+1;j
if (a[i] > a[j]) {
int k = a[j];
a[j]= a[i];
a[i]= k;
}
Algoritm natiyjeliligi:
Salıstırıwlashlar sanı
S= N (N-1) /2= (N2-N) /2
Dızbek tártiplengende orınlashtirishlar sanı

Mmin=3 (N-1)

Dızbek teris tártiplengende orınlashtirishlar sanı
Mmin=MminN/2=3 N (N-1) /2
Bul usıl boyınsha saralaw atqarılsa, eń jaman halda salıstırıwlashlar hám orınlashtirishlar sanı tártibi n2 boladı.
Kóbiksimon saralaw algoritmı
Bul usıldıń ideyası tómendegishe: n - 1 ret dızbekte tómenden joqarıǵa qaray júrip giltler jupi-jupimenen salıstırıwlanadı. Eger tómengi gilt ma`nisi joqarıdaǵı jupi giltidan kishi bolsa, ol halda olardıń ornı almastırıladı (1- súwret).
Mısal : dızbek - 4, 3, 7, 2, 1, 6.
Kóbiksimon usıldı dızbek elementlerinde tómenden joqarıǵa hám joqarıdan tómenge ótiwdi bir waqıtta ámelge asırıw nátiyjesinde jaqsılaw múmkin.
Salıstırıwlashlar sanı :
M= (n/2) (n/2) =n2/4
Almastırıwlar sanı :
Cmax=3 n2/4
2-suwretde berilgen mısalda 5 elementten ibarat dızbek berilgen. Sonday eken, dızbekte tómenden joqarıǵa (joqarıdan tómenge) ótiwler sanı 5-1=4 ret boladı. Mısaldan kórinip turıptı, olda, algoritm ishki siklda 3-qádemnen baslap dızbekti “biykar” qayta isleydi, 4-qádemdi atqarmasa da boladı.
Berilgen usıllardıń abzallıǵı :
1) Eń ápiwayı algoritm ;
2) Ámelge asırıw ápiwayı ;
3) Qosımsha ózgeriwshiler shárt emes.
Kemshilikleri:
1) Úlken dızbeklerdi uzaq qayta isleydi;
2) Hár qanday jaǵdayda da ótiwler sanı kamaymaydi.
“Kóbiksimon” usıldı jaqsılaw
1) Eger dızbekte ótiwler tekǵana joqarıdan tómenge, bálki bir waqtıniń ózinde tómenden joqarıǵa da bolsa, ol halda “jeńil” elementler “joqarıǵa júzip” shıǵadı hám “salmaqli” elementler bolsa “cho'kadi”.
2) Dızbekte “biykar” ótiwdi joq etiw ushın, sırtqı siklda dızbek saralanganligini tekseriwshi belgi qoyıw kerek.
for (int i=0;i
for (int j=n-1;j>i;j--)
if (a[j] < a[j- 1]) {
int x= a[j- 1];
a[j- 1] = a[j];
a[j] = x; }
Orınlastırıw hám salıstırıwlashlar sanı : (n* log ( n )).
Quiksort - tez saralaw algoritmı
Bul algoritm “bolıp al hám iyelik qil” principiniń ayqın mısalı bolıp tabıladı. Bul algotirm rekursiv bolıp, ortasha N*log2 N ta salıstırıw nátiyjesinde saralaydı. Algoritm berilgen dızbekti saralaw ushın onı 2 danege bolıp aladı. Bolıp alıw ushın qálegen elementti tańlap odan 2 bólekke ajratıladı. Lekin orta daǵı elementti tańlap, dızbektiń teń yarımınan 2 ge ajratgan ma‟qul. Saylanǵan gilt elementke salıstırǵanda chapdagi hám ońındaǵı hár bir element salıstırıladı. Gilt elementten kishiler shepke, úlkenler ońǵa ótkeriledi (6. 3-súwret). Endi dızbektiń hár eki tárepinde tap joqarıdaǵı ámeller tákirarlanadı. Ya‟ni bul aralıqlardıń ortasındaǵı elementler gilt retinde alınadı hám t.b.
Mısal ushın suwretdegi dızbekti saralaw algoritmın kórip shıǵamız.
1. Aralıq retinde 0 den n-1 ge shekem bolǵan dızbektiń barlıq elementlerin alamız.
2. Aralıq ortasındaǵı gilt elementti tańlaymiz, ya‟ni
key= (+) /2, i=,
j=.
3. Chapdagi i-elementti key menen salıstıramız. Eger key kishi bolsa, keyingi qádemge ótemiz. Keri jaǵdayda i++ hám sol qádemdi tákirarlaymız.
4. Ońındaǵı j-element menen key salıstırıladı. Eger key úlken bolsa, keyingi qádemge ótemiz, keri jaǵdayda j-- hám sol qádemdi tákirarlaymız.
5. i- hám j-elementlerdiń ornı almastırıladı. Eger i<=j bolsa, 3-qádemge ótiledi.
Birinshi ótiwden keyin saylanǵan element óziniń jayına kelip jaylasadı.
6. Endi sol ko'rilayotgan aralıqta key giltning shep tárepinde elementler ámeldegi bolsa, olar ústinde joqarıdaǵı ámellerdi orınlaw kerek, ya‟ni kóriletuǵın aralıq 0 den key-1 ge shekem dep belgilenedi hám 2-qádemge ótiledi. Keri jaǵdayda keyingi qádemge ótiledi.
7. Endi sol ko'rilayotgan aralıqta key giltning ońında elementler ámeldegi bolsa, olar ústinde joqarıdaǵı ámellerdi orınlaw kerek, ya‟ni kóriletuǵın aralıq key+1 den n-1 ge shekem dep belgilenedi hám 2-qádemge ótiledi. Keri jaǵdayda algoritm tawsıladı.
Sol algoritmǵa mısal kórip shıǵamız.
Mısal : Studentler at-sharıfi hám tártip nomerinen ibarat kesteni quicksort algoritmı menen saralań hám neshe orınlastırıw ámelge asırılǵanın anıqlań.

Programma kodı

#include
#include
using namespace std;
struct table{
int t;
string FIO;};
int q=0;
void qs (table *a, int first, int last) {
int i = first, j = last;table x =a[ (first + last) / 2];
do {
while (a[i]. FIO < x. FIO) i++;
while (a[j]. FIO > x. FIO) j--;
if (i <= j) {
if (i < j) { swap (a[i], a[j]);q++;}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs (a, i, last);
if (first < j)
qs (a, first, j);
}
int main (int args, tırtıq *argv[])
{ int n;cout<<" n=";cin>>n;
table student[n];
for (int i=0;i
student[i]. t=i+1;
cin>>talaba[i]. FIO;
}
qs (student, 0, n-1);
for (int i=0;i
cout<
cout<<" quicksort algoritmı " < }
Programma nátiyjesi:
studentler sanın kiriting=5
5 studentler FIO sini kiritiń
Farhod
Sırlar
Sobir
Bobur
vali| 2| Sırlar|| 4| Bobur|| 1| Farhod|| 3| Sobir|| 5| vali|
Bul algoritm kesteni 3 orınlastırıwda saraladı