"Baloncuk" çeşidləmə
Köpük çeşidləmə (ing. bubble sort) — sadə bir çeşidləmə alqoritmidir. Anlamaq və tətbiq etmək baxımından bu alqoritm ən sadədir, lakin yalnız kiçik massivlər üçün effektivdir. Tədris məqsədli sayılır və tədris ədəbiyyatından kənarda nadir hallarda istifadə edilir; praktikada isə daha çox daxil etmə ilə çeşidləmə tətbiq olunur. Alqoritm, çeşidlənəcək massiv üzərində təkrarlanan keçidlərdən ibarətdir. Hər keçiddə elementlər ardıcıl olaraq cüt-cüt müqayisə edilir və əgər cütdəki sıra səhvdirsə, elementlər yerlərini dəyişir. Massiv üzərində keçidlər, növbəti keçiddə daha dəyişiklik lazım olmayana qədər təkrarlanır, bu da massiv çeşidləndiyini göstərir. Alqoritm keçərkən, yerində olmayan element su içindəki köpük kimi lazım olan mövqeyə "yüksəlir", buna görə də alqoritmin adı belədir.
Vikipediya
Köpük çeşidləmə çox sadə bir alqoritmdir və onun vaxt mürəkkəbliyi O(n^2) təşkil edir. Hər dəfə bütün massivdən keçərkən əvvəlcə qonşu elementləri müqayisə edirik və ehtiyac varsa, onların yerlərini dəyişirik. Bu proses, növbəti keçiddə ən azı bir dəyişiklik edilənə qədər təkrarlanır. Tutaq ki, T keçiddən sonra massiv artıq artan sırada çeşidlənib, onda deyirik ki, T verilmiş massiv üçün çeşidləmə mərhələlərinin sayıdır. Aşağıda bir nümunə verilmişdir. Verilmiş başlanğıc massiv "5 1 4 2 8" götürək və sonra təsvir olunan köpük çeşidləmə alqoritmindən istifadə edərək onu aşağıdakı kimi çeşidləyək:
Birinci keçid:
( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), ilk iki elementi müqayisə etdik və onların yerlərini dəyişdik. ( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), 5 > 4 olduğu üçün yerlərini dəyişdik. ( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), 5 > 2 olduğu üçün yerlərini dəyişdik. ( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), son iki element artıq sıralandığı üçün (8 > 5), alqoritm onların yerlərini dəyişmir.
İkinci keçid:
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), 4 > 2 olduğu üçün yerlərini dəyişdik. ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
T = 2 keçiddən sonra massiv artıq çeşidləndiyi üçün deyirik ki, verilmiş massiv üçün köpük çeşidləmə alqoritminin keçidlərinin sayı 2-yə bərabərdir.
Petrik sinifdə köpük çeşidləmə alqoritmini öyrəndi və müəllimi ona ev tapşırığı olaraq bununla bağlı vəzifələr verir. Müəllim Petrikə artıq çeşidlənmiş A massivini verdi, hansı ki, N fərqli tam ədəddən ibarətdir və iddia edir ki, o, bunu K keçiddən sonra köpük çeşidləmə alqoritmi ilə əldə edib. Vəzifə: verilmiş massivdən sonra K keçiddən sonra əldə edilə biləcək neçə başlanğıc massiv A mövcud ola bilər? Nəticə çox böyük ola bilər, buna görə də onu 20100713 moduluna görə çıxarmaq lazımdır.
Giriş verilənləri
Giriş məlumatları bir neçə testdən ibarətdir.
Birinci sətirdə təbii ədəd T (T ≤ 100000) verilir, bu test hallarının sayını göstərir.
Növbəti T sətir test məlumatlarını ehtiva edir. Hər sətirdə iki tam ədəd N və K (1 ≤ N ≤ 1000000, 0 ≤ K ≤ N - 1) verilir, burada N massiv ölçüsünü, K isə köpük çeşidləmə alqoritminin mərhələlərinin sayını göstərir.
Çıxış verilənləri
Hər test halı üçün qoyulmuş vəzifənin cavabını 20100713 moduluna görə ayrıca sətirdə çıxarın.
Qeyd
Tutaq ki, {a, b, c} (a < b < c) massiv verilib. 6 fərqli başlanğıc massiv variantı mövcuddur:
{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a},
və verilmiş massiv müxtəlif yollarla əldə edilə bilər:
{a, b, c}: çeşidləmədən, çünki massiv artıq çeşidlənib.
{a, c, b}, {b, a, c}, {c, a, b}: bir keçiddə köpük çeşidləmə alqoritmi ilə.
{b, c, a}, {c, b, a}: 2 keçiddə köpük çeşidləmə alqoritmi ilə.