Qo’yilgan masala

Танлаш орқали саралаш

Мазкур усул қуйидаги тамойилларга асосланган:

1. Энг кичик калитга эга элемент танланади.

2. Ушбу элемент биринчи элемент билан ўрин алмашинади.

3. Кейин мазкур жараён қолган n-1, n-2 элементлар билан такрорланиб, то битта энг “катта” элемент қолгунча давом эттирилади.

for i := 1 to n - 1 do

begin

x := a[i];

k := i;

for j := i + 1 to n do

if a[j] < x then

begin

k := j;

x := a[k];

end;

a[k] := a[i];

a[i] := x;

end;
Алгоритм самарадорлиги:

• 
  Таққослашлар сони
  

• 
  Массив тартибланганда ўринлаштиришлар сони
  

• 
  Массив тескари тартибланганда ўринлаштиришлар сони
  

Ушбу усул бўйича саралаш бажарилса, энг ёмон холда таққослашлар ва ўринлаштиришлар сони тартиби n² бўлади.

Пуфаксимон саралаш

Ушбу усулни ғояси қуйидагича: n - 1 марта массивда қуйидан юқорига қараб юриб калитлар жуфти-жуфти билан таққосланади. Агар пастки калит қиймати юқоридаги жуфти калитидан кичик бўлса, у ҳолда улар ўрни алмаштирилади.

Мисол : массив - 4, 3, 7, 2, 1, 6.

Пуфаксимон усулни массив элементларида пастдан-тепага ва тепадан-пастга ўтишни бир вақтда амалга ошириш натижасида яхшилаш мумкин.

Таққослашлар сони:

Алмаштиришлар сони:

“Пуфаксимон” саралаш усулини ҳисоблашга мисол

Берилган мисолда 5 та элементдан иборат массив берилган. Демак, массивда пастдан юқорига (юқоридан пастга) ўтишлар сони 5-1=4 марта бўлади. Мисолдан кўриниб турибдики, алгоритм ички циклда 3 қадамдан бошлаб массивни “бекор” қайта ишлайди, 4-қадамни бажармаса ҳам бўлади.

Берилган усуллнинг афзаллиги:

1) Энг содда алгоритм;

2) амалга ошириш содда;

3) қўшимча ўзгарувчилар шарт эмас.

Камчиликлари:

1) Катта массивларни узоқ қайта ишлайди;

2) Ҳар қандай ҳолатда ҳам ўтишлар сони камаймайди

Quiksort – тез саралаш усули

Ғояси: Мазкур усулнинг асосини калитларни танланган калитга нисбатан ажратиш ташкил қилади.

Мисол:

Биринчи ўтишдан кейин танланган элемент ўзининг жойига келиб жойлашади.
“пуфаксимон” усулни яхшилаш.

1) Агар массивда ўтишлар нафақат юқоридан пастга, балки бир вақтнинг ўзида пастдан юқорига ҳам бўлса, у ҳолда “енгил” элементлар “юқорига сузиб” чиқади ва “оғир” элементлар эса “чўкади”.

2. 
   Массивда “бекор” ўтишни йўқ қилиш учун, ташқи циклда массив сараланганлигини текширувчи белги қўйиш лозим.
   

4. Алгоритм

for i := 2 to n do

for j := n downto i do

if a[j] < a[j - 1]then

begin

x := a[j - 1];

a[j - 1] := a[j];

a[j] := x;

end;

end;

end;

Ўринлаштириш ва таққослашлар сони: (n* log( n )).

5. Топшириқ

Таъмирлаш устахонасида бир нечта (N та) машина бор. Улар тўғрисида қуйидаги маълумотларга эгамиз: рақами, маркаси, эгасини исми, охирги марта таъмирланганлиги санаси (куни, ойи, йили), таъмирдан чиқиши лозим бўлган сана (кун, ой, йил).

Тўғридан-тўғри қўшиш усулидан фойдаланиб, саралашни амалга ошириш дастурини ишлаб чиқиш (вариантга мос равишда)::

1. 
   Машина эгаларини исмлари бўйича алифбо тартибида жойлаштирилсин ва мос равишда уларнинг машиналари ҳақидаги маълумотлар чиқарилсин.
   
2. 
   Автомобилларни таъмирланиш тартиби ишлаб чиқилсин. Бу ерда таъмир тугаши санаси қайси автомобил учун эртароқ бўлса шунга биринчи навабатда хизмат кўрсатилади.
   
3. 
   "Жигули" маркасидаги машиналарни олдинги таъмир санаси бўйича камайиш тартибида жойлаштирилсин.
   
4. 
   Олдинги таъмир қилинганлар сони 2 га тенг бўлган машиналар рақамлари бўйича камайиш тартибида жойлаштирилсин.
   
5. 
   Олдин таъмир қилинмаган машиналарни таъмирдан чиқиш санаси бўйича ўсиш тартибида жойлаштиринг.
   
6. 
   "Мерседес" маркали машина эгаларини алифбо бўйича тескари тартибда жойлаштиринг.
   
7. 
   Бошқаларидан олдинроқ таъмирланадиган машиналарни уларни маркаси бўйича алифбо тартибида жойлаштиринг (таъмир тугатилиши санаси 31.12.2007 дан эрта).
   
8. 
   "Жигули" маркасидаги машиналарни рақамлари бўйича ўсиш тартибида жойлаштиринг.
   
9. 
   Ўтган йилдан бери таъмирланмаган машиналарни уларнинг эгалари исмлари бўйича алифбо тартибида жойлаштиринг.
   
10. 
    Кейинги ойда таъмирланиши лозим бўлган машиналарни охирги марта таъмирланганлик санаси бўйича ўсиш тартибида келтиринг.
    
11. 
    Олдинги таъмир қилинганлар сони 3 мартадан кўп бўлган машиналарни эгалари исмларини алифбо бўйича тескари тартибда жойлаштиринг.
    
12. 
    "Мерседес" маркасидаги машиналарни рақамлари бўйича камайиш тартибида жойлаштиринг.
    

N та талабадан иборат гуруҳ тузилсин. Қуйидаги маълумотлар берилган: фамилия, исм, туғилган йили, фанлар бўйича баҳоси: МСваА, олий математика, физика, дастурлаш, топширган сессия умумий бали.

Тўғри танлов усулидан фойдаланиб, саралашни амалга ошириш дастурини ишлаб чиқиш (вариантга мос равишда):

13. 
    Талабалар фамилияларини алифбо тартибида.
    
14. 
    Талабалар фамилияларини алифбо бўйича тескари тартибда.
    
15. 
    Талабаларни ёши бўйича ўсиш тартибда.
    
16. 
    Талабаларни ёши бўйича камайиш тартибда.
    
17. 
    Талабаларни умумий бали бўйича ўсиш тартибда.
    

1. Топшириқ

1. 
   Контейнерлар рўйхати. Рўйхат операциялари.
   
2. 
   Боғланган рўйхатлар. Биргаликда боғланган рўйхат билан ишлаш
   
3. 
   Богланган рўйхатлар. Иккала боғланган рўйхат билан ишлаш
   
4. 
   Контейнер стеки. Стекнинг асосий операциялари
   
5. 
   Стекнинг тузилиши. Массив ва рўйхатлар билан бажариш стек
   
6. 
   Навбатсиз идиш. Навбатдаги асосий операциялар
   
7. 
   Таркибнинг тузилиши. Бир қатор ва рўйхатлар ёрдамида навбатни амалга ошириш
   
8. 
   Тузилма дек. Дек билан асосий амаллар
   
9. 
   Иккилик дарахтларни ташкил қилиш .Иккилик дарахтнинг операциялари
   
10. 
    Иккилик қидириш дарахти. Дарахт балантлиги ва визуализатсияси
    
11. 
    Мувозанатли иккилик дарахтлар. Мувозанатлаш операциялари
    
12. 
    График тушунчаси, Қисқа йўлни қидириш алгаритмлари
    
13. 
    График тушунчаси. Тақдимот усуллари ва ечимлари.
    
14. 
    Синов турларини ўрганиш, Синовни режалаштириш.
    
15. 
    Бирлаштирилган ёки интегратсиялашган синов учун. маълумотларнинг тўпламлари Синов тўпламларни яратиш.
    
16. 
    Маълумотни намойиш қилиш моделларини ўрганиш. UML моделлаштириш тили билан ишлаш.
    
17. 
    Маълумотни намойиш қилиш моделларини ўрганиш.UML моделлаштириш тили билан ишлаш.