Re: Degree of so/unrtedness - please help a programmer


almurph@xxxxxxxxxxxxx wrote:
Hi,

Apologies if I'm in the wrong forum or if this is too lightweigh but
I'm at the end of my teather.
Say you have an array of say integers - and you want to determine
how well sorted or unsorted said array is - my question is how do you
do this?
I have searched high and low for an algorithm on Google and all my
coding books but have come up zip! I can't believe it - surly there
must be an algorithm that can quantify sortedness for an array?

I would greatly appreciate any
advice/comments/code-samples/references that you may have to offer me.

BTW, this issue came about as I weas reading about the differing
amoung of sorting techniques (like quicksort, bubble etc...) All of the
books tak about selecting the right algorithm based upon the degree of
sortedness but *none* say anythign about how to measure this!

To keep it simple, here's a Web page which lists a few way, in the
context
of sort algorithms:

[Measures of sortedness]
http://www.cs.duke.edu/~mlittman/courses/Archive/cps130-97/lectures/lect05/node16.html

regards, chip

.

Relevant Pages

  • Re: Degree of so/unrtedness - please help a programmer
    ... Say you have an array of say integers - and you want to determine ... I have searched high and low for an algorithm on Google and all my ... must be an algorithm that can quantify sortedness for an array? ... mind is longest monotonic subsequence. ...
    (sci.math)
  • Re: Degree of so/unrtedness - please help a programmer
    ... Say you have an array of say integers - and you want to determine ... I have searched high and low for an algorithm on Google and all my ... must be an algorithm that can quantify sortedness for an array? ... permutations that slow it the most, and invent a measure of unsorted- ...
    (sci.math)
  • Re: regex question - trying to find ".mp3" in a SELECT box
    ... But `Array' is a Function object reference. ... Establish a new execution context using F's FormalParameterList, ... Since is not a primitive value, the exception should be thrown. ... | 5.2 Algorithm Conventions ...
    (comp.lang.javascript)
  • Re: Mergesort Vs Quicksort
    ... I might not have correctly remembered my algorithm of months ago ... for sorting records in an array using one auxilary of the ... on how things turn out from lower levels of recursion, ... whether the number of records in the array segment to be sorted is ...
    (comp.programming)
  • Re: Reference to derived type element by index?
    ... as a set of distinctively-named scalars. ... In another scope, the same common block ... would be a single array. ... algorithm and a specific application of the algorithm, ...
    (comp.lang.fortran)
Quantcast