BubbleSort incorrect sample answer?

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

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!

OK, I get 5 8 as needed.

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.

>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... :)

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);
    }
}

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!

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

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

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

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)))