Ma’lumotlarni saralash algoritmlari. Saralash tushunchasi va uning vazifasi Saralash algoritmi


Joylab saralashning xususiyatlari


Download 80.4 Kb.
bet4/5
Sana25.12.2022
Hajmi80.4 Kb.
#1065171
1   2   3   4   5
Bog'liq
Ma’lumotlarni saralash algoritmlari

Joylab saralashning xususiyatlari

  • Bu algoritm oddiy amalga oshirilgani uchun eng oddiy algoritmlardan biridir. Insertion sort kichik maʼlumotlarni saralash uchun samarali. Joylab saralash tabiatan moslashuvchan, yaʼni qisman saralangan maʼlumotlar toʻplamlari uchun mos keladi.
  • Insertion sort ham selection sort va buble sort kabi O(n2) vaqt murakkabligi bilan ishlasa ham, lekin ulardan koʻra samaraliroq algoritm hisoblanadi. Aynan, massiv elementlari deyarli saralangan holatda Insertion sort algoritmi merge sort yoki quick sort algoritmidan ham koʻra tezroq ishlaydi

Quick sort

  • Quicksort samarali, umumiy maqsadli saralash algoritmidir. Quicksort 1959-yilda britaniyalik kompyuter olimi Toni Xoar tomonidan ishlab chiqilgan va 1961-yilda nashr etilgan, bu hali ham tartiblash uchun keng tarqalgan algoritmdir. Umuman olganda, bu tasodifiy ma'lumotlar uchun, ayniqsa kattaroq taqsimotlarda, birlashtirish va yig'ish saralashdan biroz tezroq.
  • Quicksort - bu bo'lish va zabt etish algoritmi. U massivdan “pivot” elementini tanlash va boshqa elementlarni pivotdan kichik yoki kattaligiga qarab ikkita kichik massivga bo‘lish orqali ishlaydi. Shu sababli, uni ba'zan bo'lim-almashinuv tartibi deb ham atashadi.[4] Keyin pastki massivlar rekursiv tartibda tartiblanadi. Bu saralashni amalga oshirish uchun kichik qo'shimcha xotira hajmini talab qiladigan joyda amalga oshirilishi mumkin.
  • Tezkor saralash - bu taqqoslash tartibi, ya'ni u "kamroq" munosabati (rasmiy ravishda umumiy tartib) belgilangan har qanday turdagi elementlarni saralashi mumkin. Tezkor saralashning aksariyat ilovalari barqaror emas, ya'ni teng tartiblash elementlarining nisbiy tartibi saqlanmaydi.
  • Tezkor saralashning matematik tahlili shuni ko'rsatadiki, o'rtacha hisobda algoritm n ta elementni saralash uchun {\displaystyle O(n\log {n})}O(n\log {n}) taqqoslashlarini oladi. Eng yomon holatda, u {\displaystyle O(n^{2})}O(n^{2}) taqqoslashni amalga oshiradi.

Download 80.4 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling