#include <iostream>
#include <cstdint>
#include <vector>
#include <limits>
using namespace std;
bool Compare(const double &a, const double &b)
{
return a - b > 0.0;
}
void InsertionSort(vector<double> &vect)
{
for (size_t i = 1; i < vect.size(); ++i)
for (size_t j = i; j > 0 && Compare(vect[j], vect[j - 1]); --j)
swap(vect[j], vect[j - 1]);
}
int main()
{
vector <double> v = {1, 2, 3, 4, 5};
InsertionSort(v);
for (auto val : v)
cout << val << " ";
cout << endl;
double nan = numeric_limits<double>::quiet_NaN();
v = {1, nan, 2, nan, 1};
InsertionSort(v);
for (auto val : v)
cout << val << " ";
cout << endl;
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGludD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGxpbWl0cz4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmJvb2wgQ29tcGFyZShjb25zdCBkb3VibGUgJmEsIGNvbnN0IGRvdWJsZSAmYikKewoJcmV0dXJuIGEgLSBiID4gMC4wOwp9Cgp2b2lkIEluc2VydGlvblNvcnQodmVjdG9yPGRvdWJsZT4gJnZlY3QpCnsKCWZvciAoc2l6ZV90IGkgPSAxOyBpIDwgdmVjdC5zaXplKCk7ICsraSkKCQlmb3IgKHNpemVfdCBqID0gaTsgaiA+IDAgJiYgQ29tcGFyZSh2ZWN0W2pdLCB2ZWN0W2ogLSAxXSk7IC0taikKCQkJc3dhcCh2ZWN0W2pdLCB2ZWN0W2ogLSAxXSk7Cn0KCmludCBtYWluKCkgCnsKCXZlY3RvciA8ZG91YmxlPiB2ID0gezEsIDIsIDMsIDQsIDV9OwoJSW5zZXJ0aW9uU29ydCh2KTsKCWZvciAoYXV0byB2YWwgOiB2KQoJCWNvdXQgPDwgdmFsIDw8ICIgIjsKCWNvdXQgPDwgZW5kbDsKCQoJZG91YmxlIG5hbiA9IG51bWVyaWNfbGltaXRzPGRvdWJsZT46OnF1aWV0X05hTigpOwoJdiA9IHsxLCBuYW4sIDIsIG5hbiwgMX07CglJbnNlcnRpb25Tb3J0KHYpOwoJZm9yIChhdXRvIHZhbCA6IHYpCgkJY291dCA8PCB2YWwgPDwgIiAiOwoJY291dCA8PCBlbmRsOwoJCglyZXR1cm4gMDsKfQ==