[Guest]

i've noticed every comparison sorting algorithm relies on comparing only 2 objects. but it seems to me a ternary algorithm should also be possible.

for example consider a three way balance scale. you put objects in each of the three levers, and based on the results of the levers, you can tell which objects are heavier or lighter. for example, let's say you put 10, 15, and 20 in the scale. the 20 will be down the most, 10 will be the highest, and 15 will be medium.

assume you had such a function, lets call it tri(a,b,c) which returns them in the proper order. write an efficient sorting algorithm.

[superprismatic]

"for example consider a three way balance scale. you put objects in each of the three levers, and based on the results of the levers, you can tell which objects are heavier or lighter." This just isn't true. If the three moments add up to 0, the thing will balance. There are lots of ways for this to happen even when a, b, and c are all different.

[Guest]

How can you say a hypothetical isn't true?

And it is totally possible to create.

But can we get some clarification on the question. What are you asking for an efficient sorting algorithm for 3 objects? Are you asking someone to write the function tri(a,b,c)? As far as I can tell tri(a,b,c) is provided. So what are we supposed to sort?

Edited September 23, 2009 by caligo

[superprismatic]

How can you say a hypothetical isn't true?

And it is totally possible to create.

But can we get some clarification on the question. What are you asking for an efficient sorting algorithm for 3 objects? Are you asking someone to write the function tri(a,b,c)? As far as I can tell tri(a,b,c) is provided. So what are we supposed to sort?

I didn't say a hypothetical isn't true. I just said that a 3 pan balance can balance when the weights aren't all the same.

[Guest]

Wait never mind I understand, write a sorting algorithm based on the fact that we are sorting 3 items instead of 2 at any given time.

@super ummm how so?

Edited September 23, 2009 by caligo

[Guest]

I could write such an algorithm, however I can't see how to get away from binary comparisons within the algorithm, which I think defeats the purpose of the question (i.e., there's no apparent increase in efficiency). Perhaps it's due to the binary nature of computers. I wonder how relevant the thread below is to this discussion:

http://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=387946

[Guest]

This seems like one of those questions that when one first reads it, one thinks "There should be a way to do this." But after thinking about it, I believe the question is incomplete at best, and probably invalid.

What does it mean to compare three items? Isn't is just a set of results from comparing two of the items at a time? a to b, a to c, b to c? What do you mean when you say a to b to c?

[Guest]

Let me guess how this tri(a,b,c) function would work.

Since there are 3! possible permutations for a,b,c the function can return 6 different values.

Example:

If Return

a>b>c 1

a>c>b 2

b>a>c 3

b>c>a 4

c>a>b 5

c>b>a 6

If I am interpreting the question correctly, a function like this would be implemented already for us, and our task is to write another function

that uses this to sort a list of items.

Is this correct?

[Guest]

I realized that what I wrote does not take into account if any of the values are equal.

How many more values could be returned then?

a=b=c

a=b>c

c>a=b

b=c>a

a>b=c

a=c>b

b>a=c

1 + 2*(3 choose 2)

1 for when they are all equal

3 choose 2 because you choose two to be equal

2* since they can be greater or less than the third

7 additions

and 6 from before

The function can return an integer between 1 and 13 inclusive then I think.

Edited September 24, 2009 by mmiguel1

[Guest]

What about a modified quick-sort algorithm?

Use 2 pivots at a time instead of 1. They shouldn't be too close or too far from each other (ideally, their difference should be around 1/3 of the range of values to be sorted).

For all other elements in the list, do the 3-way compare. Dump them into one of three additional lists, one containing all values less than both pivots, one containing values between, and one containing values greater than both pivots.

Concatenate these lists, placing the pivots in their proper places.

Recursively quicksort the three sublists.

[Guest]

"for example consider a three way balance scale. you put objects in each of the three levers, and based on the results of the levers, you can tell which objects are heavier or lighter." This just isn't true. If the three moments add up to 0, the thing will balance. There are lots of ways for this to happen even when a, b, and c are all different.

I imagine this 3-way balance scale is theoretical, with point-sized balances which can support infinite weight. Also, all of the objects are theoretical in that they all have their center of gravity exactly over the point-sized balance.

[Guest]

Let me guess how this tri(a,b,c) function would work.

Since there are 3! possible permutations for a,b,c the function can return 6 different values.

Example:

If Return

a>b>c 1

a>c>b 2

b>a>c 3

b>c>a 4

c>a>b 5

c>b>a 6

If I am interpreting the question correctly, a function like this would be implemented already for us, and our task is to write another function

that uses this to sort a list of items.

Is this correct?

Perhaps it would be simpler if it was something like:

If Return

a>=b>=c 1

a>=c>=b 2

b>=a>=c 3

b>=c>=a 4

c>=a>=b 5

c>=b>=a 6

[Guest]

Perhaps it would be simpler if it was something like:

If Return

a>=b>=c 1

a>=c>=b 2

b>=a>=c 3

b>=c>=a 4

c>=a>=b 5

c>=b>=a 6

Yes, when sorting, if two values are equal then it doesn't matter which order you should put them in.

For the sake of this problem we don't need all 13 possible return values.

Regardless, we aren't tasked with implementing this function, we just assume that an efficient one is already made available to us.

The real problem is to use such a function to efficiently sort a list of elements. [i'm guessing O(n log n)]

The only reason I talked about the possible return values was so that I get an idea about how such a comparison function would communicate its result back to a calling program.

[superprismatic]

Wait never mind I understand, write a sorting algorithm based on the fact that we are sorting 3 items instead of 2 at any given time.

@super ummm how so?

The only way a 3 pan thing can act the way people are answering is if the arm lengths are all the same and the angular distance between arms is 120 degrees. I was thinking of the more general case. Since I never looked at 3-pan puzzles here, I jumped to the wrong conclusions. Sorry.

[Guest]

Allow us to label the objects A,B,C,D,E,....

what about an algorithm that does the following:

1) Compare A,B,and C

2) Take the highest and lowest, and compare D to those

3) Repeat, until all objects have been cycled through - identifying the global maximum and minimum. Remove these two from the list to be sorted (remembering they are the heaviest and lightest)

4) Compare 3 remaining objects

5) Take the highest and lowest, and compare the next object to those

6) Repeat, until all objects have been cycled through - identifying the next heaviest and lightest objects in the group. Remove, and repeat.

Not sure if this is the most efficient way, but it should work.

[Guest]

Modified Insertion Sort

Inserting x into array a sorted lowest to highest of length n greater than 3.

Offset = 0

Length = n

Compare x to a[Length/3] and a[2*Length/3] then depending on the result

If x is least...

Offset = Offset

If x is in the middle...

Offset = Offset+Length/3

If x is greatest...

Offset = Offset+2*Length/3

Length = Length/3

Repeat until Length/3 and 2*Length/3 are the same or one apart or then one more comparison will find the position for x.

That should be pretty efficient.

Edited September 24, 2009 by caligo

[Guest]

ogden's solution is a version of the selection sort. It has time complexity O(n^2).

Caligo's algorithm is for finding the correct spot to put a value in an already sorted list.

I assume that he intends to go to each element in the unsorted list and build a sorted one, one by one using his insertion algorithm.

Since he must go through each element of the unsorted list, he will perform n operations times the (typical) number of operations required to insert the value into the sorted list. Locating the correct position for x requires roughly log base 3 of n operations. Here is where the problem comes in. To insert x into the list, he will need to make room for it by shifting all the elements greater than x up a spot in the array. The time complexity for this will be proportional to n by some fractional factor.

In the end we have n* log(n) * n or time complexity O(n^2 log n).

The best bet for getting efficient sorting algorithms is to copy the binary comparison algorithms already known to be efficient, e.g. mergesort, quicksort. These have O(n log n) time complexity.

Edited September 25, 2009 by mmiguel1

[Guest]

ogden's solution is a version of the selection sort. It has time complexity O(n^2).

Caligo's algorithm is for finding the correct spot to put a value in an already sorted list.

I assume that he intends to go to each element in the unsorted list and build a sorted one, one by one using his insertion algorithm.

Since he must go through each element of the unsorted list, he will perform n operations times the (typical) number of operations required to insert the value into the sorted list. Locating the correct position for x requires roughly log base 3 of n operations. Here is where the problem comes in. To insert x into the list, he will need to make room for it by shifting all the elements greater than x up a spot in the array. The time complexity for this will be proportional to n by some fractional factor.

In the end we have n* log(n) * n or time complexity O(n^2 log n).

The best bet for getting efficient sorting algorithms is to copy the binary comparison algorithms already known to be efficient, e.g. mergesort, quicksort. These have O(n log n) time complexity.

With the 3 object comparison, I believe this selection sort will perform roughly (n-1)^2/4 operations. For smaller sets of objects, this might be ok, but not ideal for larger sets of objects.

[Guest]

I'm not sure what is intended by most efficient: code size, memory allocation, or speed/number of comparisons

[Guest]

speed/computational complexity is my concern.

yeah a merge sort would work, in general, but you need to be a bit more specific.

for example, would it now be more efficient to do 3 groups rather than 2?

me personally I was thinking of a heap sort, but with 3 elements per layer rather than 2.