1
$\begingroup$

Eg: In a list of three items ("1", "2", "3") the user is asked which item is higher, 1 or 2. They select 1. They are then asked which is higher, 2 or 3. They select 3. The system then reasons: "1 is higher than 2. If 3 is lower than 2 it must logically be lower than 1 also." etc. (So that you can sort a list of items with the fewest theoretical comparisons possible.) Thanks!

  • 0
    what is the application of this? I mean to say, if you state why you want this, it may be easier to help you.2011-03-24
  • 0
    picakhu - We're building an app that does similar but using algorithmic shortcuts and need a way to prove that it is equivalent in the number of comparisons required to sort a list of items. Thanks2011-03-24
  • 0
    If you can show that your algorithm is in $N \log N$ time, then you are done.2011-03-24
  • 0
    thanks... by "time" are you referring to the number of comparisons? (the user is being asked to manually select the higher of two pairs each time)2011-03-24
  • 0
    Posted on cstheory: http://cstheory.stackexchange.com/questions/5615/is-there-a-program-app-algorithm-that-can-sort-items-using-manual-choices-and.2011-03-25

4 Answers 4