Muhammad Al-Xorazmiy nomida Toshkent
Axborot texnologiyalari universiteti
Amaliy ish-3
Mavzu:
MA’LUMOTLARNI SARALASH USULLARINI TADQIQ
QILISH
Bajardi:
Abduvahobova Odina
3-tajriba ishi. MA’LUMOTLARNI SARALASH USULLARINI TADQIQ QILISH
Ta’mirlash ustaxonasida bir nechta (N ta) mashina bor. Ular to‘g‘risida quyidagi
ma’lumotlarga egamiz: raqami, markasi, egasining ismi, oxirgi marta ta’mirlanganligi
sanasi (kuni, oyi, yili), ta’mirdan chiqishi lozim bo‘lgan sana (kun, oy, yil).
To‘g‘ridan-to‘g‘ri qo‘shish usulidan foydalanib, saralashni amalga oshirish dasturini
ishlab chiqish (variantga mos ravishda):
2.Avtomobillarni ta’mirlash tartibi ishlab chiqilsin. Bu yerda ta’mir tugashi sanasi qaysi
avtomobil uchun ertaroq bo‘lsa, shunga birinchi navbatda xizmat ko‘rsatiladi.
Dastur kodi
#include
#include
#include
using namespace std;
struct Car {
int number;
string brand;
string ownerName;
string lastRepairDate; //
Oxirgi ta'mirlangan sanasi (kuni, oyi, yili)
string nextRepairDate; //
Ta'mirdan chiqishi lozim bo'lgan sanasi (kuni, oyi, yili)
};
//
Ta'mir tugashi sanasiga ko'ra avtomobillarni tartiblash funksiyasi
bool sortByNextRepairDate(const Car &car1, const Car &car2) {
return car1.nextRepairDate < car2.nextRepairDate;
}
int main() {
vector cars = {
{1, "Toyota", "John", "12/05/2022", "20/04/2023"},
{2, "Honda", "Alice", "20/07/2022", "15/03/2023"},
{3, "Ford", "Mike", "05/06/2022", "18/03/2023"},
//
... qolgan avtomobillar ma'lumotlari
};
//
Ta'mirlash tugashi sanasi bo'yicha avtomobillarni tartiblash
sort(cars.begin(), cars.end(), sortByNextRepairDate);
//
Ta'mirlash tartibini chiqarish
cout << "Ta'mirlash tartibi:" << endl;
for (const auto &car : cars) {
cout << "Raqami: " << car.number << ", Markasi: " << car.brand << ", Ta'mir
tugashi sanasi: " << car.nextRepairDate << endl;
}
//
Avtomobilni birinchi navbatda ta'mirlash lozimiyatini aniqlash
cout << "Birinchi navbatda xizmat ko'rsatilishi kerak avtomobil: " <<
cars[0].brand << endl;
return 0;
}
Umuman olganda saralashning maqsadi berilgan Ob’yektlar to‘plamini aniq
bir tartibda guruhlab chiqish jarayoni ta’riflanadi. Saralashning maqsadi
keyinchalik, saralangan to‘plamning qidirilayotgan elementini topishdan iborat.
Bu
qariyb universal, fundamental jarayon. Biz bu jarayon bilan har kuni uchrashamiz
– telefon daftaridagi saralash, kitoblar sarlavhasida, kutubxonalarda, lug‘atlarda,
pochtada va hokazo [6].
Xatto yosh bolalar ham o‘z narsalarini tartiblashga o‘rganadi.
Saralashning juda ko‘p usullari mavjud. Ular turli to‘plamlar uchun turlicha
bo‘lishi mumkin.
a1, a2, a3,……….., an
elementlar berilgan bo‘lsin, u holda massivni saralash deganda, uni elementlarini
o‘rinlariga almashtirish tushuniladi.
ak1,ak2,ak3,………….,ak
bu yerda, quyidagi tartiblashtirilgan funksiya bajariladi.
f(ak1)≤ f(ak2)≤ f(ak3)≤…. f(akn)
Massivlarni saralash. Massivni saralash uchun ishlatiladigan usul unga
berilgan xotirani ixcham holda ishlatishdir. Boshqacha qilib aytganda,
saralanayotgan massiv xuddi shu massivni o‘zida amalga oshirilishi lozim.
Saralanayotgan a massiv elementlarini kiritib, uni boshqa bir d massivda
saralangan holda saqlanishi bizda hech qanday qiziqish uyg‘otmaydi.
Saralash usullari kam mashina vaqtini talab qilishi lozim. Eng yaxshi tez
algoritmlar n*log n tartibidagi saralashlarni talab etadi.
Biz saralash bo‘yicha bir nechta sodda va ma’lum usullarni ko‘rib chiqamiz.
Ular to‘g‘ri usullar deb aytiladi.
Saralash usullari to‘g‘risida quyidagi fikrlarni bildirish mumkin:
1. To‘g‘ri usullar ko‘plab saralashning asosiy tamoyillarining xarakterini
ochib berishi uchun qulay.
2. Bu usullarni dasturlar oson tushunadi va ular qisqa. Eslatib o‘tamiz,
dasturning o‘zi ham xotira egallaydi.
3. Murakkab usullar ko‘p sondagi amallarni talab qiladi, lekin bu
amallarning o‘zlari yetarlicha murakkab bo‘lganlari uchun, kichik n larda tez va
katta n larda sekin ishlaydi. Ammo ularni katta n larda ishlab bo‘lmaydi.
Bitta massivni o‘zida saralashni ularni mos aniqlangan tamoyillari bilan uch
kategoriyaga ajratish mumkin:
1. Qo‘shish orqali saralash (by insertion);
2. Ayirish orqali saralash (by selection);
3. Almashish orqali saralash (by exchange).
To‘g‘ridan-to‘g‘ri qo‘shish orqali saralash. Bu usul qarta o‘yinida ko‘p
qo‘llaniladi. Qartaning elementlari fikran tayyor holdagi a1,a2,……,ai-1
ketma ketliklarga va dastlabki ketma-ketliklar ai, …….,an bo‘linadi.
Har qadamda i=2 dan boshlab i ta element ketma-ketlikdan chiqariladi va
tayyor ketma-ketlikka qo‘yiladi. Bunda u har doim kerakli joyga qo‘yiladi. i ning
qiymati har doim bittaga oshirib boriladi.
Saralashning maqsadi berilgan ob’yektlar to‘plamini aniq bir tartibda
guruhlab chiqish jarayoni ta’riflanadi.
a0, a1... an ketma – ketlik berilgan bo‘lsin.
Ketma – ketlikning elementlarini saralash (masalan: ai <= ai+1 , i = 0 dan n-1
gacha) masalasi qo‘yilgan bo‘lsin. Bu masalani ishlash algoritmini tanlaganda
quyidagilarni baholash zarur: Saralash vaqti – algoritmni baholaydigan asosiy
parametr hisoblanadi. Hotira – algoritm ishlashi uchun ketadigan qo‘shimcha
hotira hajmi. Bunda berilganlar va dastur kodi uchun ketadigan hotira hajmi
hisobga olinmaydi. Turg‘unlik – dasturni ketma – ketlikning boshqa qiymatlarda
ham turg‘un ishlashi tushuniladi. Saralash algoritmlari klassifikasiyasi. Berilgan
ketma – ketlikni saralashda ketma – ketlikning harakteristikasiga mos ravishda u
yoki bu saralash algoritmi olinadi. Aks holda algoritmlar kerakli natijani
bermaydi.
1. “Tez” saralash algoritmi:
“Tez” saralash algoritmi bosqichlari:
2. Massivning o‘rta elementini tanlab olamiz.
3. O‘rta element chap tomoniga o‘rta elementdan kichik elementlarni
joylashtiramiz, o‘rta elementning o‘ng tomoniga esa o‘rta elementdan katta
elementlarni joylashtiramiz.
int i=quyi;
int j=yuqori;
int x=A[(quyi+yuqori)/2];
do {
while(A[i]while(A[j]>x) --j;
if(i<=j){
int temp=A[i];
A[i]=A[j];
A[j]=temp;
i++; j--;
}
} while(i<=j);
Pufaksimon saralash algoritmi.
Massiv elementlarini tepadan pastga qarab saralaymiz. Bunda faqat juft
elementlar ai <= ai+1 ( i = 0 dan n-1 gacha) shart bilan tekshiriladi, agar shart
bajarilmasa ular o‘zaro o‘rin almashtiriladi.
Bu jarayon ohirgi element qolguncha bajariladi. Natijada massiv elementlari
o‘sish tartibida saralanadi.
Dasturdagi bosqichlar:
long i, j,
float x, a[];
for( i=0; i < size; i++)
for( j = size-1; j > i; j-- )
{ if ( a[j-1] > a[j] )
{x=a[j-1]; a[j-1]=a[j]; a[j]=x; } }
Saralashning maqsadi keyinchalik, saralangan to‘plamni qidirilayotgan
elementini topishdan iborat. Bu qariyb universal, fundamental jarayon. Biz bu
jarayon bilan har kuni uchrashamiz – telefon daftaridagi saralash, kitoblar
sarlavhasida, kutubxonalarda, lug‘atlarda, pochtada va h.k. Xatto yosh bolalar ham
o‘z narsalarini tartiblashga o‘rganadi. Saralashning juda ko‘p usullari mavjud. Ular
turli to‘plamlar uchun turlicha bo‘lishi mumkin. Massivlarni saralash uchun
ishlatiladigan usul unga berilgan xotirani ixcham holda ishlatish lozim. Boshqacha
qilib aytganda, saralanayotgan massiv xuddi shu massivni o‘zida amalga oshirilishi
lozim. Saralanayotgan a massivni elementlarini kiritib, unda boshqa bir d massivda
saralangan holda tashkil topgan bizga hech qanday qiziqish uyg‘otmaydi.
tartibidagi saralashlarni talab etadi. Biz quyidagi saralash bo‘yicha bir nechta
sodda va ma’lum usullarni qaraymiz. Ular to‘g‘ri usullar deb aytiladi. Saralash
usullari to‘g‘risida quyidagi fikrlarni bildirish mumkin:
1. To‘g‘ri usullar ko‘plab saralashning asosiy tamoyillarining xarakterini
ochib berishi uchun qulay.
2. Bu usulli dasturlar oson tushuniladi va ular qisqa. Eslatib o‘tamiz,
dasturning o‘zi ham xotira egallaydi.
3. Murakkab usullar ko‘p sondagi amallarni talab qiladi, lekin bu amallarning
o‘zlari yetarlicha murakkab bo‘lganlari uchun, kichik n larda tez va katta n larda
sekin ishlaydi. Ammo ularni katta n larda ishlab bo‘lmaydi.
Bitta massivni o‘zida saralashni ularni mos aniqlangan tamoyillari bilan uch
kategoriyaga ajratish mumkin:
1. Qo‘shish orqali saralash (by insertion);
2. Ayirish orqali saralash (by selection);
3. Almashish orqali saralash (by exchange).
To‘g‘ridan-to‘g‘ri qo‘shish orqali saralash
Bu usul karta o‘yinida ko‘p qo‘llaniladi.
Kartaning elementlari fikran tayyor holdagi ketma-ketlik qismlarga
bo‘linadi.
Har qadamda i=2 dan boshlab i ta element ketma-ketlikdan chiqariladi va
tayyor ketma-ketlikka qo‘yiladi. Bunda u har doim kerakli joyga qo‘yiladi.
i ning qiymati har doim bittaga oshirib boriladi.
To‘g‘ridan to‘g‘ri tanlash yordamida saralash
• Eng kichik kalitli element tanlanadi.
• Uni birinchi element a1 bilan o‘rinlari almashtiriladi.
So‘ng bu jarayon qolgan n-1 element bilan, so‘ngra n-2 element bilan va h.k.
bitta eng katta element qolmaguncha davom ettiriladi.
Pufaksimon saralash:
| 