Sorting without Indices - Challenge!

  • (3 Pages)
  • +
  • 1
  • 2
  • 3

41 Replies - 10205 Views - Last Post: 17 September 2012 - 07:02 PM Rate Topic: -----

#1 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Sorting without Indices - Challenge!

Post icon  Posted 02 September 2012 - 08:35 AM

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


Is This A Good Question/Topic? 2
  • +

Replies To: Sorting without Indices - Challenge!

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 08:49 AM

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?
Was This Post Helpful? 0
  • +
  • -

#3 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 08:57 AM

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

Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 11:21 AM

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

Spoiler


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

Spoiler


Neither of them has been optimized for speed.

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

Was This Post Helpful? 1
  • +
  • -

#5 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 11:59 AM

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.
Was This Post Helpful? 0
  • +
  • -

#6 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 12:25 PM

View PostSimown, 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.
Was This Post Helpful? 0
  • +
  • -

#7 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5943
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 12:40 PM

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

Quite satisfying, actually.
Spoiler

Was This Post Helpful? 1
  • +
  • -

#8 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5943
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 01:17 PM

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

Was This Post Helpful? 0
  • +
  • -

#9 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 01:19 PM

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

Spoiler


EDIT: Ahhh, beaten to the bubble by baavgai

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

Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 8037
  • View blog
  • Posts: 13,757
  • Joined: 19-March 11

Re: Sorting without Indices - Challenge!

Posted 04 September 2012 - 08:24 PM

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

Spoiler



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

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

Was This Post Helpful? 1
  • +
  • -

#11 Simown  Icon User is offline

  • Blue Sprat
  • member icon

Reputation: 319
  • View blog
  • Posts: 650
  • Joined: 20-May 10

Re: Sorting without Indices - Challenge!

Posted 12 September 2012 - 11:50 AM

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.
Was This Post Helpful? 0
  • +
  • -

#12 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Sorting without Indices - Challenge!

Posted 12 September 2012 - 12:38 PM

View PostSimown, 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


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

Was This Post Helpful? 0
  • +
  • -

#13 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5943
  • View blog
  • Posts: 12,871
  • Joined: 16-October 07

Re: Sorting without Indices - Challenge!

Posted 13 September 2012 - 10:04 AM

Had to have one more shot. Merge sort.
Spoiler

Was This Post Helpful? 0
  • +
  • -

#14 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2153
  • View blog
  • Posts: 3,315
  • Joined: 21-June 11

Re: Sorting without Indices - Challenge!

Posted 14 September 2012 - 08:27 AM

Here's another cheaty entry from me:

Spoiler


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

Spoiler

Was This Post Helpful? 0
  • +
  • -

#15 charles314  Icon User is offline

  • New D.I.C Head

Reputation: -11
  • View blog
  • Posts: 18
  • Joined: 13-September 12

Re: Sorting without Indices - Challenge!

Posted 14 September 2012 - 07:44 PM

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.
Was This Post Helpful? 0
  • +
  • -

  • (3 Pages)
  • +
  • 1
  • 2
  • 3