2
\$\begingroup\$

I wrote a program for this problem, but it stopped because it took too much time. Any tips?

The Problem: Bubble sort is the simplest algorithm for elements sorting. At each iteration we sequentially compare values of subsequent elements and swap them if necessary.

Your job is to write a program which finds a state of a given list of positive integer numbers after applying a given count of bubble sort iterations

Input Sample: Each line contains a space-separated list of positive integers and ends with a number of iterations, separated by vertical line ‘|’. Example:

48 51 5 61 18 | 2

Output Sample:

5 48 18 51 61

Explanation:

Iteration 1: 48 5 51 18 61

Iteration 2: 5 48 18 51 61

My code:

def bubsort(num, iters):
    itered = 1
    while itered != iters + 1:
        nums = sorting(num)
        itered += 1
    print ' '.join(num)

def sorting(num):
    for i in xrange(len(num) - 1):
        challenger = int(num[i])
        opponent = int(num[i + 1])
        if challenger > opponent:
            num[i], num[i + 1] = num[i + 1], num[i]
    return num

test = raw_input()
whole = test.strip().split(' | ')
num = whole[0].split()
iters = int(whole[1])
bubsort(num, iters)
\$\endgroup\$
2
\$\begingroup\$

Three improvements:

  • Use the for loop idiom instead of a counter and use _ for variables you don't use.

  • return the result, don't print it, you should separate processing and output.

  • Use nums, not num because you should sort multiple numbers, a plural is a more sensible choice.

def bubsort(nums, iters):
    for _ in xrange(iters):
        nums = sorting(nums)
    return nums
\$\endgroup\$
1
\$\begingroup\$

In addition to what Caridorc said, move the integer casting outside your sorting function (this will also make your code a tiny bit more efficient):

def sorting(nums):
    for i in xrange(len(nums) - 1):
        if nums[i] > nums[i + 1]:
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
    return nums

And later use a list comprehension to convert the strings to numbers:

test = raw_input()
whole = test.strip().split(' | ')
num = [int(x) for x in whole[0].split()]
iters = int(whole[1])
bubsort(num, iters)

It should also be noted that .strip() isn't really needed, since int(" 2 ") == 2, but it doesn't hurt to have it there, either.

\$\endgroup\$

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.