Last chance

Hoy vamos a hablar de las listas enlazadas,

psssssssst!: si vez códigos que necesitas y no quieres estar transcribiendo porque solo dejare imágenes, en la parte de abajo puedes encontrar el link para descargar todo :)

¿QUE ES UNA LISTA ENLAZADA?

Una lista enlazada es un tipo de estructura de datos ( o una estructura que almacena datos ) que consta de nodos ( se podría decir que es una colección de nodos ) y enlaces a otros nodos.

Dichos nodos pueden estar en cualquier parte de la memoria.

Una lista enlazada es una muy buena opción si deseas guardar varios valores y no sabes cuanto espacio pueda tomar a comparación de un array [Próximamente te dejare un link para que averigües que es un array ]

LISTAS ENLAZADAS VS. ARRAYS

Es necesario saber el tamaño del array al momento de compilar el código. [ First Blood ]

Al momento de reservar memoria para el array tiene que tomar memoria consecutiva o a la misma distancia en cambio con una lista enlazada gracias por el uso de los punteros podemos tomar memoria disponible en cualquier parte de la memoria. [ Este es el momento en donde las listas enlazadas ganan esta pelea esto es un Double kill]

AHORA EMPECEMOS….

¿QUE ES UN NODO Y COMO SE DECLARA ? ( C++ )

Si te das cuenta nombre a la clase INTNODE porque de la forma en que la declare solo funciona con variables enteras (int) , si se quisiera generalizar se podría poner un template.

Se declara una variable entera que la llamaremos info que almacenara todos los datos que queramos almacenar, y luego declaramos un puntero next del tipo IntNode ( si, es un puntero del mismo tipo que la clase porque el siguiente dato que quieras almacenar sera otro nodo ) [LOS DECLARE AL ULTIMO] .

Empezamos con la primera función sin parámetros IntNode de la cual posee el puntero next el cual tendrá el valor de cero osea que este puntero seria un puntero nulo o que apunta al vació o para ser más claros no apunta a nada todavía.

EL siguiente IntNode que posee parámetros es solo para guardar valores como vemos en el parámetro tenemos una variables entera i la cual guardara el valor de info que sera el valor que nosotros queramos guardar en el nodo del misma manera sucede con el puntero in.

¿QUE PUEDO CONSTRUIR CON ESTO?

Bueno ya tenemos el nodo que es lo básico para una estructura de datos, luego de esto podemos crear estructuras como:

Lista enlazada Simple
Lista doblemente enlazada
Lista circular
Lista circular doblemente enlazada
etc etc etc.

En el siguiente post veremos como construir cada una o algo así

LINKS PARA DESCARGAR TODOS LOS CÓDIGOS QUE VISTE ( Made with love! )

Nodo: http://adf.ly/1Q51tH

¿Que es un algoritmo?

Es un conjunto de "instrucciones-pasos ordenados" previamente establecidos por el cual permite realizar optima mente la resolución de cierto problema.

Si como yo a la primera no la entendiste, HEY! te dejo un ejemplo:
x+1 --> es un algoritmo la x representa una variable que puede ser sustituida por cualquier numero , simple pero claro.

Algo más simple seria una receta de cocina, las instrucciones como instalar algún programa, como armar un árbol de navidad, etc...

Ordenación

También conocido como Sort en ingles , es cuando se dispone de una estructura-lista-vector de elementos en algún tipo de orden dependiendo de las instrucciones que se les de y de la forma en que se desee expresar .

tan tan tan...

Algoritmos de Ordenación

Si mezclamos un algoritmo con ordenación , creo que los más lógico seria conjunto de instrucciones para el ordenamiento de una estructura de datos previamente establecida con la finalidad de proyectar el resultado en algún tipo de orden .

READY OR NOT, HERE WE GO!

Existen varios algoritmos de ordenación pero...¿Cual de todos tengo que utilizar o Cual es mejor? Todo el peso de esta pregunta recae en la eficiencia - este mide la calidad y rendimiento del algoritmo- Hay que tener cuidado en el tiempo de ejecución no siempre los algoritmos de ordenación tardaran en el mismo tiempo, en algunos tomara más tiempo que en otros y viceversa en otros sera mucho más rápido, todo esto depende de la estructura del algoritmo.
Hay muchas formas de poder implementar estos algoritmos hasta se pueden mejorar dependiendo claro de la forma de implementación y claro en el lenguaje en que se desarrolle ( por ahora los desarrollare en c++, más adelante tratare de hacerlos en otros lenguajes ) , en algunos lenguajes se pueden realizar funciones que en otros no, esto aveces resulta un gran alivio y en algunos un gran tormento.

COMENCEMOS :

* Cuando estaba en clase mi profesor nos proyecto unos vídeos luego de la explicación de cada algoritmo para tener más clara la idea de como funciona el algoritmo, al principio fue gracioso porque aparecen personas bailando ( en serio , cada uno tiene un numero pegado en el pecho y con danzas típicas empiezan a ordenarse según el algoritmo) pero luego de verlo y dejando a un lado la distracción de la música y los pasos de baile comprendes como hacer la implementan y su funcionamiento , es una lastima que no hayan echo más ... pero bueno en los que hayan disponibles añadiré el link correspondiente - THANKS !
**Buscando en internet hay muchas explicaciones ( algunos en muy difícil de entender , parece nivel Hard+1) lo explicare de la forma más sencilla que encuentre

1.BUBBLE SORT

Como su nombre lo dice ( Bubble = burbuja) tomaremos el ejemplo del vídeo de AlgoRythmics -si desean omitir la parte del baile adelante el video hasta el segundo 0:51 -

Tenemos el arreglo-vector-estructura como deseen llamarlo :

3 0 1 8 7 2 5 4 6 9
( pensemos de esta manera : si lo ordenamos de menor a mayor , los valores pequeños subirán hasta el principio del array (array = arreglo) como las burbuja ascienden a la superficie por tener poco peso y los valores mayores se irán hasta el fondo de array )

Tenemos en cuenta de que n < m ; n tiene que ser menor que m .
Caso contrario cambiamos posiciones de n,m por m,n , de esta manera si cumpliría m < n y seguir avanzando hasta el final del array.

y empieza el baile .....

1.- 3 0 1 8 7 2 5 4 6 9

Intercambiamos el lugar del 3 y 0, ya que no se cumple que 3 < 0

2.- 0 3 1 8 7 2 5 4 6 9

Intercambiamos el lugar del 3 y 1, ya que no se cumple que 3 < 1

3.- 0 1 3 8 7 2 5 4 6 9

interc.... OH en este si cumplía YEI! dejamos el 3 y el 8 en sus lugares ya que este si cumple 3 < 8

4.- 0 1 3 8 7 2 5 4 6 9

Intercambiamos el lugar del 8 y 7, ya que no se cumple que 8 < 7.

5.- 0 1 3 7 8 2 5 4 6 9

Intercambiamos el lugar del 8 y 2, ya que no se cumple que 8 < 2.

6.- 0 1 3 7    2 8 5 4 6 9

Intercambiamos el lugar del 8 y 5, ya que no se cumple que 8 < 5.

//Apartir de aqui creo que ya quedo claro como se hace la comparación y solo pondré el array

7.-     0 1 3 7    2 5 8 4 6 9

8.-       0 1 3 7    2 5 4 8 6 9

9.-       0 1 3 7    2 5 4 6 8 9

Este si cumple con la propiedad así que lo dejamos en sus posiciones 8 y 9

//Volvemos a la posición inicial a seguir comprando
//El 8 y 9 están ya ordenados por eso los sombreamos de azul
10.- 0 1 3 7    2 5 4 6 8 9

11.- 0 1 3 7 2 5 4 6 8 9

12.- 0 1 3 7 2 5 4 6 8 9

13.- 0 1 3 7 2 5 4 6 8 9

14.- 0 1 3 7 2 5 4 6 8 9

15.- 0 1 3 2 7 5 4 6 8 9

16.- 0 1 3 2 5 7 4 6 8 9

17.- 0 1 3 2 5 4 7 6 8 9

//Volvemos a la posición inicial a seguir comprando
//El 7 están ya ordenados por eso los sombreamos de azul

18.- 0 1 3 2    5    4   6    7    8 9

19.- 0 1 3 2    5    4   6    7    8 9

20.- 0 1 3 2    5    4   6    7    8 9

21.- 0 1 3 2    5    4   6    7    8 9

22.- 0 1 2 3    5    4   6    7    8 9

23.- 0 1 2 3    5    4   6    7    8 9

24.- 0 1 2 3    4   5 6    7    8 9

25.- 0 1 2 3    4   5 6    7    8 9

Nuestro array esta ordenado , como la condición ya no se cumple, se sabe de que el array fue ordenado de forma exitosa

La implementación en c++ :

void bubble(int *A, cons int n)
{
for ( int i=0 ; i<n-1 ; ++i)
{
if ( A[ i ] > A[ i+1 ] )
swap( A[ i ], A[ i+1 ]) ;
}
}

Explicación de la implementación en c++ :

Primero definimos el tipo de función para nuestro algoritmo de ordenación , el nombre y los parámetros, en este caso definimos un puntero dinámico y una variable constante entera osea que durante el momento que el código pase por el compilador el valor asignado a n no va a cambiar.
En el for declaramos la variable i la cual se le asigna el valor de cero , luego implementamos la condición para que el for pueda seguir ejecutándose i<n-1; y por ultimo tenemos el incremento la diferencia del i++ y el ++i esta en que el i tiene ya un valor asignado y depende de la posición del ++ como se ejecute en el i++ primer se le asigna el valor y luego hace el incremento , por el otro lado el ++i notemos que el ++ esta antes esto implica de que todavía no se le asigno ningún valor y luego le indicamos el valor osea que luego de que termine el proceso recién incrementara el valor de i, en cambio el i++ primero se incrementa antes de empezar el proceso.
Hacemos la comparación si el elemento en el array en la posición i es mayor al elemento del array que esta en la posición i+1 procedemos a hacer el cambio de asignación posiciones de los valores con el swap cambiando y hacemos que el valor menor este antes que el valor mayor.

2.INSERT SORT

Como su nombre lo dice ( Insert = insertar ) tomaremos el ejemplo del vídeo de AlgoRythmics -si desean omitir la parte del baile adelante el vídeo hasta el segundo 0:14 -

Tenemos el arreglo-vector-estructura como deseen llamarlo :

3 0 1 8 7 2 5 4 9 6

( pensemos de esta manera : pensemos que son objetos un ejemplo unas velas, cada uno de ellos tiene una estatura determinada y tienes que ordenarlos por tamaño , se te dan las velas en orden aleatorio; tomas el primera vela ( vela1 = 3 ) la insertas el la primera posición ( A[0] ), luego tomas cualquier otra vela y nos percatamos que es mas grande que la primera que ya teníamos ordenada (vela2 = 7) así que esta tomaría la posición siguiente ( A[1]) ), luego de esto tomamos otra vela ( vela3 = 5) esta vela tiene un valor el cual es mayor que la primera vela y menor que la segunda así que se procede a insertar entre los dos valores asi que la primera vela se queda en su lugar (vela1 = 3 estará en A[0] ), la segunda vela que teníamos pasara a una tercera posición ya que solo la desplazaríamos ( vela2 = 7 esta ahora en A[2] ) y la vela que insertamos en la posición entre las dos velas que teníamos ( vela3 = 5 ahora esta en A[1]) y asi continuamente dependiendo de los valores y se insertaran para poder ordenarlos )

piensa que tenemos dos indices funcionando al mismo tiempo el primero lo llamaremos i y al segundo j , el propósito de tener 2 indices es que al ser el primero en entrar al arreglo sera como un alto a un intervalo que tenemos que ordenar de nuestro pequeño fragmento de arreglo y cuando este ordenado ese fragmento el i avanzara 1 posición el j se situara en la posicion de i y empezara a ordenarlo

y empieza el baile .....

1.- 3 0 1 8 7 2 5 4 9 6
j i

i y j se encuentran en la misma posición (Array[1]) que le corresponde en el valor de 0 , ahorremos un poco de tiempo porque no tendría sentido que empecemos en la posición Array[0] ¿porque ordenar a un elemento? es absurdo ... porque no puedes comparar con otro elemento porque no haya nada antes que el, ya esta ordenado , por eso empezamos desde la posición Array[1].
Al elemento en la posición i lo sombreamos de rojo porque sera nuestro pare hasta que los elementos que estén antes que el sean ordenados y j recorrerá todos los elemento que estén antes  que el para ordenarlos.
Nos topamos de que A [ j ] < A [ j - 1 ], es decir => A[ 1 ] < A[ 0 ] , en otras palabras => 0 < 3 y como si cumple esta propiedad , hacemos el cambio de elementos que se encuentran en esas posiciones

2.-      0   3   1 8 7 2 5 4 9 6
j i

El indice de j decrece en 1 posición y como no tiene nada más que comprar el i aumenta 1 y el j se iguala con el

3.-      0   3   1 8 7 2 5 4 9 6
j i

Y hacemos la comparación A[ 2]<A[1] así que hacemos el cambio pero recordando de que el elemento es el que cambian no los indices, j decrece una posición

4.-   0 1   3 8 7 2 5 4 9 6
j i

En este caso no cumple la propiedad porque A [ j ] < A[ j - 1 ] => 1 < 0 no es cierto, así de que no se efectúa ningún cambio de los elementos en las posiciones asignadas, pero de igual manera j decrece una posición.

5.-   0 1   3 8 7 2 5 4 9 6
j i

J llego al principio de Array así que ya no tiene nada con que comparar , así que ese fragmento ya esta ordenado y luego i incrementa 1 posición .

6.-      0 1   3 8 7 2 5 4 9 6
j i

Los indices i y j se encuentran en la posición Array [ 3 ], compráramos que la condición no se cumple con el elemento que se encuentra en la posición anterior a el así que no efectúa ningún cambio de posición de elemento .

7.-      0 1   3 8 7 2 5 4 9 6
j i

Vemos de que el elemento de el indice j no cumple la condición , así que no se efectúa ningún cambio y j decrece una posición

8.-      0 1   3 8 7 2 5 4 9 6
j i

El elemento del indice j no cumple la condición así de que , no se efectúa cambio alguno y j vuelve a decrecer una posición.

9.-      0 1   3 8 7 2 5 4 9 6
j i
El elemento del indice j ya no tiene con otro elemento que comprarse, así de que se sabe que ese fragmento del Array esta ordenado y el indice i incrementa 1 posición

//Apartir de aqui creo que ya quedo claro como se hace la comparación y solo pondré el array

10.-   0 1   3 8 7 2 5 4 9 6
j i

11.-   0 1   3 7 8 2 5 4 9 6
j i

12.-   0 1   3 7 8 2 5 4 9 6
j i

13.-   0 1   3 7 8   2 5 4 9 6
j    i

14.-   0 1   3 7 8   2 5 4 9 6
j i

15.-   0 1   3 7 8   2 5 4 9 6
j i

16.-     0 1   3 7 2 8   5 4 9 6
j i

17.-     0 1   3 2 7   8   5 4 9 6
j i

18.-     0 1   2 3 7   8   5 4 9 6
j i

19.-     0 1   2   3 7   8   5 4 9 6
j i

20.- 0 1 2 3 7 8 5 4 9 6
j i

21.- 0 1 2 3 7 8 5 4 9 6
j i

22.- 0 1 2 3 7 5 8 4 9 6
j i

23.-     0   1   2   3 5   7   8   4 9 6
j i

24.-     0   1   2   3 5   7   8   4 9 6
j i

25.-     0   1   2   3 5   7   8   4 9 6
j i

26.-     0   1   2   3 5   7   8   4 9 6
j i

27.-     0   1   2   3 5   7   8   4 9 6
j i

28.-     0   1   2   3 5   7   8   4 9 6
j i

29.-     0   1   2   3 5   7   4 8 9 6
j i

30.-     0   1   2   3 5   4   7    8   9 6
j i

31.-     0   1   2   3 4   5   7    8   9 6
j i

32.-     0   1   2   3 4   5   7    8   9 6
j i

33.-     0   1   2   3 4   5   7    8   9 6
j i

34.-     0   1   2   3 4   5   7    8   9 6
j i

35.-     0   1   2   3 4   5   7    8   9 6
j i

36.-     0   1   2   3 4   5   7    8   9 6
j i

37.-     0   1   2   3 4   5   7    8   9   6
j i

38.-     0   1   2   3 4   5   7    8   9   6
j i

39.- 0 1 2 3 4 5 7 8 9 6
j i

40.- 0 1 2 3 4 5 7 8 9 6
j i

41.-     0   1   2   3 4   5   7    8   9   6
j i

42.-     0   1   2   3 4   5   7    8   9   6
j i

43.-     0   1   2   3 4   5   7    8   9   6
j i

44.-     0   1   2   3 4   5   7    8   9   6
j i

45.-     0   1   2   3 4   5   7    8 6    9
j i

46.- 0 1 2 3 4 5 7 6 8 9
j i

47.- 0 1 2 3 4 5 6 7 8 9
j i

48.- 0 1 2 3 4 5 6 7 8 9
j i

49.- 0 1 2 3 4 5 6 7 8 9

Nuestro array esta ordenado , como la condición ya no se cumple, se sabe de que el array fue ordenado de forma exitosa .

La implementación en c++ :

void insert_sort(int *A, int n )
{
for ( int i=1 ; i < n ; ++i )
{
for( int j=i; j>0 && A[ j ] < A [ j-1 ] ; --j)
swap( A[ j ] , A[ j-1 ] );
}
}

Explicación de la implementación en c++ :

Primero definimos el tipo de función, y los parámetros de esta como son un puntero dinámico y una variable n que sera el tamaño del arreglo
En el primer for la variable que definimos como i nos servirá de indice para empezar a pasar por todo el arreglo y empieza en la posición A[1] porque en la posición A[0] solo hay un elemento así que suponemos que ya esta ese elemento ordenado
En el segundo for declaramos la variable j que seria el indice que nos daría la posta para poder arreglar el fragmento del arreglo hasta donde lo delimite el indice de i .
si es que el numero anterior a la posición que j esta señalando es mayor se realiza un swap cambiando los valores que están en las dos posiciones y el j va a incrementando así sucesivamente y ordena el array

3.- SELECT SORT

Last chance

Adsense

miércoles, 13 de enero de 2016

Listas enlazadas [ c++ ]

jueves, 4 de septiembre de 2014

Clase Nodo

lunes, 30 de junio de 2014

PYTHON PYTHON PYTHON!

sábado, 21 de junio de 2014

Algoritmos de ordenación

¿Que es un algoritmo?

Ordenación

Algoritmos de Ordenación