|
Kirish Saralash haqida maʻlumot va ularning qoʻllanishini. Asosiy qism
|
| bet | 4/7 | | Sana | 16.05.2024 | | Hajmi | 0,7 Mb. | | #237420 |
Bog'liq Qobulov Gʼaybullo algoritmlarni loyihalashTurg„unmas saralash algoritmlari.
- Tanlash orqali saralash(Selection sort) algoritmmurakkabligiO(n2)
- Shell saralash (Shell sort) algoritm murakkabligi O(n log2n).
- Tarash orqali saralash (Comb sort) algoritm murakkabligi O(nlogn)
- Suzuvchi saralash (Smooth sort) algoritm murakkabligi O(n logn)
- Tez saralash (Quick sort) algoritm murakkabligi O(nlogn)
- Intro sort – algoritm murakkabligi O(nlogn)
- Patience sorting – algoritm murakkabligi O(nlogn)
- Stooge sort – algoritm murakkabligi O(n2.71)
- Razryadli saralash. Algoritm murakkabligi O(n+k). O(k)qo„shimcha xotira talab etiladi.
Amaliy bo„lmagan saralash
- Bogosort – algoritmmurakkabligi O(n n!).
- O„rinlashtirishsaralash – algoritmmurakkabligi O(n n!).
O(sqrt(n)).
- Ma‟nosizsaralash (Stupid sort) – algoritmmurakkabligi O(n3).
- Bead asort – Algoritmmurakkabligi O(n) yoki Maxsusapparatta‟minotitalabetiladi.
5. Quymoqli saralash (Pancake sorting) – Algoritm murakkabligi O(n).Maxsus apparat ta‟minoti talab etiladi.
Ko‟rib turubsiz saralash algaritimlari juda ko‟p turlari mavjud. Shulardan ba‟zi birlari birlari bilan tanishib chi qamiz.
Algoritmlar: - Oddiy va tushunarli, lekin katta massivlar uchun, samarali emas
- Pufakchausuli
- Tanlashusuli
- Algarirm murakkabligiO(N2)
- Qiyin, lekinsamaraliusullar
- «tezsaralash» (Quick Sort)
- «to„p-to„p» saralash (Heap Sort)
- Qo„shilibsaralash
- Piramidalisaralash
- Algarirm murakkabligi O(N*logN)
- PUFAKCHA USUL(Bubble sort)
- G„oya– stakandagi suvning pufakchalari kun bo„yi tepaga ko„tariladi.
- Massiv uchun– eng kichik («engil») element tepada joylashadi («suv yuziga ko„tariladi»).
- Pastdan boshlab ikkita qo„shni elementni solishtiramiz; agarda ular
- «noto„g„ri» turgan bo„lsa, ularni o„rnini almashtiramiz
- Birinchi o„tishda bitta element (eng kichik) o„z joyiga o„tadi
- N ta elementli massivnisaralashuchun N-1 o„tishni bajarish lozim (N-1 elementnio„z joyiga qo„yish uchun etarli).
Xar bir o‟tishdan so‟ng ushbu o‟tish davomida joy almashtirishlar bo‟lgan- bo‟lmaganligini tekshirib qo‟yish mumkin.
Masalan: 5; 2; 1; 3. sonlari uchun 3 ta o‟tish bajariladi. 1- o‟tish 2-o‟tish 3-o‟tish
5
|
5
|
5
|
1
|
2
|
2
|
1
|
5
|
1
|
1
|
2
|
2
|
3
|
3
|
3
|
3
|
Xar ikkita juftlik solishtiriladi.
A[N-1] ва A[N],
A[N-2] ва A[N-1]
…
A[2] ва A[1]
Bu solishtirishlarda qaysi massivning elementi kichik bo‟lsa o‟sha element bilan joyini almashtiradi.buning uchun bizga almashtiradigan qiymat kerak. Masalan ikkita stakandagi ikki xil suyuqlik bor ularning o‟rnini almashtirish uchun bizga allbatta bitta bo‟sh stakan kerak bo‟ladi. Shuning uchun biz yangi bir c degan o‟zgaruvchi tanlab olamiz.
|
| |
