Назарий саволлар

1.11 Saralaw usillari va olardi amelge asiriw

Сараланып атырғанда бир қыйлы гилтлер ушыраўы мүмкин, бул жағдайда сараланағаннан кейин бир қыйлы гилтлилер баслағыш тәртипте қандай жайласқан болса, усы тәртипте қалдырылыўы мақсетке муўапық болады (Бир қыйлы гилтлилер өзлерине салыстырғанда). Бундай усылға турақлы саралаў делинеди.

Саралаў эффективлигин бир неше дереклер бойынша баҳалаў мүмкин:

• 
  саралаўға кеткен ўақыт;
  
• 
  саралаў ушын талап қылынған оператив яд;
  
• 
  программаны ислеп шығыўға кеткен ўақыт.
  

Биринши деректи қарап шығайық. Саралаў орынланғанда салыстырыўлар яки алмастырыўлар саны есаплаў мүмкин.

Ойлайық, Н = 0,01n² + 10n – салыстырыўлар саны. Егер n < 1000 болса, ол жағдайда екинши қосылыўшы үлкен, кери жағдайда яғный, n > 1000 болса, биринши қосылыўшы үлкен болады.

Демек, кишкене n лерде салыстырыўлар саны n ге тең болады, үлкен n ларда болса n² қа тең болады.

Саралаўда салыстырыўлар саны төмендеги аралықларда болады:

0(n log n) дан 0 (n²) гача; 0 (n) – идеал жағдайда.

Саралаўдың төмендегише усыллары бар:

• 
  қатаң (туўрыдан-туўры) усыллар;
  
• 
  жақсылаған усыллар.
  

Қатаң усыллар:

1. туўрыдан-туўры қосыў усылы;

2. туўрыдан-туўры таңлаў усылы;

3. туўрыдан-туўры алмастырыў усылы.

Жоқарыда келтирилген үш усылда да алмастырыўлар саны дерлик бир қыйлы болады.