<p><a href="http://en.wikipedia.org/wiki/Inversion_%28discrete_mathematics%29" rel="nofollow noreferrer">Inversions</a> are one way to measure "disorder" in a list:</p>

<blockquote>
  <p>Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i &lt; j$ and $A[i] &lt; A[j]$ then the pair $(i,j)$ is an <strong><em>inversion</em></strong> of $A$.</p>
</blockquote>

<p>However, it's not the only such measure. In general, this concept is formalized in the notion of <strong><em>presortedness</em></strong> - roughly:</p>

<blockquote>
  <p>An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.</p>
</blockquote>

<p>The survey papers by Mannila [1] and Estivill-Castro &amp; Wood [2] might be good places to start. </p>

<p>The question <a href="https://cs.stackexchange.com/questions/11836/how-to-measure-sortedness">How to measure "sortedness"</a> is related.</p>

<hr>

<p>[1] <a href="http://dl.acm.org/citation.cfm?id=2283359" rel="nofollow noreferrer">Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.</a></p>

<p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017" rel="nofollow noreferrer">Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.</a></p>

CC BY-SA 3.0
2014-12-14T07:35:28.870Z
2014-12-14T07:35:28.870Z
2017-04-13T12:48:30.830Z
user103853
<p>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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2014-11-18T16:20:43.997Z
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
<graph-theory><graph-algorithms><randomness><sorting>
How to Quantify Entropy in a Data Set
user103853
# How to Quantify Entropy in a Data Set

(Asked by: username_0 on 2014-11-18)

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?

**Tags:** graph-theory, graph-algorithms, randomness, sorting

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2014-12-14. Score: 4 | Accepted answer

[Inversions](http://en.wikipedia.org/wiki/Inversion_%28discrete_mathematics%29) are one way to measure "disorder" in a list:

> 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$.

However, it's not the only such measure. In general, this concept is formalized in the notion of ***presortedness*** - roughly:

> An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila [1] and Estivill-Castro & Wood [2] might be good places to start.

The question [How to measure "sortedness"](https://cs.stackexchange.com/questions/11836/how-to-measure-sortedness) is related.

---

[1] [Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.](http://dl.acm.org/citation.cfm?id=2283359)

[2] [Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017)


---

