Anti-QuickSort#869
Sıralama üçün geniş istifadə olunan sürətli çeşidləmə alqoritmi — QuickSort—istifadə olunur. Aşağıda bu alqoritmdən istifadə edərək massivini sıralayan proqram verilmişdir.
var a : array [1..N] of integer;
procedure QSort(left, right : integer);
var m, i, j, t : integer;
begin
m := a[(left+right) div 2];
i := left; j := right;
repeat
while a[i] < m do inc(i); {birinci while}
while a[j] > m do dec(j); {ikinci while}
if i <= j then
begin
t := a[i]; a[i] := a[j]; a[j] := t;
inc(i); dec(j);
end;
until i > j;
if j > left then QSort(left, j);
if i < right then QSort(i, right);
end;
begin
...
QSort(1, N);
end.
QuickSort orta hesabla ən sürətli sıralama alqoritmi olsa da, bəzi hallarda çox uzun müddət işləyə bilər. Alqoritmin iş vaxtını, massiv elementləri ilə müqayisələrin sayı ilə qiymətləndirəcəyik (yəni, birinci və ikinci whileda ümumi müqayisələrin sayı). Sürətli çeşidləmənin maksimum sayda belə müqayisələr edəcəyi testi yaradan proqram yazmaq lazımdır.
Birinci sətirdə tək bir ədəd (1 \leq N \leq 70000) verilir.
Sürətli çeşidləmənin maksimum müqayisə sayını yerinə yetirəcəyi -dən -ə qədər olan ədədlərin bir permutasiyasını çıxarın. Belə permutasiyalardan bir neçəsi varsa, istənilənini çıxarın.
Nümunə 1