Algoritmo de ordenamiento?

Iniciado por t4r0x, 11 Agosto 2013, 04:38 AM

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

t4r0x

Hola, quiero saber si alguien sabe algun algoritmo de ordenacion que pueda restaurar
el orden original de una cadena, por ejemplo tengo esta cadena:
"EDWKLAAQDFF"
El algoritmo la ordenara asi:
"AADDEFFKLQW"

De forma alfabetica, y que despues pueda restaurar a como este estaba
El algoritmo de burbuja pueda que funcione pero no encuentro una forma para
mantener la forma original de la cadena , asi que me preguntaba si existen algortimos
que trabajen asi y como se llaman para poder buscar informacion y poder programar uno. gracias!

za.asi

Podrias almacenar los canvios que hagas en el orden original en un vector para despues consultarlo y reordenar los caracteres

eferion

pues a ver... tienes qSort en la stl... algoritmo de burbuja, por selección, por inserción, por mezcla, por cuentas, mediante arbol binario...

Opciones hay muchas... para más detalles de cada una mira por internet... explicar todos y cada uno de ellos puede llevar bastante tiempo.


Alien-Z

Ten en cuenta que no todos los métodos que te ha comentado eferion sirven para lo mismo, es decir, ¿podrías usar cualquiera de esos algoritmos para ordenar tu cadena? SI; ¿Es igual de eficiente? NO, cada uno sirve para un caso distinto; deberías leer al menos una descripción para saber cuál utilizar en cada aplicación.

t4r0x

Bueno si conozco los algoritmos basicos como el de burbuja , esos algoritmos estan
bien y ordenan como yo quiero pero mi problema principal es que quiero saber
una manera al menos un poco eficiente de saber como restaurar estas cadenas
a su forma original, y en realidad no se de que forma buscar en internet, por
algoritmos de ordenacion encuentro bastantes pero ninguno habla de restaurar
el estado original ese tipo de informacion necesito gracias

crksergio

Si quieres volverlas a su forma original, por qué no guardar las ordenadas en un nuevo arreglo, así las originales quedan intactas?

ivancea96

¿A qué te refieres con forma original? Un algoritmo de ordenamiento básico, como el "Burbuja", ordenaría eso eficientemente. Porque, te refieres a ordenar las letras de "mayor a menor" ¿no?

rir3760

Cita de: t4r0x en 12 Agosto 2013, 03:11 AMconozco los algoritmos basicos como el de burbuja , esos algoritmos estan bien y ordenan como yo quiero pero mi problema principal es que quiero saber una manera al menos un poco eficiente de saber como restaurar estas cadenas a su forma original
Lo primero que debes indicar es el lenguaje de programación que estas utilizando. Y, como ya te comentaron, los algoritmos de ordenacion solo hacen eso: ordenan.

Para realizar la operación que mencionas debes utilizar (en el caso de C) un array adicional. Este lo utilizas para almacenar los indices de (o también punteros a) cada uno de los elementos del array de valores.

Es el array de indices (o punteros) el que se ordena. Después si quieres acceder a los valores en orden accedes a ellos indirectamente mediante el array de soporte (indices o punteros).

Por ejemplo supongamos que el array de valores es:
V[0] == C
V[1] == B
V[2] == A
V[3] == E
V[4] == D


El array de indices lo inicializas con el indice del primer elemento, segundo, etc., de esta forma:
NDX[0] == 0
NDX[1] == 1
NDX[2] == 2
NDX[3] == 3
NDX[4] == 4


Y una vez ordenado el array de indices este termina así:
NDX[0] == 2
NDX[1] == 1
NDX[2] == 0
NDX[3] == 4
NDX[4] == 3

Indicando que, para imprimir en orden el array de valores, se deben imprimir los elementos con indices 2, 1, 0, 4 y 3. Un programa de ejemplo:
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
   char v[5]  = {'C', 'B', 'A', 'E', 'D'};
   int ndx[5] = {0, 1, 2, 3, 4};
   int i;
   int j;
   int aux;
   
   /* Ordenacion de los indices mediante BubbleSort */
   for (i = 4; i > 0; i--)
      for (j = 0; j < i; j++)
         if (v[ndx[j]] > v[ndx[j + 1]]){
            aux = ndx[j];
            ndx[j] = ndx[j + 1];
            ndx[j + 1] = aux;
         }
   
   /* Valores segun su posicion */
   for (i = 0; i < 5; i++)
      printf("%3c", v[i]);
   putchar('\n');
   
   /* Valores segun el orden indicado por el array de indices */
   for (i = 0; i < 5; i++)
      printf("%3c", v[ndx[i]]);
   putchar('\n');
   
   return EXIT_SUCCESS;
}


Un saludo
C retains the basic philosophy that programmers know what they are doing; it only requires that they state their intentions explicitly.
--
Kernighan & Ritchie, The C programming language

eferion

Cita de: t4r0x en 12 Agosto 2013, 03:11 AM
Bueno si conozco los algoritmos basicos como el de burbuja , esos algoritmos estan
bien y ordenan como yo quiero pero mi problema principal es que quiero saber
una manera al menos un poco eficiente de saber como restaurar estas cadenas
a su forma original, y en realidad no se de que forma buscar en internet, por
algoritmos de ordenacion encuentro bastantes pero ninguno habla de restaurar
el estado original ese tipo de informacion necesito gracias


A no ser que guardes el original o mapees los resultados ( es decir, que guardes la posición que tenía cada cadena en su posición original ) te va a ser imposible restaurar la información.

Tu imagínate que tiras 6 dados... después los ordenas de menor a mayor... se te ocurre alguna forma humanamente posible de, viendo la secuencia ordenada, deducir la posición original de cada uno ?? no, verdad ?? pues eso.