Köpük çeşidləmə (Bubble sort)

Sadalama ilə çeşidləmə (Bubble sort) sadə çeşidləmə alqoritmidir. Bu alqoritm çox asan başa düşülür və tətbiq olunur, amma yalnız kiçik massivlər üçün effektivdir. Əsasən tədris məqsədi ilə istifadə edilir və real məsələlərdə nadir hallarda tətbiq olunur; praktikada daha çox daxil etmə ilə çeşidləmə işlədilir. Alqoritm çeşidlənəcək massivdə təkrar-təkrar keçidlər edir. Hər keçiddə qonşu elementlər müqayisə olunur və yerləri səhvdirsə dəyişdirilir. Bu proses heç bir dəyişiklik olmayana qədər davam edir, bu da massiv çeşidləndi deməkdir. Alqoritm işləyərkən elementlər "köpük kimi" lazımi mövqeyə keçirlər, buna görə də adı belədir.

Vikipediya

Köpük çeşidləmə çox sadə bir alqoritmdir və vaxt mürəkkəbliyi O(n^2)-dir. Hər dəfə massivə başdan sona baxılır, qonşu elementlər müqayisə edilir və lazım olarsa yerləri dəyişdirilir. Bu, bir keçiddə ən azı bir dəyişiklik olmayana kimi təkrarlanır. Tutaq ki, $T$ keçiddən sonra massiv artıq artan sıra ilə çeşidlənib. Onda deyirik ki, $T$ bu massiv üçün köpük çeşidləmə mərhələlərinin sayıdır. Nümunə: başlanğıc massiv "5 1 4 2 8" olsun və bu massivi alqoritmlə aşağıdakı kimi çeşidləyək:

Birinci keçid:

($51$ 4 2 8) $\to$ ($15$ 4 2 8), ilk iki elementi müqayisə etdik və yerlərini dəyişdik. (1 $54$ 2 8) $\to$ (1 $45$ 2 8), dəyişmə: 5 > 4. (1 4 $52$ 8) $\to$ (1 4 $25$ 8), dəyişmə: 5 > 2. (1 4 2 $58$) $\to$ (1 4 2 $58$), son iki element düzgündür (8 > 5), dəyişmə yoxdur.

İkinci keçid:

($14$ 2 5 8) $\to$ ($14$ 2 5 8). (1 $42$ 5 8) $\to$ (1 $24$ 5 8), dəyişmə: 4 > 2. (1 2 $45$ 8) $\to$ (1 2 $45$ 8). (1 2 4 $58$) $\to$ (1 2 4 $58$).

T = 2 keçiddən sonra massiv çeşidlənib, ona görə də bu massiv üçün köpük çeşidləmə mərhələlərinin sayı $2$-dir.

Artıq çeşidlənmiş $A$ massivində $N$ müxtəlif tam ədəd var və deyilir ki, bu massiv dəqiq $K$ keçiddən sonra köpük çeşidləmə yolu ilə alınıb. Tapşırıq: neçə başlanğıc massiv $A$ ola bilər ki, yalnız $K$ keçiddən sonra bu ardıcıllıq əldə olunsun? Cavab böyük ola bilər, cavabı $20100713$ modulunda çıxarın.