«amaliy matematika va informatika» kafedrasi «Algoritmlar nazariyasi» fanidan kurs ishi

O’rtacha holat tahlili. Ishni boshlang’ich massiv tеskari tartibda joylashgan eng yaxshi holatdan boshlaymiz. Elеmеntlarning bunday joylashuvi bizga avtomatik holda to’g’ri piramidani bеradi. Shuning uchun har bir Piramida protsеdurasiga murojaat vaqtida elеmеntlarning to’g’ri joylashganligini tasdiqlovchi ikkita taqqoslash amali bajariladi. Ushbu protsеdura elеmеntlarning taxminan yarmi uchun chaqirilganligidan piramida qurish mobaynida N ga yaqin taqqoslash amallari bajarilishi kеlib chiqadi. Saralangan massivga ega bo’lish uchun piramidadan barcha elеmеntlarni kеtma-kеt olib, uni har safar qaytadan shakllantirish lozim. Shuning uchun eng yaxshi holatda piramidali saralash algoritmi N Q NlogN ta taqqoslash amali bajarilib, uning murakkabligi O(NlogN) ga tеng bo’ladi. Shunday qilib, piramidali saralash algoritmining eng yaxshi holat murakkabligi bilan eng yomon holat murakkabligi mos tushadi. Bundan o’rtacha holat murakkabligining O(NlogN) ga tеng ekanligi kеlib chiqadi.

2.2 Piramidal saralashga doir masala yechish

Piramidali (top’lam) bu ikki tomonlama daraxtdir

a[i] ≤ a[2i+1];

a[i] ≤ a[2i+2].



a[0] — piramidaning minimal elementi.

Piramidal tartiblashning asl g'oyasi, umumiy arifmetik elementlardan olingan piramidaning oldindan yasalishi va elementlarning tartiblashidir. Algoritmning bajarilishi 2 etapga bo’linadi.

1 –bosqich. Piramidani qurish. n/2-1 dan boshlab, daraxting o’ng qismini aniqlab olamiz (daraxtning pastki darajasi). Massivning bu qismidan chaproqda turgan elementlarini olamiz va uni piramida bo’ylab joylashtiramiz, undan kichik elementlar kelib qolsa, ularning kichigi bo’ylab harakatlanamiz.

Masalan saralash uchun massiv 24, 31, 15, 20, 52, 6

Elementlarni dastlabki piramida ko’rinishida joylashtiramiz; o’ng qism elementining nomeri (6/2-1)=2 – bu element 15.

15 elementini piramida bo’ylab joylashtirish natijasi:




Keyingi joylashtirilayotgan element – 1, 31 ga teng



keyingi element –0, 24 ga teng.

Albatta olingan massiv hali tartiblanmagan. Lekin joylashtirish jarayoni piramidali saralash asosi hisoblanadi. Joylashtirish natijasida eng kichik element piramida uchida bo’lib qoladi.

2– bosqich qurilgan piramidada saralash. Massivning eng oxirgi elementini joriy qilamiz. Joriy elementni uchidagi element(eng kichik) bilan joylarini almashtiramiz. Joriy elementni (uchidagi) n-1 elementli piramida bo’ylab joylashtiramiz. Keyin oxirgisidan bitta oldingi elementni tanlaymiz va h.k.



jarayonni davom ettiramiz. Natijada massiv kamayish tartibida saralangan bo’ladi.





Piramidali saralashning C++ dagi dasturi

#include

#include

// To’plamni shakllantirish – to’plam bo’yicha “joylashtirish”

void siftDown(int *numbers, int root, int bottom)

{

int maxChild; // maksimal avlod indeksi

int done = 0; // to’plam shakllanganligi bayrog’i

// Toki oxirgi qatorga bormaganimizcha

while ((root * 2 <= bottom) && (!done))

{

if (root * 2 == bottom) // agar oxirgi qatorda bo’lsak,

maxChild = root * 2;

// chap avlodni eslab qolamiz

// aks holda, ulardan kattasini eslab qolamiz

else if (numbers[root * 2] > numbers[root * 2 + 1]) maxChild = root * 2;

else

maxChild = root * 2 + 1;

// agar uchidagi element maksimal avloddan kichik bo’lsa

if (numbers[root] < numbers[maxChild])

{

int temp = numbers[root]; // ularning joylarini almashtiramiz

numbers[root] = numbers[maxChild];

numbers[maxChild] = temp; root = maxChild;

}

else // aks holda

done = 1; // piramida hosil bo’ladi

}

}

// to’plamda saralash funksiyasi

void heapSort(int *numbers, int array_size)

{

// piramidaning pastki qatorini shakllantiramiz

for (int i = (array_size / 2) - 1; i >= 0; i--)

siftDown(numbers, i, array_size);

// qolgan elementlarni piramida bo’ylab joylashtiramiz

for (int i = array_size - 1; i >= 1; i--)

{

int temp = numbers[0]; numbers[0] = numbers[i]; numbers[i] = temp; siftDown(numbers, 0, i - 1);

}

}

int main()

{

int a[10];

// Massivni tasodifiy sonlar bilan to’ldiramiz

for (int i = 0; i<10; i++)

a[i] = rand() % 20 - 10;

// massivning saralashgacha bo’lgan elementlarini chiqaramiz

for (int i = 0; i<10; i++)

printf("%d ", a[i]); printf("\n");

heapSort(a, 10); // saralash funksiyasini chaqirish

// Saralashdan keying massiv elementlarini chiqarish

for (int i = 0; i<10; i++) printf("%d ", a[i]); printf("\n");

getchar(); return 0;

}

Natija:

Piramidali saralash algoritmining tahlili

Ba'zi tashqi murakkabliklarga qaramay, piramidali saralash eng samarali hisoblanadi. Saralash algoritmi katta n lar uchun samarali. Eng yomon holatda o’zgaruvchan elementlar qadamlari soni 𝑛 log₂ 𝑛.

Almashtirishlarning o’rtacha soni taxminan quyidagiga teng:
XULOSA

Axborot texnologiyasining maqsadi axborotlarni inson ularni tahlil qilishi va shu asosda biror ishni bajarish bo’yicha qaror qabul qilishi uchun ishlab chiqishdan iborat. Shunday qilib, tizim - bu o’zaro bog’liq va yagona maqsadga erishish uchun ma’lum qoida asosida o’zaro munosabatda bo’ladigan unsurlar to’plami. Bu unsurlar to’plami oddiy unsurlar yig’indisidangina iborat bo’lmay, har bir unsur ham o’z navbatida tizim bo’lishi mumkin. Tizimlar tuzilishi bo’yicha oddiy yoki murakkab bo’lishi mumkin. Oddiy tizimlarni tashkil etuvchi unsurlar soni kam bo’lib, sodda tuzilishga ega bo’ladi. Murakkab tizimlar esa, bir nechta unsurlardan tashkil topgan bo’lib bu unsurlar ham o’z navbatida alohida tizimlarga bo’linishi mumkin. Axborot texnologiyalarida Algoritmlash nazaryasini ham o’rni katta.

Hozirgi kunda Respublikamizda keng tarqalib borayotgan ish joylarini avtomatlashtirish va ish joylarida axborot kommunikatsiya vositalaridan keng foydalanishga katta e’tibor berilmoqda.

Men ushbu kurs ishini qilish davomida algoritmlashda Piramidal saralash haqida ancha o’rganib oldim. O’zimga berilgan mavzuni tushunganimcha yoritishga harakat qildim. Kurs ishini qilish davomida algoritmlashda bir qator saralash turlarini o’rgandim va buni kelajakda bilganlarimni qo’llashga harakat qilaman. Ushbu mavzuni yoritar ekanman, men algoritmlashda Piramidal saralashning o’z o’rniga ega ekanligini va qachon, qayerda ishlatilishini va afzalliklariyu kamchiliklari haqida bilib oldim.

FOYDALANILGAN ADABIYOTLAR

1. 
   O`.T.Haitmatov va b.Informatika va axborot texnologiyalari. O’quv qo’llanma. T. TKTI. 2005 y.
   
2. 
   Aripov M., Xaydarov A. Informatika asoslari T. “O`qituvchi”2002y.
   
3. 
   Holmatov T.X.,Toyloqov N.I. Amaliy matematika, dasturlash va kompyuterning dasturiy ta’minoti. T.Mexnat, 2000 y. 27-32 b.
   
4. 
   А.В. Петров и др. Вычислительная техника и программирование. Учебник для технических вузов.М.:Высш. шк.,1990.
   
5. 
   Культин Н.Б.Программированиев Турбо Паскаль и Дельфи. СПб.:БХВ-Сaнкт-Петербург,1999.
   
6. 
   Дж. Макконел. Основы современных алгоритмов. 2-е дополненное издание Москва:Техносфера, 2004.
   
7. 
   Джулиан М. Бакнелл.Фундаментальные алгоритмы и структуры данных в Дельфи..СПб.-ДиаСофтЮП,2003.
   
8. 
   Л.Г. Гагарина, В.Д. Колдаев. Алгоритмы и структуры данных. М: Финансы и статистика. ИНФРА-М.2009.
   
9. 
   Роберт Седжвик. Фундаментальные алгоритмы на C++. К.: Издательство «ДиаСофт», 2001.
   
10. 
    Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М., Наука, 1987.
    
11. 
    Кнут Д. Искусство программирования для ЭВМ. Основные алгоритмы. М., 2000.
    
12. 
    В.И.Игошин. Математическая логика и теория алгоритмов. Издательство Саратовского Университета, 1991.
    

Internet saytlari:

• 
  https://hozir.org
  
• 
  https://fayllar.org
  
• 
  http://intsys.msu.ru/stuff/vnosov/theorald.htm#top
  
• 
  http://structur.h1.ru/hash.htm
  
• 
  http://sorting2.shtml