|
Saralash algoritmlari ikki tipga bo’linadi
|
| bet | 3/6 | | Sana | 16.11.2023 | | Hajmi | 247,89 Kb. | | #99549 |
Bog'liq Amaliy matematika va informatika fakulteti Tabiy va aniqfanlar k-fayllar.org (1)Saralash algoritmlari ikki tipga bo’linadi.
1.O(N) vaqtda saralovchi algortimlar.
2.O(n•log(n)) vaqtda saralovchi algoritmlar.
Algoritmlarda log(n) bu.
n= bo’lganda taqqoslang:
O() =, O(n•log(n)) = 1660964.
Vaqt – bu algoritmni tezligini xarakterlovchi asosiy parametr. Bu albatta hisoblash murakkabligi bilan bog’liq.
Algoritmning uchta asosiy hulqi yani o’zini tutishi.
1.yomon
2.o’rta
3.yaxshi
Bo’lishi mumkin.
O(n log n)– baho algoritmni o’rta xulqi hisoblanadi.
O(n2) – baho algoritmni yomon xulqini aks ettiradi.
O(n)– baho algoritmni yaxshi xulqini aks ettiradi.
Algoritmlar quyidagilar bilan farq qiladi.
· Ishlash vatqi 0 ( ).
· Taqqoshlashlar soni 0 ( ).
· Almashtirishlar soni. 0(N)
· Qo’shimcha xotira. 0(1)
2.1 Saralash xossalari va ularning sinflari
Turg’unlilik (stability)
Tabiy xulqlilik– algoritm o’zini tabiy holdagidek tutadi. Agar kiritiladigan ketma-ketlikdagi bu xarakteristikani xisobga olsa va yaxshi ishlasa u tabiiy xulqli deyiladi.
Turg’un saralash algoritmlari.
1. Tanlashni saralash (Selection sort) – algoritm murakkabligi O(n2)
2. Ko’pikli saralash (Bubble sort) – algoritm murakkabligi O(n2).
3. Aralashtirish saralashi (SHeyker, Cocktail sort, bidirectional bubble sort) -
algoritm murakkabligi O(n2)
4. O’rniga qo’yish saralashi (Insertion sort) – algoritm murakkabligi O(n2)
5. Qo’shilish saralashi (Merge sort) – algoritm murakkabligi O(n logn)
6. Ikkilik daraxti yordamida saralash (Tree sort) – algoritm murakkabligi
O(n log n). Qos’himcha O(n) xotira talab etadi.
7. Timsort saralashi (Timsort) – algoritm murakkabligi O(n log n) qo’shimcha
|
| |
