Guruh talabasi Omonbayev Jaloliddin 7-Topshiriq

911-21 guruh talabasi Omonbayev Jaloliddin
7-Topshiriq
1-kurs talabalari endi C++ fanidan saralash algoritmlarini o’rganishni boshlashdi. Birinchi bo’lib pufakchali saralash algoritmini o’rganishdi. Pufakchali saralash usuli O(n²) amal talab qiluvchi algoritmlardan biri. Unda jami n-1 ta iteratsiya bo’lib, har bir iteratsiyada qo’shni elementlar taqqoslanadi va ular noto’g’ri tartibda joylashgan bo’lsa ularning o’rni almashtiriladi. Har bir iteratsiyada navbatdagi eng katta son o’z joyini topib boradi:
long long k = 0;
for (int i = n; i >= 2; i--) {
for (int j = 1; j < i; j++) {
if (a[j] > a[j+1]) {
int t = a[j];
a[j] = a[j+1];
a[j+1] = t;
k++;
}
}
}
cout<a massiv birdan boshlab indekslangan. Bu masalada sizning vazifangiz berilgan pufakchali saralash dasturi uchun almashtirishlar soni k ni topishdan iborat.
Kiruvchi ma’lumotlar
Birinchi qatorda n – massiv elementlari soni berilgan(1≤n≤10⁵). Ikkinchi qatorda n ta butun son – a massiv elementlari bitta probel bilan ajratib berilgan. Massiv elementlari modul jihatdan 10⁹ dan oshmaydi.
Chiquvchi ma’lumotlar
Bitta sonni – masalaning javobini chiqaring.
Misollar

№	Kiruvchi ma’lumotlar	Chiquvchi ma’lumotlar
1	3 3 1 2	2

#include

using namespace std;
long long merge(int a[], int temp[], int left, int mid, int right) {
int i = left;
int j = mid + 1;
int k = left;
long long almashtrish = 0;
while (i <= mid && j <= right) {
if (a[i] <= a[j]) {
temp[k] = a[i];
i++;
} else {
temp[k] = a[j];
j++;
almashtrish += mid - i + 1;
}
k++;
}
while (i <= mid) {
temp[k] = a[i];
i++;
k++;
}
while (j <= right) {
temp[k] = a[j];
j++;
k++;
}
for (int x = left; x <= right; x++) {
a[x] = temp[x];
}
return almashtrish;
}
long long mergeSort(int a[], int temp[], int left, int right) {
long long almashtrish = 0;
if (left < right) {
int mid = left + (right - left) / 2;
almashtrish += mergeSort(a, temp, left, mid);
almashtrish += mergeSort(a, temp, mid + 1, right);
almashtrish += merge(a, temp, left, mid, right);
}
return almashtrish;}
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
int temp[n];
long long swaps = mergeSort(a, temp, 0, n - 1);
cout << “Almashtrishlar soni : ”<return 0;}