ayuda con ejercicio

Iniciado por ChristianThraash, 11 Julio 2016, 01:42 AM

0 Miembros y 1 Visitante están viendo este tema.

ChristianThraash

Hola me podrian ayudar a codificar este enunciado , no lo entiendo dice asi:

Implementar un método de ordenamiento algorítmico con código propio, donde dado un
conjunto de valores o vector, devuelva el conjunto ordenado, indicando cantidad de pasos
que debieron realizarse para hacerlo. Incluir en el documento una breve introducción a la
complejidad algorítmica y su relación con el algoritmo usado

+ 1 Oculto(s)

busca ordenamientos burbuja, quicksort, mergesort talves te puedan ayudar

LaiaxanIV

Puedes usar, por ejemplo, el algoritmo de ordenación por inserción.
Código (cpp) [Seleccionar]
#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.