Masala #0358

Xotira 16 MB Vaqt 3000 ms
14

Analiz

Insertion sort algoritmi barchaga ma’lum. Shunday bo’lsada yanam bir bor eslatib o’tamiz:

n uzunlikdagi massivni kamaymaydigan tartibda saralash uchun:

  1. arr[1] dan arr[n] gacha barcha element birma-bir yurib chiqiladi;
  2. Joriy element o’zidan oldingilar bilan solishtiriladi;
  3. Joriy elementdan katta bo’lgan barcha elementlar bir pog’ona o’ngga suriladi, bo’sh qolgan joyga joriy element joylashtiriladi.

Misol uchun: 4 3 2 10 12 1 5 6 ketma-ketlikdagi massiv quyidagi ketma-ketlikda saralanadi:

Bu saralash algoritmida asosiy vaqt elementlarni surish uchun ketadi. Jami surishlar soni yuqoridagi jadvalda qizil rang bilan ko’rsatilgan kataklar soniga teng bo’lishi bizga ma’lum.

Siz n ta elementdan iborat arr massivi uchun Insertion sort algoritmi necha marotaba surish amalini ishlatishini aniqlang.


Kiruvchi ma'lumotlar:

Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 15)\) testlar soni kiritiladi. Ikkinchi satrdan boshlab, har bir test uchun alohida ikkita satrning birinchi satrida \(n (1 \le n \le 100000)\), massiv elementlari soni, ikkinchi satrida n ta butun son, \(arr (1 \le arr_i \le 10000000)\) massiv elementlari kiritiladi.


Chiquvchi ma'lumotlar:

Har bir test uchun alohida satrda bitta butun son, masala yechimini chop eting


Misollar
# input.txt output.txt
1
3
8
4 3 2 10 12 1 5 6
5
1 1 1 2 2
5
2 1 3 1 2
12
0
4