Juda ham katta sonlar bilan ishlash 8 mavzu


Taroqsimon caralash (Comb sort)



Download 5,79 Mb.
bet3/7
Sana14.07.2022
Hajmi5,79 Mb.
#796574
1   2   3   4   5   6   7
Bog'liq
Ko3qDGRlNMCvobXcWi5vGmdrWoZV2FMK2EstZftB

Taroqsimon caralash (Comb sort).

  • Shaker saralashning yana bir o‘zgartirilgani. "Toshbaqalar" dan qutulish uchun masofada turgan elementlarni qayta tashkil qilamiz. Keling, uni tuzatamiz va chapdan o‘ngga boramiz, bu masofada turgan elementlarni taqqoslaymiz, agar kerak bo‘lsa, ularni qayta tartibga solaylik. Shubhasiz, bu "toshbaqalar"ni tez qator boshiga olish imkonini beradi. Dastlab qator uzunligiga teng masofani olib, so‘ngra uni taxminan 1.247 ga teng bo‘lgan biror koeffitsientga bo‘lish maqbuldir. Masofa bir biriga teng bo‘lganda shaker saralash bajariladi. Eng yaxshisi, murakkabligi O(nlogn), eng yomoni, u O(n2). O‘rtacha murakkabligi nima uchun juda aniqmas, amalda O(nlogn) kabi ko‘rinadi.
  • void combsort(int* l, int* r) {
  • int sz = r - l;
  • if (sz <= 1) return;
  • double k = 1.2473309;
  • int step = sz - 1;
  • while (step > 1) {
  • for (int* i = l; i + step < r; i++) {
  • if (*i > *(i + step))
  • swap(*i, *(i + step));
  • }
  • step /= k;
  • }
  • bool b = true;
  • while (b) {
  • b = false; for (int* i = l; i + 1 < r; i++) {
  • if (*i > *(i + 1)) {
  • swap(*i, *(i + 1));
  • b = true;}}}}

Qo‘shish orqali saralash (Insertion sort).

  • Algoritm yakunlangandan keyin javobni o‘z ichiga olgan bir yangi massiv yaratiladi. Javob massividagi elementlar har doim tartiblanib turishi uchun manba massividan elementlarni birma-bir kiritamiz. Murakkabligi o‘rtacha va eng yomon hol O(n2) va eng yaxshi O(n) bo‘ladi. Boshqa algoritmlarga nisbattan joriy qilish yaxshiroq (yangi massiv yaratish va albatta u nimanidir qo‘yish qiyin): joriy massivning ba’zi bir prefikslari tartiblashtirilganiga ishonch hosil qilish va modomiki ular noto‘g‘ri tartibda ekan uni kiritish o‘rniga joriy elementni avvalgisi bilan o‘zgartiramiz.
  • void insertionsort(int* l, int* r) {
  • for (int *i = l + 1; i < r; i++) {
  • int* j = i;
  • while (j > l && *(j - 1) > *j) {
  • swap(*(j - 1), *j);
  • j--;
  • }
  • }
  • }

Download 5,79 Mb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




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

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish