BubbleSort incorrect sample answer?

Back to General discussions forum

a_banderov     2014-08-01 14:03:25

Hello :) So I have just solved the Bubble Sort problem and the sample test data -

input data: 8 3 1 4 1 5 9 2 6

answer: 5 8

  • might have some incorrect answers. When I run my solution it gives me 6 and 12, not 5 and 8. My code seems to be correct, because I was given "problem solved" after submitting.
nicolas_patrois     2014-08-01 14:32:02
User avatar

My answers are 6 15 (if it is problem #27).

Rodion (admin)     2014-08-01 14:39:18
User avatar

To a_banderov: your code is correct but it performs swap of equal values - it swaps 1 and 1 on the two last passes :)

You can fix this unnecessary swap by changing >= to > inside if.

Your code gives correct results when submitted since test cases intentionally avoid equal numbers. :)


To nicolas_patrois: the first 8 is the number of values really, not the first element of an array. I guess lines get glued due to lack of formatting (hope I'll add "editing" features soon).

With array of 9 values including thi leading 8 the result is really 6 15 - you are correct about this!

a_banderov     2014-08-01 14:55:25

@ADMIN It really glued them together. I copy/pasted it straight from the problem and it was ok. Thank you for pointing out that minor mistake of mine.

nicolas_patrois     2014-08-01 15:10:08
User avatar

OK, I get 5 8 as needed.

Scaevola     2014-12-13 06:23:44

Hi there, I've finished the Bubble Sort, however my results for the example do not match (4 8). I'm sorting the array (making a pass) from right to left, might this have anything to do with it? Thanks!

Update: in case anyone asks, yes, the resultant array was sorted numerically from lowest to highest value starting at the zero index. Just the method was reverse, hoping to save a few cpu cycles. I switched it around to make a pass from left to right and my results now match... oh well, not as efficient but it moves me on.

Rodion (admin)     2014-12-13 09:26:46
User avatar

>I'm sorting the array (making a pass) from right to left, might this have anything to do with it?

Yes, I think you are pretty correct - results may be different depending on how you implement the algorithm.

Meanwhile test input data do not contain equal values (like two 1-s in example) so probably for that case both implementations will give the same answer.

Though all these consideration, of course have only theoretical value, as the exercise itself... :)

jayeshcp     2015-02-01 23:02:46

What is the problem this code, I get all results correct but it is not getting accepted as correct.

import java.util.*;

class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[] nums = new int[N];
        int numPasses = 0, numSwaps = 0;

        // Read inputs
        for(int i = 0; i < N; i++) {
            nums[i] = in.nextInt();
        }

        // Sort numbers
        boolean sorted = false;

        while(!sorted) {
            sorted = true;
            numPasses++;
            for(int i = 0; i < N - 1; i++) {
                if(nums[i] > nums[i + 1]) {
                    sorted = false;
                    numSwaps++;
                    int temp = nums[i];
                    nums[i] = nums[i + 1];
                    nums[i + 1] = temp;
                }
            }
        }


        // Output results
        System.out.println(numPasses + " " + numSwaps);
    }
}
Rodion (admin)     2015-02-02 05:56:46
User avatar

Hi!

That is strange. Your solution looks correct. Could you please post sample input data you are given, your answer and "expected answer" which the site tells you when it says about incorrect result? I hope we'll be able to research this mystery together!

jayeshcp     2015-02-02 21:39:22

Strange ! .. It accepted this time. Thanks Admin.

Mandeep Bhutani     2015-02-25 16:51:09

I'm also having a problem with counting the passes. The number of swaps comes out fine, but the number of passes returns the wrong number no matter where the counter is placed.

Here is the code:

num_input = int(raw_input("How many numbers?"))
data = map(int, raw_input("Please enter data:").split())
swaps = 0
passes = 0
for i in range(0, len(data) - 1):
    for j in range(0, len(data) - i - 1):
        while data[j] > data[j+1]:
            data[j], data[j+1] = data[j+1], data[j]
            swaps += 1
    passes += 1
print passes, swaps
Ashish Padalkar     2015-02-26 09:40:18
User avatar

If I am not wrong , I think you are have no mechanism to verify the third step of the algorithm provided

"Repeat such passes through array until the new pass will do no swaps at all."

you are running passes equal to length of data

Bharat Chaudhury     2016-05-31 13:44:44

not able to get the number of passes correctly. can anyone tell me the mistake am making ?

arr=[14,7,4,2,6,10,5,1,3,13,17,12,8,9,11,15,16,18] passes = 0 temp =0 swap_count=0 i=0 l=len(arr)

for passnum in range(len(arr)-1,0,-1) :

for i in range(passnum) :



    if arr[i] > arr[i+1] :
        print("sawp occured between %d and %d " %(arr[i],arr[i+1]))
        temp=arr[i]
        arr[i] = arr[i+1]
        arr[i+1] = temp
        swap_count=swap_count+1
        print(arr)

    else :

        print("NO sawp  between %d and %d " %(arr[i],arr[i+1]))
        print(arr)


    print("now i is %d" %i)
passes+=1

print("total swap is %s" %str(swap_count)+" "+"%s" %(str(passes)))

Please login and solve 5 problems to be able to post at forum