|
4- mavzu. Saralash usullari. Massiv elementlarini saralash. Reja: Saralash usullari
|
| bet | 2/7 | | Sana | 09.02.2024 | | Hajmi | 19,23 Kb. | | #153640 |
Bog'liq 4- mavzu. Saralash usullari. Massiv elementlarini saralash. Reja-fayllar.orgFaylda saralash. Fayllar sekin ishlovchi, lekin kattaroq hajmdagi tashqi xotirada saqlanadi. Agarda saralanadigan ma’lumotlar ketma-ket kirish mumkin bo’lgan tuzilmalarda saqlanayotgan bo’lsa, bunday tuzilmalarga massivda saralash algoritmlarini qo’llab bo’lmaydi. Chunki, ketma-ket kirishga ruxsat berilgan tuzilmalarda vaqtning har bir momentida faqat va faqat bitta komponentga murojaat qilish mumkin bo’ladi.
a) To’g’ridan-to’g’ri qo’yish orqali saralash algoritmi
Algorotmning asosiy g’oyasi: Massiv elementlari shartli ravishda oldindan tayyorlangan ketma-ketlik a1, a2, ..., ai-1 va kiruvchi ketma-ketlik ai, ai+1, ..., an kabi qismlarga ajratib olinadi.
Oldindan tayyor ketma-ketlikda har bir i-element qulay joyga joylashtiriladi.
Ushbu algoritmning ishlashiga C++ dasturlash tilida misol. O’nta elementdan iborat butun sonli massiv berilgan. Massiv elementlarini o’sish tartibida saralang.
Yechimi:
#include
void ttSort(int *num, int size) // saralash funksiyasi
{
for (int i = 1; i < size; i++)
{
int value = num[i]; // element qiymati va uning indeksini saqlash
int index = i;
while ((index > 0) && (num[index - 1] > value))
{
num[index] = num[index - 1];
index--;
}
num[index] = value;
}
}
int main()
{
int a[10];
for (int i = 0; i < 10; i++)
{
printf("a[%d] = ", i);
scanf("%d", &a[i]);
}
ttSort(a, 10);
for (int i = 0; i<10; i++)
printf("%d ", a[i]);
getchar(); getchar();
return 0;
}
Natija:
Algoritmning ishlash samaradorligi tahlili
Ci kalitlarni taqqoslashlar soni i-qadamda eng ko’p (i-1) marta, eng kamida 1 marta amalga oshiriladi. Agar n ta kalitning almashishi bir xil ehtimolli bo’lsa, u holda taqqoslashlar soni n2n2 ga teng bo’ladi. Sijitishlar soni .
Shuning uchun taqqoslashlar va siljitishlar soni mos ravishda quyidagicha bo’ladi:
Eng yaxshi holat dastlabki elementlarning tartiblangan holati. Eng yomon holat esa ularning teskari tartiblangan holati.
Xulosa: shunday qilib, to’g’ridan-to’g’ri qo’yish orqali saralash usuli kompyuter uchun unchalik ham ma’qul emas, chunki bir nechta elementlar guruhini birdaniga surish samarali bo’lmaydi.
|
| |
