key+1 dan n-1 gacha deb belgilanadi va 2-qadamga o’tiladi. Aks holda algoritm
tugaydi.
7
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:
8
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
9
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).
3.Oldingi ta’mir qilinganlar soni 2 ga teng bo‘lgan mashinalar raqamlari bo‘yicha kamayish tartibida
joylashtirilsin.
Dastur kodi
#include
#include
#include
struct Car {
int number;
std::string brand;
std::string ownerName;
std::string lastRepairDate;
std::string nextRepairDate;
};
bool compareByNumber(const Car &car1, const Car &car2) {
return car1.number > car2.number;
}
int main() {
int N;
std::cout << "Mashinalar sonini kiriting: ";
std::cin >> N;
std::vector cars(N);
// Mashinalar ma'lumotlarini kiritish
for (int i = 0; i < N; ++i) {
std::cout << "Mashina raqami: ";
std::cin >> cars[i].number;
std::cout << "Mashina markasi: ";
std::cin >> cars[i].brand;
std::cout << "Egasi ismi: ";
10
std::cin >> cars[i].ownerName;
std::cout << "Oxirgi ta'mirlangan sanasi (kun oy yil): ";
std::cin >> cars[i].lastRepairDate;
std::cout << "Keyingi ta'mir uchun sana (kun oy yil): ";
std::cin >> cars[i].nextRepairDate;
}
// Oldingi ta'mir qilingan mashinalarni raqamlari bo'yicha tartiblash
std::sort(cars.begin(), cars.end(), compareByNumber);
// Tartiblangan ro'yxatni chiqarish
std::cout << "\nTartiblangan mashinalar ro'yxati:\n";
for (const auto &car : cars) {
std::cout << "Raqam: " << car.number << ", Marka: " << car.brand << ",
Egasi: " << car.ownerName
<< ", Oxirgi ta'mirlangan sanasi: " << car.lastRepairDate << ",
Keyingi ta'mir sana: " << car.nextRepairDate << "\n";
}
return 0;
11
}
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.
|
