Masala #0358
Analiz
Insertion sort algoritmi barchaga ma’lum. Shunday bo’lsada yanam bir bor eslatib o’tamiz:
n uzunlikdagi massivni kamaymaydigan tartibda saralash uchun:
- arr[1] dan arr[n] gacha barcha element birma-bir yurib chiqiladi;
- Joriy element o’zidan oldingilar bilan solishtiriladi;
- 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.
Kirish faylining dastlabki satrida bitta butun son, testlar soni kiritiladi. Ikkinchi satrdan boshlab, har bir test uchun alohida ikkita satrning birinchi satrida , massiv elementlari soni, ikkinchi satrida n ta butun son, massiv elementlari kiritiladi.
Har bir test uchun alohida satrda bitta butun son, masala yechimini chop eting
# | 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 |