[Simown]

I've been away a while with general busyness but I'm back to set you a challenge!

The basic idea is this: write your own sorting method without using indices (square bracket notation [ ])

For example, in a normal sorting method you might want to swap positions i and j. Code like this:

n[i], n[j] = n[j], n[i]

This is not allowed. As a further restriction, I am not allowing any square brackets in your code, even if they aren't indexing anything. Time to think outside the box a bit.

For example, when you have written your function use a random number generator to test it:

import random

for i in range(5):
  sortedIntegers = mySortingMethod(list(random.randint(0, 100) for x in range(20)))
  print sortedIntegers
....
[1, 2, 2, 11, 11, 15, 16, 18, 23, 27, 35, 38, 39, 57, 57, 57, 64, 81, 81, 97]
[0, 5, 6, 6, 15, 21, 21, 35, 46, 49, 62, 62, 65, 67, 70, 73, 78, 80, 89, 90]
[0, 0, 6, 14, 14, 27, 31, 33, 49, 52, 53, 57, 58, 60, 69, 86, 90, 93, 95, 100]
[2, 8, 8, 15, 20, 20, 22, 22, 33, 35, 37, 41, 44, 44, 45, 70, 79, 84, 88, 96]
[2, 8, 12, 15, 19, 19, 30, 37, 40, 41, 46, 51, 60, 63, 65, 75, 79, 79, 92, 99]

A few rules:
* It must be a single top-level function (nested helper functions are fine) that sorts a random LIST of integers into ascending order
* Built-in sorting functions are not allowed, nor functions from another module not packaged with Python
* There are allowed to be repeats in the random sequence of integers, it must deal with this
* Right now, only Python entries will be accepted, I may open it up to other languages in the future, implementations in other languages are fine but will not be judged in the challenge.
* Python 2 or 3 is fine
* The winner will be the person who enters the fastest sorting method timed by me, there is also an award for the most creative submission.


After a few entries or a bit of interest I'll release my solution I've already written for you all to have a peek at

Happy Challenging! Let's see what you can do.

EDIT: I should really set a deadline, 2 weeks from today should be good to be get plenty of entries so Sunday 16th September 2012 will be the cut off.

This post has been edited by Simown: 12 September 2012 - 11:51 AM

[sepp2k]

Does it matter whether the function works in-place or not? Does the "single function" rule also disallow nested helper functions (like say def mergeSort(lst): def merge(lst1, lst2): ...)?

Oh and something rather cheaty just occurred me: When you say "without using indices (square bracket notation [ ])", does that imply that any construct not involving square brackets is allowed?

[Simown]

You are allowed nested helper functions, like the merge sort example you gave. Especially if it's going to be recursive of course! What I probably meant is that I need to be able to call it as a single top-level function:

aFunction(aList)

Anything beyond that is up to you.

Any construct not involving square brackets is allowed, yep. I'd prefer if at least a little effort went in to it. The entire sorting method has to be written manually, after all.

As for in-place functions - I don't mind. If it's timeable and adheres to the rest of the rules, I'll allow it.

This post has been edited by Simown: 02 September 2012 - 09:02 AM

[sepp2k]

Okay, I've come up with two solutions. One is a non-cheaty implementation of mergesort:

Spoiler

def mergesort(lst):
  def merge(lst1, lst2):
    merged = list()
    i1 = lst1.__iter__()
    i2 = lst2.__iter__()
    v1 = i1.__next__()
    v2 = i2.__next__()
    try:
      while True:
        if v1 <= v2:
          merged.append(v1)
          last = v2
          v1 = i1.__next__()
        else:
          merged.append(v2)
          last = v1
          v2 = i2.__next__()
    except StopIteration:
      # The value in last has already been taken out of its iterator, but has not yet been
      # added to the result list. Let's do that now.
      merged.append(last)
      # One of the two iterators is now empty, but the other may still have items
      # Iterate over both iterators to get the items that are left in one of the iterators
      for v in i1:
        merged.append(v)
      for v in i2:
        merged.append(v)
    return merged

  if len(lst) == 1:
    return lst

  lst1 = list()
  lst2 = list()
  
  for i, v in enumerate(lst):
    if i < len(lst)/2:
      lst1.append(v)
    else:
      lst2.append(v)

  lst1 = mergesort(lst1)
  lst2 = mergesort(lst2)
  return merge(lst1, lst2)

The other is a cheaty implementation of in-place quicksort:

Spoiler

def cheaty_quicksort(lst):
  def qs(fro, to):
    if fro < to:
      pivot_idx = random.randint(fro,to)
      pivot = lst.__getitem__(pivot_idx)

      right = to
      left = fro

      def seek():
        nonlocal left, right
        while lst.__getitem__(left) < pivot:
          left += 1
        while lst.__getitem__(right) > pivot:
          right -= 1

      def swap(i,j):
        tmp = lst.__getitem__(i)
        lst.__setitem__(i, lst.__getitem__(j))
        lst.__setitem__(j, tmp)

      while left <= right:
        seek()
        if left <= right:
          swap(left, right)
          left += 1
          right -= 1

      qs(fro, right)
      qs(left, to)

  qs(0, len(lst)-1)

Neither of them has been optimized for speed.

This post has been edited by sepp2k: 02 September 2012 - 12:24 PM

[Simown]

Haha, I see what you meant by "cheaty", but I guess it doesn't break the rules. The first one is nicely done, except one tiny thing: you created two empty lists in your code with square brackets! Change it to list() and it's perfect.

[sepp2k]

Simown, on 02 September 2012 - 08:59 PM, said:

you created two empty lists in your code with square brackets! Change it to list() and it's perfect.

Thanks, I missed that. Fixed now.

[baavgai]

I thought, rather than doing a proper sort, I'd do something appropriately pythony and see how far I got.

Quite satisfying, actually.

Spoiler

def mySortingMethod(nums):
	def getNext(nums):
		while len(nums)>0:
			n = min(nums)
			nums.remove(n)
			yield n
	return list(n for n in getNext(nums))

[baavgai]

Not enough play time on that last one. Here's a bubble sort:

Spoiler

def mySortingMethod(nums):
	swapped = True
	while swapped:
		swapped = False
		head = list()
		n1 = nums.pop(0)
		while len(nums)>0:
			n2 = nums.pop(0)
			if n2 < n1:
				head.append(n2)
				swapped = True
			else:
				head.append(n1)
				n1 = n2
		head.append(n1)
		nums.extend(head)
	return nums

[Simown]

Time to show one of my solutions! It's based on a bubble sort.

Spoiler

def mySort(n):
  for i in range(0, len(n)):
    for j in range(len(n)-1, i, -1):
      k = n.pop(j-1)
      n.insert(j-1, k)
      p = n.pop(j)
      n.insert(j, p)
      if k > p:
        swap = n.pop(j-1)
        n.insert(j+1, swap)
  return n

EDIT: Ahhh, beaten to the bubble by baavgai

This post has been edited by Simown: 02 September 2012 - 01:21 PM

[jon.kiparsky]

I've always had a soft spot for radix sort, which is perfect for this challenge:

Spoiler

def rsort(l):
	
	sort_key = 1
		
	sorted = False

	while  not sorted:
		
		sorted = True
		low = list()
		high = list()
				
		for i in l:
			if sort_key <= i:
				sorted = False
			if (i/sort_key) %2 == 0:
				low.append (i)
			else:
				high.append(i)

		l = low
		l.extend (high)

		sort_key *=2
		
	return l	

This is just a quick one bashed together, there's probably some improvements that could be made, but it seems to work for positive integers. Negative numbers, of course, would require some special attention.


EDIT: the special attention required for negative numbers turns out to be minimal. Revised code follows.

Spoiler

def rsort(l):
	
	sort_key = 1
	sorted = False


	while  not sorted:
		
		sorted = True
		low = list()
		high = list()
				
		for i in l:

			if sort_key <= abs(i):
				sorted = False
			if (i/sort_key) %2 == 0:
				low.append (i)
			else:
				high.append(i)

		l = low
		l.extend (high)

		sort_key *=2
		
	return l	


def do_sort(l):
	neg_list = [i for i in l if i <0]
	pos_list = [i for i in l if i >= 0]	
	l = rsort(neg_list)
	l.extend(rsort(pos_list))
	return l

This post has been edited by jon.kiparsky: 05 September 2012 - 09:25 PM

[Simown]

Only four days left to get your entry in! Make it count.

If you'd like to give it a go in another language, please do and post it here. I will only be timing Python entries for the challenge, however.

[sepp2k]

Simown, on 12 September 2012 - 08:50 PM, said:

If you'd like to give it a go in another language, please do and post it here.

Here's merge sort in Haskell:

Spoiler

mergeSort [] = []
mergeSort [x] = [x]
mergeSort list = merge (mergeSort firstHalf) (mergeSort secondHalf)
  where
    n = (length list) `div` 2
    firstHalf = take n list
    secondHalf = drop n list 

    merge list1 [] = list1
    merge [] list2 = list2
    merge (x:list1) (y:list2) =
      if x < y
      then x : merge list1 (y : list2)
      else y : merge (x : list1) list2

On second thought that might not count though because it uses take and drop, which correspond to list slices in Python.

So here's one without anything that could count as indexing:

Spoiler

mergeSort [] = []
mergeSort [x] = [x]
mergeSort list = merge (mergeSort firstHalf) (mergeSort secondHalf)
  where
    halve [] half1 half2 = (half1, half2)
    halve [x] half1 half2 = (x : half1, half2)
    halve (x:y:list) half1 half2 = halve list (x:half1) (y:half2)

    (firstHalf, secondHalf) = halve list [] []

    merge list1 [] = list1
    merge [] list2 = list2
    merge (x:list1) (y:list2) =
      if x < y
      then x : merge list1 (y : list2)
      else y : merge (x : list1) list2

[baavgai]

Had to have one more shot. Merge sort.

Spoiler

Merge sorts generally break everything down to build it back up. With python, we can start at the broken down stage. Lists make it way to easy, even without braces. No recursion is needed.

def mergeSort(nums):
	dat = list(list((n,)) for n in nums)
	while len(dat)>1:
		left, right = dat.pop(0), dat.pop(0)
		merged = list()
		while len(left)>0 and len(right)>0:
			lVal, rVal = left.pop(0), right.pop(0)
			if lVal < rVal:
				right.insert(0, rVal)
				merged.append(lVal)
			else:
				left.insert(0, lVal)
				merged.append(rVal)
		merged.extend(left)
		merged.extend(right)
		dat.append(merged)
	return dat.pop()

[sepp2k]

Here's another cheaty entry from me:

Spoiler

def cheaty_counting_sort(lst):
  minv = min(lst)
  maxv = max(lst)

  counts = list(0 for i in range(minv, maxv+1))

  def count_for(x):
    return counts.__getitem__(x - minv)

  def inc(x):
    counts.__setitem__(x - minv, count_for(x) + 1)

  for item in lst:
    inc(item)

  return list( x for x in range(minv, maxv + 1) for i in range(0, count_for(x)))

And here's a wrapper that picks this one or mergesort depending on the input data:

Spoiler

def mysort(lst):
  if max(lst) - min(lst) <= len(lst)*10:
    return cheaty_counting_sort(lst)
  else:
    return mergesort(lst)

[charles314]

Excuse my interest, but this link http://www.eeyogo.co...dom-sort-3.html has this -or similar contest. What is really going on(?).

And to further add, I used this search operator: https://www.google.c...&psj=1&bav=on.2,or.r_gc.r_pw.r_qf.&fp=ba9a35dc39c5822a&biw=1163&bih=828

Excuse me if I am wrong, but the matching of the wording was to close to be uncanny, I suppose.