key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda algoritm
tugaydi.
Shu algoritmga misol ko’rib chiqamiz.
Misol: Talabalar ism-sharifi va tartib raqamidan iborat jadvalni quicksort algoritmi
bilan saralang va nechta o’rinlashtirish amalga oshirilganini aniqlang.
Dastur kodi
#include
#include
using namespace std;
struct table{
int t;
string FIO;};
int q=0;
void qs(table *a,int first,int last){
int i = first, j = last;table x =a[(first + last) / 2];
do {
while (a[i].FIO < x.FIO) i++;
while (a[j].FIO > x.FIO) j--;
if(i <= j) {
if (i < j){ swap(a[i], a[j]);q++;}
i++;
j--;
}
} while (i <= j);
if (i < last)
qs(a,i,last);
if (first < j)
qs(a,first,j);
}
int main(int args, char *argv[])
{ int n;cout<<"n=";cin>>n;
table talaba[n];
for(int i=0;i
talaba[i].t=i+1;
cin>>talaba[i].FIO;
}
qs(talaba,0,n-1);
for(int i=0;i
cout<
cout<<"quicksort algoritmi "<
system("PAUSE");
}
Dastur natijasi:
talabalar sonini kiriting=5
5 ta talabalar FIO sini kiriting
Farhod
Asror
Sobir
Bobur
Vali
| 2 | Asror |
| 4 | Bobur |
| 1 | Farhod |
| 3 | Sobir |
| 5 | Vali |
Bu algoritm jadvalni 3 ta o‘rinlashtirishda saraladi
Topshiriq
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;
}
9
ADABIYOTLAR VA MANBALAR RO’YXATI
1. Adam Drozdek. Data structures and algorithms in C++. Fourth edition. 2013.
2. Н.А.Литвиненко. Технология программирования. “БХВ Петербург”
Санкт-Петербург. 2012 г.
3. Роберт Седжвик. Фундаментальные алгоритмы на C++. Анализ,
Структуры данных, Сортировка, Поиск//К.: Изд. «ДиаСофт», 2007
4. Ma’ruza matnlari. Carnegie Mellon University – CORTINA. 2010. 15-121
Introduction
to
Data
Structures,
(
http://www.cs.cmu.edu/~tcortina/15-
121sp10/lectures.html
)
5. https\\Metanit.com.
10
|
