|
Saralashalgoritmlaribajarilishtezligidaxotiranieffektivishlatilishibo„yichabah olash
|
| bet | 3/7 | | Sana | 16.05.2024 | | Hajmi | 0,7 Mb. | | #237420 |
Bog'liq Qobulov Gʼaybullo algoritmlarni loyihalashSaralashalgoritmlaribajarilishtezligidaxotiranieffektivishlatilishibo„yichabah olash.
Vaqt – bu algoritmni tezligini xarakterlovchi asosiy parametr.Bu albatta hisoblash murakkabligi bilan bog„liq.
Algoritmning uchta asosiy xulqi ya‟ni o„zini tutishi
- yomon
- o„rta
- yaxshi
bo‟lishi mumkin.
O(n log n)– bahoalgoritmnioʻrtaxulqihisoblanadi. O(n2) – baho algoritmni yomon xulqini aksettiradi. O(n)– bahoalgoritmniyaxshixulqiaksettiradi.
Bu yerda n saralanadiganelementlarsonibo„lib, uavvaldanberilganbo„lishikerak.
Xotira – ba‟zi biralgoritmlarsaralashdaqo„shimchaxotiratalabetiladi.Odatdabundayalgoritmlar O(log n) xotiranitalabetiladi. Ba‟zi birlari saralashda qo„shimcha xotira talab etmaydi. Bundayalgoritmlaro„zo„rnida (joyida) saralashdebataladi.
2
n
ak , ak
1
, ..., ak
n
f ak f ak ... f ak
1 2
Saralash jarayonida dastlabki massivning bir qismi operativ xotirada o‟qiladi.u yerda ichki saralash usillaridan biri bilan saralanadi.so‟ngra tashqi xotira qurilmasiga yozib olinadi. Bu jarayon bir necha bor takrorlanadi. Shu tariqa saralangan yozuvlar ketma-ketligi keyinchalik birlashtiriladi. Tashqi xotira qurilmasidagi tartibga solingan ma‟lumotlar ketma-ketligini birlashtirish operatsiyasi qo‟shilish deb ataladi.
Saralashxossalarivaularningsinflari
Turg„unlilik (stability)
Tabiiyxulqlilik– algoritmo„zinitabiiyholdagidektutadi. Agar kiritiladigan ketma- ketlikdagi bu xarakteristikani xisobga olsa va yaxshi ishlasa u tabiiy xulqli deyiladi.
Turg„un saralash algoritmlari.
- Tanlashni saralash (Selection sort) – algoritm murakkabligi O(n2)
- Ko„pikli saralash (Bubble sort) – algoritm murakkabligi O(n2).
- Aralashtirish saralashi (SHeyker, Cocktail sort, bidirectional bubble sort) - algoritm murakkabligi O(n2)
- O„rniga qo„yish saralashi (Insertion sort) – algoritmmurakkabligi O(n2)
- Qo„shilishsaralashi (Merge sort) – algoritmmurakkabligi O(n logn)
- Ikkilikdaraxtiyordamidasaralash (Tree sort) – algoritmmurakkabligi O(n log n) qo„shimcha O(n) xotiratalabetadi.
- Timsortsaralashi (Timsort) – algoritmmurakkabligi O(n log n) qo„shimcha O(n) xotiratalabetadi.
- Sanashorqalisaralash (Counting sort) – algoritmmurakkabligi O(n+k) qo„shimcha O(n) xotiratalabetadi.
9. Bloklisaralash (Savatlisaralash, Bucket sort) – algoritmmurakkabligi O(n) qo„shimcha O(k) xotiratalabetadi
|
| |
