Meanwhile knowing how "sorted" an array is gives some information about the array and might help sorting it more efficiently, it is not quite right, that quick-sort runs in $O(n^2)$ if the array is sorted. The running time of quick-sort depends on the pivoting rule and your statement holds only if we always choose the first (or last) element as the pivot. A good way to avoid this problem is to shuffle the whole input randomly before we start sorting.
Now to gain more information about how "sorted" the array is, we have to define this quantity formally. We need a formal mathematical definition of "sortedness" before we can design an algorithm to measure it. Here are two different quantities that show in some way the "sortedness" of the array. Let us call the input array $A := a_1, \dots a_n$ where $n$ is the length of the array.
The first of which is the number of "inversions". So what are inversions? - you might ask. Inversions are pairs $(i, j)$ such that $i < j$ and $a_i > a_j$. Of course in a sorted array we have no inversions. Counting inversions can be done in running time $O(n\log n)$ using different methods among which are divide and conquer and using balanced search trees. However since counting inversions is not faster than sorting, I would not recommend it to find how sorted an array is as a pre-sorting routine.
Another measure is the minimum number of elements to be removed to turn the array sorted. This problem is equivalent to finding the longest increasing subsequence and it has an $O(n \log n)$ algorithm using dynamic programming. However, there is an simple linear time two approximation algorithm for this problem. Intuitively, the algorithm removes pairs of adjacent inversions until the array contains no more inversions. In pseudo-code the algorithm goes as follows:
- Let L be an empty linked list
- For each a := a[1] .. a[n] do
- Append a to L.
- Set i := 1
- While a[i] is not the last element in L
- while a[i] no the first element in L
and a[i] < a[i-1] do
- remove a[i] and a[i-1] from L
- Set i to the next element.
- Set i to the next element.
Each time we remove two elements from $L$, they form an inversion an at least one of them should be removed. Hence we remove at most twice as many as the total number of elements that must be removed. Note that the running time can be bounded in $O(n)$ since the outer while iterate over all elements once and each call of the inner loop removes two elements and hence it can not be called more than $O(n)$ times in total.
One way to use this measure to sort arrays more efficiently is to use the previous algorithm to find all such pairs. Let $L_1$ be the list above after removing the elements from it and $L_2$ the list of all removed elements. Now since we know that $L_1$ is sorted, all we need to do is to sort $L_2$ in $O(h\log h)$ assuming $h$ is the number of elements has to be removed to turn the array sorted. Using some kind of sliding window (the conquer part of merge sort), we can build a sorted version of $A$ combining $A_1$ and the sorted version of $A_2$ in linear time. In total we get an adaptive sorting algorithm running in $O(n + h \log h)$.
[1,2,3,4,5,7,6]is almost sorted, I would expect this fictional algorithm to output something like 0.9, while the score of[4,3,2,1]should be 0. Depending on this output, I shall choose which algorithm to use. $\endgroup$