Código
#include <iostream> #include <vector> using namespace std; // Pre: no tiene // Post: v contiene los elementos iniciales y ordenados crecientemente. void ordena_por_insercion(vector<double>& v) { // Inv: v[0..i-1] esta ordenat crecientemente for (int i = 1; i < v.size(); ++i) { double x = v[i]; int j = i; while (j > 0 and v[j - 1] > x) { v[j] = v[j - 1]; --j; } v[j] = x; } } int main() { int n; cin >> n; vector<double> v(n); for (int i = 0; i < n; ++i) cin >> v[i]; ordena_per_insercio(v); for (int i = 0; i < n; ++i) cout << v[i] << " "; cout << endl; }
Este algoritmo tiene coste = O(n^2) en el peor caso. Normalmente para estudiar la complegidad de los algorimtos tenemos en cuenta el peor, el mejor y el caso intermedio.