K-çeşidləmə

Sıralama verilmiş ədədlər massivini (və ya digər obyektləri) artan və ya azalan qaydada düzülməkdir. Bu tapşırığın bir çox müxtəlif növləri və onların çoxu üçün olduqca səmərəli alqoritmlər mövcuddur. Bu alqoritmlər üçün mühüm parametr massiv elementlərini sıralamaq üçün tələb olunan dəyişmələrin (swap) sayıdır.

Bu məsələdə biz $k$-sıralama adlanan bir variantı nəzərdən keçiririk. $k$-sıralamada siz $k$-dəyişmə (k-swap) edə bilərsiniz, bu da indeksi tam olaraq $k$ fərqlənən iki massiv elementinin qiymətlərini dəyişməyə imkan verir. Məsələn, [$6$, $10$, $4$, $1$, $2$] massivini k = 3 üçün nəzərdən keçirək. Bu massiv belə iki əməliyyatla artan qaydada sıralana bilər: birinci dəyişmədən sonra massiv [$1$, $10$, $4$, $6$, $2$] olur; ikinci dəyişmədən sonra isə [$1$, $2$, $4$, $6$, $10$] alınır.

Verilmiş a_1, a_2, \ldots, a_n tam ədədlər massivini nəzərə alaq. Tapşırığınız, bu massiv artmayan qaydada sıralanarkən ən az neçə $k$-dəyişmənin tələb olunduğunu tapmaqdır.