Вы можете передать функцию обратного вызова общего типа вашей функции bubblesort и вызвать функцию через разумные промежутки времени.
Это будет влиять на производительность, но это не должно вызывать беспокойства, когда вы используете пузырьки в любом случае.
Сначала нужно некоторое включает в себя:
#include <iostream>
#include <vector>
#include <random>
#include <chrono>
, а затем функцию BubbleSort, которую я по существу взял из википедии: https://en.wikipedia.org/wiki/Bubble_sort#Optimizing_bubble_sort
template <typename T, typename Func>
void bubblesort(std::vector<T> &v, Func callback) {
size_t const len = v.size();
size_t n = v.size();
while(n > 0) {
size_t newn = 0;
for(size_t i = 1; i <= n-1; ++i) {
if (v[i - 1] > v[i]) {
std::swap(v[i-1], v[i]);
newn = i;
}
}
n = newn;
callback(100-static_cast<int>(n*100/len));
}
}
Мы будем называть данную функцию обратного вызова (или использование operator() на объект) всякий раз, когда выполняется сортировка в одном элементе.
Параметр, который мы передаем, представляет собой целочисленный процент от того, как далеко мы пришли. Обратите внимание, что из-за целочисленной арифметики вы не можете изменить порядок операций с n * 100/v.size(), иначе он всегда будет равен 0, так как n всегда будет меньше v.size();
using namespace std::chrono; //to avoid the horrible line becoming even longer
int main() {
std::vector<int> vec;
/* fill vector with some data */
std::mt19937 generator(static_cast<unsigned long>(duration_cast<milliseconds>(system_clock::now().time_since_epoch()).count())); //oh god
for(int i = 0; i < 100000; ++i) {
vec.push_back(static_cast<int>(generator()));
}
Для инициализации мы создаем генератор случайных чисел и засеваем его текущим временем. Затем мы помещаем некоторые элементы в вектор.
char const *prefix = "Bubble sort under progress. Done: ";
int lastp = -1;
bubblesort(vec, [&lastp,prefix](int p){
//if progress has changed, update it
if(p != lastp) {
lastp = p;
std::cout << "\r" << prefix << p << "%" << std::flush;
/*std::flush is needed when we don't start a new line
'\r' puts the cursor to the start of the line */
}
});
std::cout << "\r" << prefix << "100%" << std::endl;
//make sure we always end on 100% and end the line
}
Теперь основная часть: мы передаем функцию лямбда C++ для нашей функции bubblesort в качестве обратного вызова. Затем наша функция bubblesort вызовет эту лямбда с процентным значением и запишет ее на экран.
И вуаля, мы получили себя некоторый аккуратный выход:
https://youtu.be/iFGN8Wy9T3o
Заключительные ноты:
Вы, конечно, можете интегрировать функцию LAMDA в самой функции сортировки, но я бы не рекомендовал этот поскольку вы теряете большую гибкость. Но это выбор дизайна, который зависит от вас - если вам не нужна гибкость, просто переустановите его.
Процент не очень точный, ведь зная, что вы на 20% (и как долго это нужно, чтобы добраться туда), совсем не говорит о том, сколько времени потребуется, чтобы добраться до 100% вполне возможно, что последние 20% вектора были отсортированы (и, следовательно, быстро отсортировались с bubblesort - O (n)), но остальные 80% были случайными и берут O (n^2) для сортировки. На самом деле все это говорит вам, что вы добиваетесь прогресса, но это все, что вам нужно в первую очередь, поэтому я думаю, что все в порядке.
Если вы хотите получить более точный процент настроить программу так:
#include <iomanip>
/* ... */
callback(10000-static_cast<int>(n*10000/len));
/* ... */
std::cout.fill('0'); //to fill leading zero of p%100
std::cout << "\r" << prefix << p/100 << "." << std::setw(2) << p%100 << "%" << std::flush;
Если вы решили использовать значение с плавающей точкой, а не помнит, чтобы очистить остаточные символы из предыдущих выходов - «\ г» только сбрасывает курсор , но не очищает линию.
Используйте std::cout.precision(3); для фиксированной точности или напишите некоторые пробелы после сообщения, чтобы очистить предыдущие прогоны.
Проблема в том, что большинство компьютеров не просто запускают вашу программу. У них есть другие вещи, которые влияют на производительность, поэтому им придется сделать предположение. –
Время первого x% и экстраполировать. –
Как вы собираетесь рассчитать этот процент? Как только вы это определите, дисплей прост. Однако расчет не является чем-то простым. Учитывая 1000 пунктов, как ваш алгоритм сортировки знает, что он достиг 17% от своего рода, когда по своей природе сортировка пузырьков очень повторяется? –