Как найти степень отсортированности массива?

Question

[mamadaliev]

Всем доброго времени суток. Вопрос по алгоритмам сортировок на языке Си/C++.
Объясните пожалуйста, что же такое степень отсортированности массива и как её найти в процентах?



Спасибо.

Answer 1

[longclaps]

Степень отсортированности массива - хрень науке неизвестная, сам придумай как считать. Есть количество инверсий в массиве, считается элементарно:

cnt=0;
for (i=1; i<n; i++)
    for (j=0; j<i; j++)
        if (arr[j]>arr[i])
            cnt++;

Answer 2

[Сергей Кормишин]

Судя по вашей табличке мне кажется Вы ищите Наибольшую неубывающую подпоследовательность.

Делите ее длину на длину массива и получаете проценты.