# How to Quantify Entropy in a Data Set

I'm currently creating a program in Java to analysis the pathological cases of Quicksort. Namely, the transition of complexity from O(n^2) to O(nlogn) as a data set gets less ordered. Since Quicksort is a value-based algorithm, the choice of pivot determines its efficiency. We usually (Quicksort 3, and choosing a random element aside) select the first or last element as the pivot in an array. Therefore, since a good pivot is one that splits the array in half symmetrically, a more disordered array will make selecting a good pivot easier; or at least reduce the likely hood of running into the pathological case.

My program gradually randomises this array by swapping some elements each time. When I started to plot the graph of this using gnuplot I notice the trend I expected; a exponential distribution, branching off to a uniform distribution.

My question is, how do I quantify a level of disorder in a array? Is their a better way to gradually make an array of values more disordered?

• An interesting theoretical underpinning: If we draw strings with probability proportional to $2^{-K(x)}$, where $K$ is Kolmogorov complexity, then the expected running time is equal to worst-case running time (see Li and Vitanyi p269 which actually uses Quicksort as an example). So I think Kolmogorov complexity would be a "correct" theoretical answer to your question ... but unfortunately impossible to work with ... maybe that can help guide the solution though. – usul Nov 18 '14 at 16:20

Let $A[1..n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$.
An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.