elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Security Series.XSS. [Cross Site Scripting]


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  ¿Cómo hallar una Permutacion ordenada con MergeSort?
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: ¿Cómo hallar una Permutacion ordenada con MergeSort?  (Leído 1,336 veces)
_TTFH_3500

Desconectado Desconectado

Mensajes: 123



Ver Perfil
¿Cómo hallar una Permutacion ordenada con MergeSort?
« en: 11 Octubre 2018, 01:12 am »

Dado un arreglo desordenado con n elementos, el siguiente código retorna una permutación tal que al aplicarla al arreglo original los elementos quedan ordenados.

Código
  1. #include <stdio.h>
  2.  
  3. typedef unsigned int uint;
  4.  
  5. void Swap(int &a, int &b) {
  6. int t = a;
  7. a = b;
  8. b = t;
  9. }
  10.  
  11. int* BubbleSort(const int* A, uint n) {
  12. int* P = new int[n];
  13. for (uint i = 0; i < n; i++)
  14. P[i] = i;
  15. bool ordenado;
  16. do {
  17. ordenado = true;
  18. for (uint i = 1; i < n; i++)
  19. if (A[P[i-1]] > A[P[i]]) {
  20. Swap(P[i-1], P[i]);
  21. ordenado = false;
  22. }
  23. } while (!ordenado);
  24. return P;
  25. }
  26.  
  27. int main() {
  28. uint n;
  29. printf("Ingrese la cantidad de numeros: ");
  30. scanf("%u", &n);
  31. printf("Ingrese los numeros:\n");
  32. int* A = new int[n];
  33. for (uint i = 0; i < n; i++)
  34. scanf("%d", &A[i]);
  35. int* P = BubbleSort(A, n);
  36. printf("Los numeros ordenados son:\n");
  37. for (uint i = 0; i < n; i++)
  38. printf("%d ", A[P[i]]);
  39. printf("\n");
  40. delete[] A;
  41. delete[] P;
  42. return 0;
  43. }

Pero lo hace en tiempo O(n^2), en cambio el siguiente codigo: https://www.geeksforgeeks.org/merge-sort/ retorna el arreglo ordenado en tiempo O(n log(n))
¿Cómo puedo modificar MergeSort para obtener una permutación ordenada en lugar de ordenar el propio arreglo?



En línea

CalgaryCorpus


Desconectado Desconectado

Mensajes: 323


Ver Perfil WWW
Re: ¿Cómo hallar una Permutacion ordenada con MergeSort?
« Respuesta #1 en: 11 Octubre 2018, 05:15 am »

Aplica la misma idea que muestras aquí, mantén un arreglo de índices y compara la desrefencia. Cuánto corresponda mover o intercambiar, lo haces en el arreglo de índices.


En línea

Aqui mi perfil en LinkedIn, invitame un cafe aqui
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
como hallar los subtitulos en una pelicula
Multimedia
ivanmoises 1 1,567 Último mensaje 26 Diciembre 2007, 14:54 pm
por Songoku
como hallar el Exe al que pertenece la ventana ??? « 1 2 »
Programación Visual Basic
<[(x)]> 17 5,377 Último mensaje 31 Diciembre 2008, 20:36 pm
por <[(x)]>
como puedo Hallar AcroSeno y ArcoCoseno ???
Programación Visual Basic
<[(x)]> 2 6,953 Último mensaje 28 Mayo 2009, 02:49 am
por <[(x)]>
problema con el mergesort
Programación C/C++
mapers 0 1,408 Último mensaje 22 Enero 2011, 09:26 am
por mapers
Como hacer el método de ordenamiento QuickSort y Mergesort para Listas Dinamicas
Programación C/C++
gibranini 1 5,759 Último mensaje 2 Julio 2014, 08:28 am
por eferion
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines