0
\$\begingroup\$

Write shortest code that detect how many swaps (minimum) are needed to sort (in increasing order) any array of unique positive integers. It should be fast enough to detect number of swaps in array of 1'000'000 integers in decreasing order in 1-2 minutes.

Refs

Score

[time elapsed]s/60s * [length of code]
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can you post a link to a reference implementation/description of bubble sort in your post? \$\endgroup\$
    – mellamokb
    Feb 29, 2012 at 18:59
  • \$\begingroup\$ I thought that everyone on CodeGolf.SE.com know that algorithm. \$\endgroup\$
    – Hauleth
    Feb 29, 2012 at 19:04
  • 4
    \$\begingroup\$ I'm confused by "minimum" here. Bubble sort, as specified by the first pseudocode implementation on the Wikipedia page, is a well-specified algorithm which takes an unknown but fixed number of swaps given an input. What are we taking the minimum over? Or do you mean what is the minimum number of swaps needed, not doing the swaps in the order that standard bubble sort does them? \$\endgroup\$ Mar 1, 2012 at 3:16
  • 2
    \$\begingroup\$ @Hauleth: I don't doubt that, it's just good practice to include all details in a spec. It's also a little confusing that bubble sort is only mentioned in your title. Can you work it into your introductory paragraph as well? \$\endgroup\$
    – mellamokb
    Mar 1, 2012 at 13:31
  • 1
    \$\begingroup\$ Apart from small optimizations, the number of swaps for bubblesorting a given input should be constant, independent from the language. Sort 1M of values with bubblesort shouldn't be possible in 2 minutes on a nowadays customer PC/laptop/xPhone. Can you provide a reference code which solves the sorting in 2 Minutes? I vote to close. \$\endgroup\$ Mar 1, 2012 at 23:40

1 Answer 1

1
\$\begingroup\$

Python - 262 chars * 45 / 60 = 196.5

Edit: much faster sorting algorithm.

First it will sort all the items in the list by what hundred they are in (0, 100, 200, etc), in a list in m (note: I count these as 1 step each, so a list of 1,000,000 items will automatically have 1,000,000 steps initially)

Then it will sort the lists within m using the bubble sorting function c

This is greatly sped up from using c on the original list to be sorted, because the amount of time it takes to sort 1000 items is small (~0.04 seconds), but exponentially increases the larger the list gets (~45 seconds at 10,000 items). But if you sort 100 lists of 100 items, it only takes .4 seconds, to sort, more than 100 times faster than sorting 1 list of 10,000 items. It should therefor take 4 seconds to sort 100,000 items, and 40 seconds to finally sort 1,000,000

In actuality, it took 45 seconds to sort the reversed 1,000,000 item list this way, and results in 50,500,000 steps:

python bubblesortcount.py
50500000
44.6600000858

This functon works with the given case (reverse ordered list), as well as any random case. No negative integers, though.

r=range
def b(l):
 m=[[]for i in r(len(l)//100+1)];t=[];o=0
 for e in l:m[e//100].append(e);o+=1
 for e in m:x=c(e);t+=x[0];o+=x[1]
 return t,o
def c(l):
 s=0
 for p in r(len(l)-1,0,-1):
  for i in r(p):
   if l[i]>l[i+1]:l[i],l[i+1]=l[i+1],l[i];s+=1
 return l,s

test:

import random,time
a=time.time()
d=b(range(1000000)[::-1]) #reversed list
#d=b(random.sample(range(1000000),1000000)) #scrambled list
z=(time.time()-a)
#print d[0] # comment to not print a gigantic list
print d[1] # number of steps
print z # time it took

Edit: by changing the amount the helper function sorts by to 100, I reduced the average time it takes to sort the list to 45 seconds. also reduces character count by 2

edit again: you know what? maybe what I'm doing isn't valid. I can change the amount the helper function sorts by to just 1 and it will sort a million items in 5 seconds.. is this valid?

\$\endgroup\$
8
  • \$\begingroup\$ Well, of course it's too slow if you actually implement Bubblesort (this being an O (n ²) algorithm)! That's the interesting thing about this challenge. \$\endgroup\$ Feb 29, 2012 at 22:38
  • \$\begingroup\$ I suppose that the speed in which the code runs all depends on the machine it's being run on as well. my wimpy dualcore 1.83ghz laptop processor isn't quite up to speed to recent quad-core, 3.3 ghz technology (though I am building a spankin' new desktop soon, just not soon enough) \$\endgroup\$
    – Blazer
    Feb 29, 2012 at 22:45
  • \$\begingroup\$ The challenge doesn't seem to necessarily be to implement bubble sort, but to report the number of swaps needed. \$\endgroup\$ Feb 29, 2012 at 23:01
  • 1
    \$\begingroup\$ @StevenRumbalski: misleading title is misleading, then \$\endgroup\$
    – Blazer
    Feb 29, 2012 at 23:05
  • \$\begingroup\$ @Blazer: hardware is hardly significant compared to algorithm complexity when you're dealing with data blocks in the order of magnitude of millions, as well as language performance (otherwise you clearly shouldn't be using Python: you're program re-written in C and compiled with a decent compiler with -O2, run on your Laptop, would almost certainly outperform your code as simply run through the python interpreter on a state-of-the-art PC with an eight-core i7 processor). \$\endgroup\$ Feb 29, 2012 at 23:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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