0
#include <iostream>
#include <vector>
#include <random>
#include <ctime>
#include <algorithm>
using namespace std;
mt19937 Rand (random_device{}()+time(0));

// Cree las funciones de ordenamiento aqui:
void ordenar (vector<int>::iterator b, vector<int>::iterator e)
{
}

main() {
  vector<int> numeros;
  numeros.resize(10);
  iota(numeros.begin(), numeros.end(), 0);
  shuffle(numeros.begin(), numeros.end(), Rand );
  for (auto n : numeros) cout << n << " ";
  cout << endl << endl;
  // LLAME A LA FUNCION DE ORDENAMIENTO AQUI!!!
  ordenar(numeros.begin(),numeros.end());

  for (auto n : numeros) cout << n << " ";
  cout << endl;
}


//
2

1 respuesta 1

0

Supongo que tu pregunta es como se implementan estos algoritmos. Literalmente en el ejercicio será cambiar los valores de las funciones y poco mas. Aún así no se si será la respuesta que esperas pero...

Insertion Sort: Insertion sort, es un algoritmo que ordena una lista de valores escogiendo un siguiente valor y guardandolo en la lista de valores ya ordenados sin crear espacio adicional. A esto se le llama insertar el valor. Ejemplo:

    v

lista: 5 4 8 4 Al principio nuestro 'siguiente valor' es el primero de todos. Y siempre estará ordenado así que

      v

lista: 5 4 8 4 Nuestro siguiente valor, será el 4, y iremos mirando por cada uno de los valores ya ordenados si es mayor, menor o igual.

Si es mayor o igual el nuestro, implica que ya hemos encontrado su lugar, Si es menor, haremos un swap de ambas posiciones para seguir mirando donde colocarlo. El algoritmo seguiría estos pasos:

5 4 8 4 <-- el primer elemento esta ordenado

4 5 8 4 <-- el segundo elemento (el primer cuatro) ya esta ordenado

4 5 8 4 <-- idem

4 4 5 8 <-- idem

Merge Sort: Merge Sort, sigue la filosofia de dividir y vencer, suponemos que un problema grande y dificil de solucionar podemos dividirlo en subproblemas mas pequeños y llegar a una solucion del problema grande uniendo las soluciones de los pequeños. A este ultimo paso se le llama fusion (en ingles merge).

Ejemplo con la misma lista: 5 4 8 4 Tenemos la funcion mergesort que se llamará a si misma dos veces tal que: mergesort([5,4,8,4]){ mergesort([5,4]); mergesort([8,4]); } Y por cada uno de ellos de igual manera tambien llamaremos a la misma funcion dos veces dividiendo el problema hasta que solamente tengamos una lista de un elemento. Ahora bien, ordenar un solo elemento es sencillo, es solamente ese elemento. Pues cuando recursivamente volvamos a la funcion donde llamamos

mergesort([5]); mergesort([4]);

Habremos de crear una nueva función que usualmente se llama merge, tal que unirá las dos listas ordenadas, en una sola lista ordenada. Este algoritmo solamente recorre ambas listas y va cogiendo siempre el mínimo valor de cada una todo el rato para crear la lista ordenada y devolverla. El algoritmo de MergeSort siempre tiene esta forma:

mSort(L){ if(size(L) == 1) return L; pL = primeraMitad(L); sL = segundaMitad(L); pL = mSort(pL); sL = mSort(sL); reeturn merge(pl, sl); }

Ambas soluciones son efectivas en unos casos u otros. Los algoritmos dependen siempre de la entrada que se les proporciona, y ya no solo por su salida, si no por cuan eficientes pueden ser. Merge Sort suele ser siempre mas eficiente, pero solamente en temas de tiempo y cuando las listas son grandes porque Merge Sort utiliza espacio adicional, mientras que Insertion Sort no usa mas espacio que la lista proporcionada, pero en listas grandes es un tiempo mucho mayor al de Merge Sort.

Tiempos Asintóticos de los algoritmos:

Insertion Sort: O(n^2)

Merge Sort: O(nlogn)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.