# Sorting without Indices - Challenge!

• (3 Pages)
• 1
• 2
• 3

## 41 Replies - 12257 Views - Last Post: 17 September 2012 - 07:02 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=290729&amp;s=1e7134271fcc213b2d911dbf26546b37&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Simown

• Blue Sprat

Reputation: 321
• Posts: 650
• Joined: 20-May 10

# Sorting without Indices - Challenge!

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

• D.I.C Lover

Reputation: 2308
• Posts: 3,570
• 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?

### #3 Simown

• Blue Sprat

Reputation: 321
• 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

### #4 sepp2k

• D.I.C Lover

Reputation: 2308
• Posts: 3,570
• 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

### #5 Simown

• Blue Sprat

Reputation: 321
• 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.

### #6 sepp2k

• D.I.C Lover

Reputation: 2308
• Posts: 3,570
• Joined: 21-June 11

## Re: Sorting without Indices - Challenge!

Posted 02 September 2012 - 12:25 PM

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.

### #7 baavgai

• Dreaming Coder

Reputation: 6605
• Posts: 13,945
• 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

### #8 baavgai

• Dreaming Coder

Reputation: 6605
• Posts: 13,945
• 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

### #9 Simown

• Blue Sprat

Reputation: 321
• 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

### #10 jon.kiparsky

• Pancakes!

Reputation: 9537
• Posts: 16,482
• 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

### #11 Simown

• Blue Sprat

Reputation: 321
• 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.

### #12 sepp2k

• D.I.C Lover

Reputation: 2308
• Posts: 3,570
• Joined: 21-June 11

## Re: Sorting without Indices - Challenge!

Posted 12 September 2012 - 12:38 PM

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.

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

### #13 baavgai

• Dreaming Coder

Reputation: 6605
• Posts: 13,945
• 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

### #14 sepp2k

• D.I.C Lover

Reputation: 2308
• Posts: 3,570
• 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

### #15 charles314

Reputation: -11
• 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(?).