CODEWITHSUNDEEP
pythonpython-2.7bubble-sort
jted95
jted95

Reputation: 1144

Day 20: Sorting in Hackerrank, Python

recently I have been doing HackerRank 30 days of code challenge and solve the challenge using Python. However in day 20(about Bubble Sort algorithm) I cannot solve it. This is the link to the task in Hackerrank and below is my code.

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
numSwap = 0

for first in a:
    b = a[a.index(first)+1:]
    for second in b:
        if first > second:
            a[a.index(first)] = second
            a[a.index(second)] = first
            numSwap += 1

firstElement = a[0]
lastElement = a[len(a)-1]
print "Array is sorted in %d swaps\nFirst Element: %s\nLast Element: %d " %(numSwap, firstElement, lastElement)

The input for this code is:

3
3 2 1

The result of the code is:

Array is sorted in 3 swaps  
First Element: 3  
Last Element: 1

The expected result:

Array is sorted in 3 swaps.
First Element: 1
Last Element: 3

the question is why it did not work like expected? which part of the code is wrong? Thank you.

Upvotes: 0

Views: 2625

Answers (2)

jted95
jted95

Reputation: 1144

I finally know what is the mistake in my code.

for first in a:
    b = a[a.index(first)+1:]
    for second in b:
        if first > second:
            a[a.index(first)] = second
            a[a.index(second)] = first
            numSwap += 1

so these code below is swapping back the elements to its original place:

a[a.index(first)] = second
a[a.index(second)] = first

should have created a variable to contain one of the elements.

smaller = a.index(first)
bigger = a.index(second)
a[smaller] = second
a[bigger] = big

and my second mistake is the first for will not repeat the algorithm from the newly updated list causing the 2 as the first element.

the correct code is as written by TheDarkKnight.

Here's a solution that should work flawlessly:

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
# Write Your Code Here
numberOfSwaps = 0
for i in xrange(n):
    for j in xrange(n-1):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            numberOfSwaps += 1
    if not numberOfSwaps:
        break


print "Array is sorted in", numberOfSwaps, "swaps."
print "First Element:", a[0]
print "Last Element:", a[n-1]

Cheers :)

Upvotes: 0

Sreetam Das
Sreetam Das

Reputation: 3389

The problem with your code and the reason why it isn't working as expected is because:

for first in a:
b = a[a.index(first)+1:]
for second in b:
    if first > second:
        a[a.index(first)] = second
        a[a.index(second)] = first
        numSwap += 1

you are swapping the elements in the first array, a, but aren't updating the same in the second array, b.

Here's a solution that should work flawlessly:

import sys

n = int(raw_input().strip())
a = map(int, raw_input().strip().split(' '))
# Write Your Code Here
numberOfSwaps = 0
for i in xrange(n):
    for j in xrange(n-1):
        if a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            numberOfSwaps += 1
    if not numberOfSwaps:
        break


print "Array is sorted in", numberOfSwaps, "swaps."
print "First Element:", a[0]
print "Last Element:", a[n-1]

Cheers :)

Upvotes: 1

Related Questions