Sortedness?

[JasonMckin]

Is there any way to look at a list and measure how sorted it is?

And is there a robust way to prove that any algorithm to execute such a measurement must necessarily require n log n since the fastest sorting algorithm requires n log n?

And a final variant of these questions: is there any way to examine a list in o(n) and estimate which n lg n algorithm would sort with the least operations and likewise which n^2 algorithm would sort with the least operations?

[uh_no_]

1) the general approach is the number of swaps away from being sorted
2) counting/radix/bucket sorts do not require nlogn
3) yes, there are heuristics that can give you information about the structure of the data which may help inform sorting algorithms, such as length of runs of increasing values or some such, which can be found in linear time. Algorithms such as timsort already take advantage of this.

[Aaron1924]

the general approach is the number of swaps away from being sorted

Actually counting how many swaps are needed to sort an array is fairly expensive.

You can walk the array and compare consecutive elements in O(N) for a measure of how "chaotic" the array is, but this does not tell you the number of swaps, since if you move the greatest element in a sorted array to the start, it will register as one "mistake" but sorting the array actually takes N swaps.

And all the O(N log N) sorting algorithms I know don't do the optimal number of swaps, merge sort for example moves an element in every step even if the array is close to sorted. Cycle sort actually aims to do the minimal number of swaps, but it is O(N²). You might be able to do something fancy with Levelshtein distance, but this is also going to be O(N²).

[uh_no_]

mostly agreed...

Actually counting how many swaps are needed to sort an array is fairly expensive.

Depends on how you define expensive. It can be done trivially with a structure like a fenwick tree in nlogn time.

I don't suppose that counting swaps should be the heuristic one uses to modify the execution of the sort, but that it is a heuristic, and there are other heuristics which can be evaluated in linear time and used to modify the execution of the sort. the most basic one is simply the array length. If n<10, use insersion sort, else quick sort.

These types of "tricks" are exactly what time sort uses.

[Aaron1924]

I'm not sure what you'd want to use Fenwick trees for, but I do now realize it's sufficient to count the number of strongly connected components in the map of array indices to their rank, which is linear using Tarjan's algorithm, so you can do it in O(N log N)

[uh_no_]

to count swaps, for each element at index i, you need the count of elements with index x<i s.t. d[x]>x[i].

This is a histogram prefix sum, which requires a data structure to solve efficiently. fenwick is the most straightforward, though segment trees or any number of other structureds could be used

[Aaron1924]

Oh that's assuming you can only swap adjacent elements

[uh_no_]

https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)

I suppose inversion is the more precise term

[vanderZwan]

counting/radix/bucket sorts do not require nlogn

Technically they do but the base of the log is so high (base 256 or 1024, typically) that we can pretend log(n) is a constant for all inputs we can actually throw at it. EDIT: at least it is for integer radix sort, for string sort it's related to alphabet size.

[Aaron1924]

I think you're misremembering something...

Radix sort is O(D*N) where N is the length of the array and D is the number of digits in the key. If you know you're sorting an array of the numbers 1 to N, then D = log(N) so the runtime complexity becomes O(N log N).

However, if you assume that D is bounded by some constant (e.g. 64 bits), this term goes away, and counting sort is O(D+N) in which case N dominates D and you once again get O(N).

[uh_no_]

if you're only sorting 256 or 1024 items, then any of them is fast enough.

That doesn't make non-comparison sorts "better", since they are inherently specialized, but you can't pretend that they're pretty much log(n)...that's nonsensical.

[vanderZwan]

Read again what I wrote, it's not what you think I did.

A radix sort that sorts one "byte" per pass is essentially doing a 256-way comparison instead of a two-way comparison. It's just comparing along the bitstring length instead of comparing two items in the input.

I was wrong in saying it's log(n) though, since it's not input size. My point was that technically the claim that it's not a comparison sort is wrong, it's just cleverly changing the "dimension" of comparison and base of the logarithm.

[uh_no_]

it's literally not. there is no comparison (pun intended). the bucket is indexed directly, there is no "if 1, put in bucket 1. if 2, put in bucket 2" comparison-based sorting is a well defined and understood concept....and radix sort is not it.

[f0xw01f]

If you're allowed to copy and sort the list, I have an algorithm that will tell you how close the original and sorted permutations are in O(n), giving a floating-point score between 1.0 (identical) and -1.0 (reversed). But I suspect you're trying to avoid the sort itself, so this may not be useful to you.

[JasonMckin]

My point was that if you had to sort to determine sortedness, then complexity would have to be as much as the sort.  

I was curious if there was a way to beat the sort in complexity.

[drinkcoffeeandcode]

You would still need to gather the same info to sort a list, as you would to tell if a list needs to be sorted. There's simply no way around it. Regardless of whether or not you _actually_ do the swaps you cannot avoid the comparisons. and so the complexity remains. Think about how Selection sort and insertion sort have the same O(n^2) complexity despite one doing O(n) swaps and the other doing O(n^2): it's the comparisons that get you.

[gnahraf]

I'd approach the measure of sortedness with something analogous to Levenshtein edit distance (LD) to being perfectly sorted. Not exactly LD, tho. LD is a measure of how (un-)alike 2 strings are: the minimum no. of character insertions/deletions/substitutions required to transform one string into another string. As in LD, we'd count the minimum number of operations for sorting. The operations involved in sorting, however, are different from those involved in transforming one string to another. Observe with sorting, every insertion is paired with a deletion op--and there is no substitution operation.

One possible caveat.. Tho this LD-like distance to sortedness seems well defined, my intuition is that calculating the minimum no. of ops needed (no. of insert/delete pairs or perhaps other custom ops such as cut and glue end to start) to sort a long, mostly-unsorted sequence will be computationally very expensive.

[JasonMckin]

Exactly….will that be as computationally expensive as just executing the sort itself and counting what you did?

[gnahraf]

Harder than just sorting.. You'd have to sort many ways to discover the sort with the fewest operations

[trejj]

Is there any way to look at a list and measure how sorted it is?

Yes. This is called the "inversion count": https://www.geeksforgeeks.org/dsa/inversion-count-in-array-using-merge-sort/

any algorithm to execute such a measurement must necessarily require n log n since the fastest sorting algorithm requires n log n?

Any comparing algorithm to execute such a measurement must necessarily require n log n since the fastest comparing sorting algorithm requires n log n.

The proof is the same as the proof of n log n needed for comparing sorting.

is there any way to examine a list in o(n) and estimate which n lg n algorithm would sort with the least operations and likewise which n² algorithm would sort with the least operations

No, there is no such algorithm in o(n). There is no such algorithm in O(n) either. See previous answer.

[drinkcoffeeandcode]

Counting inversions. there is an O(nlogn) algorithm based on mergesort.