Hackerearth пузырьСортировка

В Hackerearth я пытался решить подсчет свопов пузырьковой сортировки. и мой вывод всегда отличается от правильного вывода. например;
мой вывод 2475, а правильный вывод 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;
}

Я делаю что-то не так или правильные выводы неверны?


algorithm counting swap bubble-sort counting-sort
person Yusuf Gündüz    schedule 06.11.2017    source источник
comment
Независимо от разницы в выводе, который вы получаете, поскольку вы используете C++, я настоятельно рекомендую использовать std::vector, а не необработанные массивы, и std::swap, а не создавать свои собственные. Это уменьшает площадь поверхности кода и потенциально может устранить любые незначительные ошибки, которые могут возникнуть здесь.   -  person templatetypedef    schedule 06.11.2017
comment
Добро пожаловать в StackOverflow. Пожалуйста, прочтите и следуйте инструкциям по публикации в справочной документации. Здесь применяется минимальный, полный, поддающийся проверке пример. Мы не сможем эффективно помочь вам, пока вы не опубликуете свой код MCVE и точно не опишите проблему. Мы должны иметь возможность вставить ваш опубликованный код в текстовый файл и воспроизвести проблему, которую вы описали. У вашей публикации есть две проблемы: (1) она требует ввода; (2) вы не предоставили тестовый пример. Жестко закодируйте кейс и завершите публикацию.   -  person Prune    schedule 06.11.2017

Ответы (2)


arrow_upward
0
arrow_downward

В логике обмена вместо A[j]=temp; пишем A[j+1]=temp;

Во внешнем цикле for i<tm-1 вместо i<tm

person venkata    schedule 06.11.2017

arrow_upward
0
arrow_downward

Может это и не важно, но можно найти число инверсии с большей сложностью. Это решение потребует O(n^2). Это можно сделать за время O(nlogn). Идея состоит в том, чтобы использовать сортировку слиянием, и в состоянии слияния вы уже знаете, сколько значений больше/меньше от значения, фактически не считая их. При слиянии, если значение правого подмассива больше, то все остальные значения справа от него также больше. Вам просто нужно подсчитать, сколько значений находятся справа. Подробное и приятное объяснение приведено здесь.

person dipal    schedule 06.11.2017