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\$
  • 1
    \$\begingroup\$ Can you post a link to a reference implementation/description of bubble sort in your post? \$\endgroup\$ – mellamokb Feb 29 '12 at 18:59
  • \$\begingroup\$ I thought that everyone on CodeGolf.SE.com know that algorithm. \$\endgroup\$ – Hauleth Feb 29 '12 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\$ – Keith Randall Mar 1 '12 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 '12 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\$ – user unknown Mar 1 '12 at 23:40
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\$
  • \$\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\$ – ceased to turn counterclockwis Feb 29 '12 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 '12 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\$ – Steven Rumbalski Feb 29 '12 at 23:01
  • 1
    \$\begingroup\$ @StevenRumbalski: misleading title is misleading, then \$\endgroup\$ – Blazer Feb 29 '12 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\$ – ceased to turn counterclockwis Feb 29 '12 at 23:28
-1
\$\begingroup\$

I understand this :

input = unique positive integers in decreasing order so we have n,n-1,n-2.

And for output we want the minimum swap in order to get n - 999, n -998 for example.

So given to these informations we are always in the worst case of bubblesort. So answer is always n².

So let's do it in ruby. a is the according array.

def b(a) (a.size -1) * (a.size / 2) end

31 characters

\$\endgroup\$
  • \$\begingroup\$ No, the input is not always positive integers in decreasing order. That's just a worst-case scenario that your code should be able to handle. From the OP, "... are needed to sort (in increasing order) any array of unique positive integers." Keep trying, you have good thinking process, just solved the wrong problem :) \$\endgroup\$ – mellamokb Mar 13 '12 at 17:32

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.