7
\$\begingroup\$

Don't you hate it when you're trying to roughly sort a list based on user data, but you have to poll the user for thousands of comparisons?

Hate no more, because the answers to this challenge are (going to be) here!

Method

The sorted-ness of a list is defined by how many possible comparisons it has which are correct.

Let's have an example. The list [1, 2, 4, 3] has the possible comparisons 1 <= 2, 1 <= 4, 1 <= 3, 2 <= 4, 2 <= 3 and 4 <= 3. 1 out of those 6 comparisons are incorrect, so this list is (5 / 6) * 100 = 83.33% sorted.

Challenge

Create a program or function that sorts a given list (but not necessarily 100%) and sorts all of the below test cases by at least 75%.

If your program sorts a list by less than 75% that is not in the test cases, that's okay, but try not to hard-code to the test-cases although I can't ban you from doing so.

You must use a comparison sort. Pretend the numbers are black boxes that only support comparison operations.

Your program may sort the list backwards, which means if it's is able to sort all of the test cases by less than 25%, you can post it as a backwards sort.

For programs that perform STDIO, the list should be taken and printed as base-10 integers with some kind of separator, with optional text at the start and end (for example 1\n2\n3 or [1, 2, 3])

You may also return or print a list of indices that correspond to the sorted list (e.g. [1, 3, 2] when sorted is indices [0, 2, 1])

You may not compare any of the elements of the list with any constant values.

The defaults for I/O and standard loopholes apply as usual.

Scoring

This is a , not a . Your code is scored by the highest number of comparisons your code needs to be able to sort across all of the test cases.

A comparison is defined as any operation that involves a value x from the given list and another value y which may or may not also be from the given list, and does a boolean check of one of x < y, x <= y, x == y, x >= y or x > y or returns a result depending on whether x < y, x == y or x > y. This includes any expressions, including mathematical equations, that have the same effect of comparison.

The test cases are here.

To verify your sorted lists, use this program.

The lowest score wins. Good luck!

\$\endgroup\$
  • \$\begingroup\$ Given that it takes about n log n comparison for a naive algorithm, make sure that there are >> n log n lists with some length may work. For example, if each list has length 200, having 50000 tests should be ok. \$\endgroup\$ – user202729 Nov 24 '18 at 10:40
  • \$\begingroup\$ Is this code valid? (100% sorted, no observable comparison) \$\endgroup\$ – Arnauld Nov 24 '18 at 13:47
  • 1
    \$\begingroup\$ Are we required to use a comparison sort, that is, only access the list by comparing pairs of values at given indices? I'm unclear in general how many operations on elements can be scored if they are not comparisons. \$\endgroup\$ – xnor Nov 24 '18 at 21:19
  • 2
    \$\begingroup\$ @LyricLy Haha, I ninja-fixed the link. I think this makes sense, but could be made clearer and more precise in the challenge text. The usual model for this is that you have a black-box function that takes two indices i and j and tells you whether a[i]<a[j] (or since, you allow ties, it could give cmp(a[i],a[j]). \$\endgroup\$ – xnor Nov 24 '18 at 21:23
  • 2
    \$\begingroup\$ Please clarify whether an answer is required to sort all lists 75% of the way (given “To poorly sort a list, you must sort it at least 75% of the way.… Create a program or function that poorly sorts a given list”), or whether it’s allowed to sort the given test cases 75% of the way while sorting other possible inputs less than 75% of the way (given “and sorts all of the below test cases by at least 75%”)? I assumed the former, but it looks like @xnor assumed the latter. \$\endgroup\$ – Anders Kaseorg Nov 25 '18 at 3:11
3
\$\begingroup\$

Python 3, score 244

def sort_func(l):
	num_pieces = 9
	
	medians = [median5(l[5*i : 5*(i+1)]) for i in range(num_pieces)]
	
	center = median(medians)
	
	lows = []
	highs = []
	
	for x in l:
		if x < center:
			lows.append(x)
		else:
			highs.append(x)
	
	for d in range(9):
		for lst in [lows, highs]:
			if lst[d] > lst[~d]:
				lst[d], lst[~d] = lst[~d], lst[d]
	
	l[:] = lows + highs

def median(lst):
	lst.sort()
	return lst[len(lst)//2]

def median5(l):
	a, b, c, d, e = l

	if a > b: a,b=b,a
	if c > d: c,d=d,c

	if a < c:
		a = e
		if a > b: a,b=b,a
	else:
		c = e
		if c > d: c,d=d,c

	if a < c:
		if b > c:return c
		else: return b
	else:
		if d > a:return a
		else: return d

Try it online! Thanks to user202729 for making the comparison-counting class for verification.

The algorithm has 3 parts:

  • Estimate the median of the list (~76 comparisons if unlucky)
  • Compare each element to the estimated median and put it in the low or high sub-list (150 comparisons, 1 per list element)
  • Tweak each of the low and high lists by swapping the first and last elements if they are other of order, then the 2nd and 2nd to last, up to the 9th and 9th-to-last (18 comparisons)
  • Output the concatenated low and high list

The idea is that if we knew the median of the list, we could partition the list into its low and high halves by comparing each element to the median. Then, putting the high half after the low half, any comparison between elements from different halves is correct. On average half the within-half comparisons happen to be right, so a random comparison has about a 75% chance of being correct overall.

Sometimes though we get unlucky in the random comparisons for a given list. So, we improve each half a little by swapping the first and last element if they happen to be out of order, since this is the highest-impact swap for one comparison. Then, do the same for the 2nd and 2nd-to-last element, and so on. It turns out that doing this for 9 elements on each end for each half is enough to bring us over the 75% mark for all the test cases.

The median used is an estimate, since finding the actual median is too expensive, which also contributed to getting worse-than-average scores. It's estimated by taking 9 groups of 5 elements, finding the median of each, and then finding the median of those values.

The median of 5 is found using an worst-case-optimized algorithm that uses a maximum of 6 comparisons. The median of 9 is computed naively by sorting, which is surely inefficient. There are algorithms that use 14 comparisons in the worst cases, but I haven't found code for one.

A potential improvement would be to used the information gained in the median-finding step in the sorting step. We already know how the median compares to itself, the 8 other elements in the list of medians, and the 4 other elements in its group. This would save 13 comparisons, for a score of 231.

Further information could be gleaned using elements that were found smaller (resp, bigger) than a median that is itself smaller than the median-of-medians. We could also put each element used in the median finding into its estimated rank position in the final list.

Another potential improvement would be to use the full cmp comparisons rather than just < to better handle the case when elements are equal, for exactly by putting elements equal to the estimate median into the middle.

\$\endgroup\$
3
\$\begingroup\$

Python 3, score = 172 164

def shell(a, cmp):
    for step in [148, 138, 107, 43]:
        for i in range(len(a) - step):
            if cmp(a[i], a[i + step]) > 0:
                a[i], a[i + step] = a[i + step], a[i]

Try it online!

Four passes of Shellsort.

Python 3, score = 229 196

def insert(x, a, cmp):
    if not a:
        return [x]
    m = len(a)//2
    c = cmp(x, a[m])
    if c < 0:
        return insert(x, a[:m], cmp) + a[m:]
    elif c > 0:
        return a[:m + 1] + insert(x, a[m + 1:], cmp)
    else:
        return a[:m] + [x] + a[m:]

def ford_johnson(a, cmp):
    if len(a) <= 1:
        return a
    m = len(a)//2
    cmp1 = lambda x, y: cmp(x[-1], y[-1])
    b = ford_johnson([insert(x, [y], cmp) for x, y in zip(a[:m], a[m:2*m])], cmp1)
    if len(a) % 2:
        b += [[a[-1], None]]
    for k in range(m, len(a)):
        l, i, (x, y) = max((-i.bit_length(), i, t) for i, t in enumerate(b) if len(t) == 2)
        b[:i + 1] = insert([x], b[:i], cmp1) + [[y]]
    if len(a) % 2:
        b.pop()
    return [x for x, in b]

def thirty_four(a, cmp):
    for i in range(34):
        a[i::34] = ford_johnson(a[i::34], cmp)

Try it online!

Consider the list as 34 interleaved lists and sort each independently, using the Ford–Johnson merge-insertion sort.

\$\endgroup\$
  • \$\begingroup\$ I know it's allowed, but can it fail on some other cases? \$\endgroup\$ – l4m2 Nov 25 '18 at 5:15
  • \$\begingroup\$ @l4m2 Yeah, for example, [-(i%34) for i in range(150)] is not in the test cases and only gets 45.7% sorted. \$\endgroup\$ – Anders Kaseorg Nov 25 '18 at 5:32
0
\$\begingroup\$

Python 3, score 757

def f(l):
	a = 0  # we are going to sort the first (a) elements
	n = len(l)
	while (
			a*(a-1)//2  # there are ~ pairs that is guaranteed to be in order
			<=
			n*(n-1)//2  # total number of pairs
			*0.75):  # it's possible to compute this in O(1), but I'm lazy
		a+=1
	return sorted(l[:a])+l[a:]

Try it online!

The solution simply sorts about first ~75% of the array, so that it's guaranteed to be valid.

Python sorted takes about O(n log n) comparison.

\$\endgroup\$
  • \$\begingroup\$ Can you use a custom array-type that counts all comparisons? \$\endgroup\$ – michi7x7 Nov 24 '18 at 16:12
  • \$\begingroup\$ @michi7x7 Currently I'm using a custom object type for that. What's the difference? \$\endgroup\$ – user202729 Nov 24 '18 at 16:18
  • \$\begingroup\$ Ah, so that's how you computed your score. You didn't mention that \$\endgroup\$ – michi7x7 Nov 24 '18 at 16:23
  • 1
    \$\begingroup\$ @MishaLavrov If you read the code instead of the explanation, you’ll see that it actually computes the smallest a such that a(a−1)/2 > n(n−1)/2 · .75, so it sorts about √75% ≈ 86.6% of the array. \$\endgroup\$ – Anders Kaseorg Nov 25 '18 at 3:06
  • \$\begingroup\$ @AndersKaseorg Thanks for spotting that! I indeed only read the explanation and not the code. \$\endgroup\$ – Misha Lavrov Nov 25 '18 at 3:21
0
\$\begingroup\$

JavaScript (Node.js), 669

cnt=0;
function wtf(arr){return arr.length*~-arr.length}
function finished(arr) {
  x = 150*149*.25; // toleration
  for (i in arr) x-=wtf(arr[i]);
  return x>=0;
}
function cut(arr) {
  rnd=(Math.sin(arr.length)*1237812731+127317823102)%arr.length|0;
  tmp=[[],[arr[rnd]], []];
  for(i=0; i<arr.length; i++) if(i!=rnd) {
    cnt++;
    //tmp[arr[i]<arr[0]?0:1].push(arr[i]);
    if(arr[i]<arr[rnd]) tmp[0].push(arr[i]); else
    if(arr[i]>arr[rnd]) tmp[tmp.length-1].push(arr[i]); else
    tmp.splice(1,0,[arr[i]]);
  }
  //console.log(arr.length+','+t)
  return tmp;
}
function nesort(arr) {
  e=[arr];
  while(!finished(e)){
    x*=-5;
    t=0;
    for(i in e) if(e[i].length>e[t].length)t=i;
    for(i in e) if(e[i].length<e[t].length && wtf(e[i])>x)t=i;
    e.splice(t,1,...cut(e[t]));
  }
  return (e+'').match(/\d+/g).map(parseFloat);
}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.