4-Laboratoriya ishi

4-Laboratoriya ishi
7-Topshiriq

1-kurs talabalariendi C++ fanidansaralashalgoritmlarinio’rganishniboshlashdi. Birinchibo’libpufakchalisaralashalgoritminio’rganishdi. PufakchalisaralashusuliO(n²) amaltalabqiluvchialgoritmlardanbiri. Undajami n-1 ta iteratsiyabo’lib, harbiriteratsiyadaqo’shnielementlartaqqoslanadivaularnoto’g’ritartibdajoylashganbo’lsaularningo’rnialmashtiriladi. Harbiriteratsiyadanavbatdagiengkatta son o’zjoyinitopibboradi:

     long long k = 0;

     for (int i = n; i>= 2; i--) {

         for (int j = 1; j

              if (a[j] > a[j+1]) {

                 int t = a[j];

                 a[j] = a[j+1];

                 a[j+1] = t;

                 k++;

              }

         }

     }

  cout<

a massivbirdanboshlabindekslangan. Bu masaladasizningvazifangizberilganpufakchalisaralashdasturiuchunalmashtirishlarsoni k nitopishdaniborat.

Kiruvchima’lumotlar'>Kiruvchima’lumotlar

Birinchiqatorda n – massivelementlarisoniberilgan(1≤n≤10⁵). Ikkinchiqatorda n ta butun son – a massivelementlaribittaprobelbilanajratibberilgan. Massivelementlarimodul  jihatdan 10⁹ danoshmaydi.

Chiquvchima’lumotlar

Bittasonni – masalaningjavobinichiqaring.

Misollar

№	Kiruvchima’lumotlar	Chiquvchima’lumotlar
1	3 3 1 2	2

package com.company;

import java.util.Scanner;

public class Main {

int a[] = new int[10000];
int b[] = new int[10000];
int inv = 0;

public static void main(String[] args) {

// write your code here
int n;
Main main = new Main();
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for (int i = 0; i < n; i++) {
main.a[i] = scanner.nextInt();
}
main.megasort(0, n - 1);
for (int i = 0; i < n; i++) {
System.out.print(main.a[i]+" ");
}
System.out.println("inv: "+main.inv);

}

void megasort(int L, int R) {

if (L >= R)
return;
else {
int m = (L + R) / 2;
megasort(L, m);
megasort(m + 1, R);
int p1 = L, p2 = m + 1;
int p = L;
while (p1 <= m && p2 <= R) {
if (a[p1] <= a[p2]) {
b[p] = a[p1];
p++;
p1++;
} else {
inv += m - p1 + 1;
b[p] = a[p2];
p++;
p2++;
}
}
while (p1 <= m) {

b[p] = a[p1];

p++;
p1++;
}
while (p2 <= R) {
b[p] = a[p2];
p++;
p2++;
}
for (int i = L; i <= R; i++)
a[i] = b[i];
}

}
}