Блог

Я создал код, отвечающий за выполнение пузырьковой сортировки в списке. Кажется, что это работает, но для выполнения требуется много времени. Я был бы рад, если бы кто-нибудь сказал мне, что в этом не так, чтобы я мог избежать повторения той же ошибки в будущем

Подумал, что это может быть как-то связано с auto , но переписывание кода ничего не дало.

 void Sorting::bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
    int k = 0;
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i  )
    {
        for (auto j = std::next(start, 1); j != std::prev(stop, k); j  )
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
        k  ;
    }
}
  

Протестировано на 1000 элементах — 9032 с (измерено с помощью std:: chrono)

делать

 void bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
    std::list<int>::iterator k = stop;
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i  )
    {
        for (auto j = std::next(start, 1); j != k; j  )
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
        k--;
    }
}
  

чтобы не выполнять непрерывные перерасчеты std::prev(stop, k) все время, ваша программа делает почти только это

Конечно, список также не является лучшей коллекцией для хранения int и их сортировки

Полный пример :

 #include <list>
#include <iostream>
#include <chrono>
#include <ctime>

void bubblesort(std::list<int>::iterator start, std::list<int>::iterator stop)
{
#ifdef YOU
    int k = 0;
#else
    std::list<int>::iterator k = stop;
#endif
    int temp;
    std::list<int>::iterator j_1 ;
    for (auto i = start; i != stop; i  )
    {
        for (auto j = std::next(start, 1);
#ifdef YOU
             j != std::prev(stop, k);
#else
             j != k;
#endif
             j  )
        {
            j_1= std::prev(j, 1);
            if (*j_1 > *j)
            {
                temp = *j_1;
                *j_1 = *j;
                *j = temp;
            }
        }
#ifdef YOU
        k  ;
#else
        k--;
#endif
    }
}

int main()
{
  std::list<int> l;

  for (int i = 0; i != 1000;   i)
    l.push_front(i);

#ifdef DEBUG
  for (auto i : l)
    std::cout << i << ' ';
  std::cout << std::endl;
#endif


  std::chrono::time_point<std::chrono::system_clock> start, end;  

  start = std::chrono::system_clock::now();
  bubblesort(l.begin(), l.end());
  end = std::chrono::system_clock::now();
  std::cout << std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count() / 1000.0
    << " sec" << std::endl;

#ifdef DEBUG
  for (auto i : l)
    std::cout << i << ' ';
  std::cout << std::endl;
#endif
}
  

Компиляция и выполнение :

 pi@raspberrypi:/tmp $ g    b.cc
pi@raspberrypi:/tmp $ ./a.out
0.183 sec
pi@raspberrypi:/tmp $ g   -DYOU b.cc
pi@raspberrypi:/tmp $ ./a.out
3.98 sec
pi@raspberrypi:/tmp $ 
pi@raspberrypi:/tmp $ g   -O3 b.cc
pi@raspberrypi:/tmp $ ./a.out
0.004 sec
pi@raspberrypi:/tmp $ g   -O3 -DYOU b.cc
pi@raspberrypi:/tmp $ ./a.out
0.413 sec
  

Обратите также внимание на преимущество компиляции в O3 …

Это скорее дополнение к ответу Бруно, лучше попытаться отделить реализацию sort от реальных типов, например

 template <class InIt>
void bubblesort(InIt start, InIt stop)
{
    InIt k = stop, j_1;
    for (auto i = start; i != stop;   i)
    {
        for (auto j = std::next(start, 1); j != k;   j)
        {
            j_1 = std::prev(j, 1);
            if (*j_1 > *j)
            {
                /*auto temp = *j;
                *j = *j_1;
                *j_1 = temp;*/
                std::swap(*j,*j_1); 
                // - no real performance difference on GCC with -O2.
            }
        }
        --k;
    }
}