Hackerearth bubbleSort

Question

In Hackerearth i tried solving bubble sort swap counting. and my output always different from correct output.for example;
my output is 2475 and correct output is 2788

#include <iostream>
using namespace std;


int main()
{
int *A,tm,times=0;
cin >> tm;
A = new int[tm];
for(int i = 0; i<tm;i++) {cin >> A[i];}

int temp;

for(int i = 0; i<tm;i++){
    for(int j = 0; j < tm-i-1;j++){
        if(A[j] > A[j+1]){
            times++;;
            temp = A[j];
            A[j] = A[j+1];
            A[j] = temp;
        }
    }
}
cout << times;

return 0;
}

Am i doing something wrong or correct outputs are wrong?

Independently of the difference in output you’re getting, since you’re using C++ I would strongly advise using std::vector rather than raw arrays and std::swap versus rolling your own. That reduces the surface area of the code and could potentially eliminate any minor bugs you might have here. — templatetypedef, Nov 06 '17 at 17:27
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. We cannot effectively help you until you post your MCVE code and accurately describe the problem. We should be able to paste your posted code into a text file and reproduce the problem you described. Your posting has two problems: (1) it requires input; (2) you haven't provided the test case. Hard-code the case and finish the posting. — Prune, Nov 06 '17 at 17:30

score 1 · Accepted Answer · answered Nov 06 '17 at 17:30

1

In the swap logic, in place of A[j]=temp; write A[j+1]=temp;

In the outer for loop, i<tm-1 instead of i<tm

answered Nov 06 '17 at 17:30

venkata

447
3
15

score 0 · Answer 2 · answered Nov 06 '17 at 22:39

May be this is irrelevant, but it is possible to find the number of inversion with a better complexity. This solution will require O(n^2). It can be done in O(nlogn) time complexity. The idea is to use merge sort and at merging state you already know how many values are greater/smaller from a value without actually counting them. While merging, if a value of right subarray is greater, then all other values right of it are also greater. You just need to count how many values are at right. A detailed and pleasant explanation is provided here.

Hackerearth bubbleSort

2 Answers2