Archivos de Categoría: Informática

Manual de programación en C

Entre los años 2001-2004 estuve dando clases en mi academia de informática, Academia Starnet. Entre otras materias di clases de programación en C.

Yo utilizaba el compilador Turbo C, lo podéis descargar aquí. Os dejo el manual que preparé:

Descargar 

{iframe width=”600″ height=”780″ style=”border: none;” }http://docs.google.com/viewer?url=http%3A%2F%2Fjosemari-cp40.webjoomla.es%2FDescargas%2FProgramaci%25C3%25B3n%2520en%2520C%2520Web.pdf&embedded=true{/iframe}

Prácticas Hack x Crack

Estas prácticas se publicaron en el foro de Hack x Crack (revista de seguridad informática que se dejó de publicar a finales del 2005) y fueron creadas por sus Administradores y Moderadores.

Tuve el honor de colaborar en la elaboración de alguna de estas 45 prácticas con las que os aseguro disfrutaréis:

Práctica 01. Configurando esafe para autenticar sesiones. 
Práctica 02. Vigilancia de Pc’s no custodiados con salus. 
Práctica 03. Vídeo-vigilancia con Pcspy. 
Práctica 04. Crear un banco de pruebas. 
Práctica 05. Esnifar sesiones de navegación. 
Práctica 06. Ocultar la IP. 
Práctica 07. Enviar mail anónimo usando telnet 
Práctica 08. Enviar mail anónimos mediante Phasma 
Práctica 09. Repeler cartas bomba y spam con email Remover 
Práctica 10. Encriptar mensajes de correo con PGP 
Práctica 11. Creación de un disco duro virtual encriptado con PGP 
Práctica 12. Configurar un servidor de ftp 
Práctica 13. Fxp entre servidores 
Práctica 14. Correos maliciosos 
Práctica 15. Convirtiendo el servidor ftp Serv-u en un troyano 
Práctica 16. Habilitar y deshabilitar las auditorías 
Práctica 17. Arrancando el serv-u automáticamente 
Práctica 18. Herramientas para manipular el registro 
Práctica 19. Empleo de rootkit ntroot 
Práctica 20. Instalación y configuración de ZoneAlarm 
Práctica 21. Cómo saltarse a ZoneAlarm y a otros… 
Práctica 22. Ocultación de archivos. Joinner, camuflages y streaming 
Práctica 23. Datos del registro y permitir relay de correo con Sam Spade 
Práctica 24. Volcado de su web a nuestro equipo con teleport 
Práctica 25. Barridos ping y trazado de rutas 
Práctica 26: localización geográfica con visualroute y neotrace 
Práctica 27. Detección del sistema operativo. Netcat, grinder, chronicle 
Práctica 28. Ocultar la ip mediante un bouncer 
Práctica 29. Enviar mail anónimos usando un ftp 
Práctica 30. Túneles y redirectores de puertos 
Práctica 31. Escaneadores y exploración de puertos. 
Práctica 32. Herramientas del sistema operativo para obtener información 
Práctica 33. Enumeración de usuarios. 
Práctica 34. Dns y nslookup. 
Práctica 35. Enumeración ne recursos y usuarios con snmp. 
Práctica 36. Aplicaciones, registro y otros escáneres 
Práctica 37. Esnifer y craqueo de contraseñas. Cain 
Práctica 38. Paso del hash. 
Práctica 39. Exploits para obtener shell de system 
Práctica 40. Shell remota con psexec.exe 
Práctica 41. Shell remota mediante el programador de tareas 
Práctica 42. Interactividad con iExplorer. 
Práctica 43. Una de servicios….marchando!!!! 
Práctica 44. Control remoto 
Práctica 45. Borrado de huellas 

 

Clasificación en memoria primaria

Introducción

La ordenación de datos es un tema importantísimo ya que organizar la información nos servirá para poder recuperarla posteriormente. Organizar esta información será costoso pero conseguiremos que la búsqueda sea muy rápida.

Voy a explicar los métodos más conocidos de ordenación, pondré el código fuente en C del programa que implemente el algoritmo, una explicación y comentaré por encima lo rápido o lento que es ese método.

Muchas veces tenemos la falsa creencia de que no es especialmente importante fijarnos en el método que seguimos para hacer un programa; es un error fijarse únicamente en que el resultado final sea bueno. NO hay que pensar esto:

-Bueno, como esto de la informática avanza tan rápido, aunque hoy vaya un poco lento dentro de uno años ya funcionará mejor.

Como ejemplo: Entre los algoritmos de ordenación que veremos hay dos clásicos que son el burbuja y el quicksort, este último tardaría en ordenar 100.000 elementos unos 17 segundos, mientras que el segundo tardaría 1700 minutos = 2 días, 5 horas y 40 minutos. La diferencia es bastante importante y es responsabilidad del programador utilizar bien los recursos.

Aunque ya he hablado de tiempos, no es costumbre hacerlo, porque claro, no es lo mismo ejecutar un programa en un 486 que en un Pentium4, o hacer el mismo algoritmo en C que en Ada o en VB. Así que aunque no me quiero meter de lleno en los costes de los algoritmos, por lo menos que se sepa que en un algoritmo de ordenación las 2 operación básicas son las comparaciones y los movimientos, y a la hora de ver lo bueno que es un algoritmo se tendrían en cuenta el número de comparaciones y de movimientos que hace el algoritmo (cuantos menos mejor).

Estoy utilizando la palabra algoritmo y la palabra programa y parecen casi sinónimas, pues no lo son. Los algoritmos son muy anteriores a los programas, los griegos propusieron numerosos algoritmos pero que se sepa no hicieron ningún programa. Como ejemplos de algoritmos griegos podemos mencionar el algoritmo de Euclides para calcular el máximo común divisor o la criba de Eratóstenes para calcular números primos. Estos 2 algoritmos pueden implementarse fácilmente.

Algoritmo fue acuñado por Mamad ibnMusa Al-Jwarizmi , matemático árabe del siglo IX y debe entenderse algoritmo como un método para resolver un problema. 
Un programa es una implementación del algoritmo para poderse ejecutar en un computador.

Por último y para que no haya más dificultades de las que ya presentan estos métodos: 
Matriz = Array = Arreglo = Tabla = Vector (si es de una dimensión)

En estas explicaciones ordenaremos vectores (arrays de 1 dimensión), ordenar arrays de más dimensiones no sería mucho más complicado.

Recomendaría encarecidamente que antes de seguir leyendo intentaseis hacer un algoritmo que ordenase un vector. Es bueno coger papel y lápiz e intentarlo.

Decir que para entender todo esto es recomendable: Vistazo rápido al algoritmo, ver ejemplo, volver al algoritmo con más calma, programarlo y meter watches.

 

Librerías:


Para no extender los programas demasiado, y como todos utilizarán una serie de funciones comunes, voy a implementar una librería que contenga todas estas funciones:

Por cierto, voy a hacer los ejemplos con TurboC.

Esta librería la llamaremos arrays.h y para que no haya problemas copiadla a la carpeta INCLUDE de vuestro compilador.

 #include <stdio.h>  #include <stdlib.h>  /*La siguiente función inicializa un vector v de MAX posiciones con números entre 0 y 99*/ void inicializar_vector_int (int v[], int MAX) { int i; srand(time(NULL)); for (i = 0; i  MAX; i ++)    {    v [i] = rand () % 100;    } }  void imprimir_vector_int (int v[], int MAX) { int i; for (i = 0; i  MAX; i++)    {    printf ("Vector[%3i]: %2i;    ", i, v[i]);    } }  void intercambiar (int *a, int *b) { it aux; au = *a; *a = *b; *b = aux; } 

Son tres funciones sencillitas que inicializan e imprimen un vector, los parámetros de estas funciones son los mismos en las 2 funciones, el vector y el número máximo de elementos. La última función intercambia por referencia el valor de 2 variables.

 

Métodos:

La clasificación por inserción se basa en insertar un elemento dado en el lugar que corresponde de una parte ya ordenada del array.

Inserción directa:

Explicación:

Este método es bastante intuitivo, en resumen, lo que hace es:

  • Toma un elemento en la posición i.
  • Busca su lugar en las posiciones anteriores.
  • Mueve hacia la derecha los restantes.
  • Lo inserta.

Algoritmo:

  #include <stdio.h>  #include <conio.h>  #include <arrays.h>  #define MAX 10  void main () { int i, j, a[MAX], aux; //clrscr(); //No es ANSI C (C estándar)  puts ("nnCLASIFICACION POR INSERCION BINARIAnn"); inicializar_vector_int (a,MAX); printf("nVector Desordenado:nn"); imprimir_vector_int (a, MAX);  for (i = 1; i < MAX; i++)    {    aux = a[i];    j = i;   //movemos los nums a la derecha hasta //encontrar la posición sin salirnos del vector    while ((aux 0))       {       a [j] = a [j-1];       j = j-1;       }    a[j] = aux;    } printf ("nnVector Ordenado:n"); imprimir_vector_int (a, MAX); } 

 

5

12

7

3

4

1

18

8

Vector inicial

5

12

7

3

4

1

18

8

(En negrita el que vamos a ordenar, gris de fondo para el subarray ordenado)

5

7

12

3

4

1

18

8

Hemos metido 7 en la posición que le corresponde y hemos corrido el resto de elementos (el 12) a la derecha.

3

5

7

12

4

1

18

8

Lo mismo, hemos puesto el 3 en su posición y hemos movido el resto una posición a la derecha.

3

4

5

7

12

1

18

8

 

1

3

4

5

7

12

18

8

 

1

3

4

5

7

12

18

8

 

1

3

4

5

7

8

12

18

Creo que con el ejemplo debe quedar claro.

 

Inserción binaria:

Explicación:

Es una mejora del anterior, básicamente cambia en un punto, a la hora de buscar la posición en la que debe ir el elemento lo hace de forma dicotómica
Dico... qué? 
Explico con un ejemplo muy sencillito.

Supongamos que jugamos con nuestro hermanito pequeño a un sencillo juego, él se inventa un número del 1 al 1000 y nosotros tenemos que adivinarlo lo antes posible, él nos indicará si nuestro número es más grande o más pequeño que el suyo.

Lo más lógico sería empezar con el 500, si nos hemos pasado diríamos 250, si nos hemos vuelto a pasar el 125, si nos hemos quedado ahora cortos diríamos:

125+(250-125)/2 = 187 (sin decimales, claro)

Bueno, se entiende, ¿verdad? Pues eso es una búsqueda dicotómica, no sería muy sensato por nuestra parte empezar: 1, 2, 3, 4, ... Podríamos tardar mucho, hasta 1000 intentos. En cambio, ¿sabéis cuántos intentos haremos como máximo con nuestra búsqueda dicotómica?

Reflexionemos, calculadora... Pues haríamos exactamente:

log 2 (1000) = 9.9

Vamos que como máximo haremos 10 intentos. Os explico de donde sale ese logaritmo en base 2 (si al final nos servirán y todo los logaritmos xD).

Hay que hacerlo en base 2 porque dividimos cada vez entre 2 los números restante, fijaros en la fórmula que he puesto antes. Simplificando más:

Si fueran 2 números, como máximo haríamos 1 intento para saber el número, claro decimos 1 y si no es ya sabemos cual queda.

Si fueran 4 números como máximo en 2 turnos ya lo sabríamos.

Si fueran 8 números como máximo lo adivinaría en 3 turnos.

Ejemplo: Números del 1 al 8, me imagino el 3. Al principio puede ser cualquiera:

1

2

3

4

5

6

7

8

Digo el 4 (el más central), así que descarto del 5 al 8.

1

2

3

4

Digo el 2 (el más central), me quedan 2 números:

3

4

Digo el 3 (el más central), he ganado!

Pues el logaritmo en base 2 de 8 en 3.

¿Qué no sabéis aún que es un logaritmo? Verdad que 2^3 = 8? Pues se trataría de si tenemos esta ecuación 2^x = 8, adivinad las x.

Las calculadoras científicas no tienen logaritmo en base 2, tienen logaritmo en base 10 (log) y logaritmo en base e (un número muy raro que sale de una sucesión 🙂 , ln).

Si queremos calcular el logaritmo en base 2 de algún número por ejemplo de 1000 podemos hacer: (log(1000))/(log(2))

Tendríamos el mismo resultado si hiciéramos: (ln(1000))/(ln(2))

Bueno, seguimos, que a este paso no acabaremos.

En resumen, este algoritmo sigue estos pasos:

  • Toma un elemento en la posición i.
  • Busca su lugar dicotómicamente en las posiciones anteriores.
  • Mueve hacia la derecha los restantes.
  • Lo inserta.

Este método es más efectivo que el anterior porque hay menos comparaciones al hacer la búsqueda. A diferencia que el anterior no tiene que comparar con todos los elementos anteriores hasta encontrar el bueno.

Comentar que hay una variación del método de búsqueda dicotómica que explicado de forma muy sencilla y con un ejemplo sería algo así:

Si seguimos con un ejemplo parecido al anterior; suponemos que hay que buscar la posición que le corresponde a un número entre 1000 que ya tenemos colocados, estos 1000 números van entre el 0 y el 999, ese número que debemos poner en la posición correcta en el 100, pues probablemente el número 100 irá en una posición cercana a la 100. Si quisiera meter el número 500 buscaría por la mitad, con el 900 buscaría antes por el final.

No le deis muchas vueltas, simplemente se trata de hacer una estimación de donde puede ir ese número antes de ponernos a buscar. Nosotros lo haremos con el método clásico explicado anteriormente.

Algoritmo:

  /*Algoritmo de Inserción Binaria*/  #include <arrays.h>  #include <stdio.h>  #define MAX 10  void main () { int i, j, m, L, R, x; int v[MAX]; puts("nnCLASIFICACION POR INSERCION BINARIAn"); inicializar_vector_int (v, MAX); printf ("nVector sin ordenar:nn"); imprimir_vector_int (v, MAX);  for (i = 1; i  MAX; i++)   {   x = v[i];    /* L/R: Índice izquierdo/derecho del subarray en el   que hacemos la búsqueda*/   L = 0;   R = i;    while (L  R)      {      m = (L+R)/2;  //Búsqueda en la mitad del subarray       if (v[m]  R; j--)      {      v[j] = v[j-1];  //desplazamiento      }    v[R] = x;          //inserción   }  printf ("nnVector ordenado:n"); imprimir_vector_int(v,MAX); } 

 

Selección directa:

Explicación:

También es un método bastante intuitivo, y de hecho es el que a más alumnos se les ocurre antes de haber visto ningún método de ordenación.

Se trata de:

  • Buscar el menor elemento de la parte del vector que no está ordenada.
  • Colocarlo en la primera posición de la parte no ordenada de la tabla.

Este método es más efectivo que los 2 anteriores

Algoritmo:

  /*Algoritmo de Selección Directa*/  #include <stdio.h>  #include <arrays.h>  #define MAX 10  void main () { int i, j, k, x, v[MAX];  puts("nnCLASIFICACION POR SELECCION DIRECTAn"); inicializar_vector_int (v, MAX); printf ("nVector sin ordenar:nn"); imprimir_vector_int (v, MAX);  for (i = 0; i < MAX-1; i++)    {    k = i;    x = v[i];  //selección inicial    for (j = i+1; j  MAX; j++)       {       if (v[j]  x) 	   { 	   k = j; 	   x = v[j; //Selección 	   }       }    v[k] = v[i]; //Intercambio    v[i] = x;     } printf ("nVector ordenado:nn"); imprimir_vector_int (v, MAX);  } 

Ejemplo:

Como ejemplo ordenaremos el mismo vector que antes. Pondré en negrita los elementos que se van a intercambiar y de color gris de fondo los que ya están ordenados.

5

12

7

3

4

1

18

8

Cogemos el 1 que es el más pequeño y lo ponemos en la primera posición.

1

12

7

3

4

5

18

8

El siguiente más pequeño es el 3, irá en la segunda posición.

1

3

7

12

4

5

18

8

Seguimos con el 4. Fácil, ¿verdad?

1

3

4

12

7

5

18

8

 

1

3

4

5

7

12

18

8

El 7 ya está en su sitio, así que se deja.

1

3

4

5

7

12

18

8

 

1

3

4

5

7

8

18

12

 

1

3

4

5

7

8

12

18

El último elemento queda ordenado el solito.

Supongo que con el ejemplo se verá muy claro este algoritmo, yo diría que este es el más sencillito y más intuitivo.

 

Burbuja (o intercambio directo):

Explicación:

Antes de empezar con este método quiero incidir en lo malo que es. Este es un algoritmo peor que los anteriores y cuando veáis el ejemplo lo entenderéis.

Se trata de:

  • Hacer comparaciones entre pares de elementos contiguos
  • Intercambiarlos si están desordenados

Algoritmo:

  /*Algoritmo de Burbuja o Intercambio Directo*/  #include <stdio.h>  #include <arrays.h>  #define MAX 10  void main () { int i, j, v[MAX];  puts("nnCLASIFICACION POR BURBUJAn"); inicializar_vector_int (v, MAX); printf ("nVector sin ordenar:nn"); imprimir_vector_int (v, MAX);  for (i = 0; i < MAX; i++)    {    for (j = 0; j  v[j+1])  //compara elementos contiguos 	 intercambiar(&v[j], &v[j+1]);       }    }  printf ("nVector ordenado:nn"); imprimir_vector_int (v, MAX); } 

Ejemplo:

Visto el algoritmo puede parecer sencillito, y la verdad es que el método es muy simple, pero veamos el ejemplo. Pondremos el mismo vector de los ejemplos anteriores pero nos saltaremos algunos pasos porque este método es muy largo. De todas formas no pasa nada, enseguida se comprende lo que hace.

5

 

5

 

5

 

5

 

5

 

5

 

5

 

5

 

 

12

 

12

 

7

 

7

 

7

 

7

 

7

 

7

 

1ª pasada

7

 

7

 

12

 

3

 

3

 

3

 

3

 

3

 

7 iteraciones

3

 

3

 

3

 

12

 

4

 

4

 

4

 

4

 

 

4

 

4

 

4

 

4

 

12

 

1

 

1

 

1

 

 

1

 

1

 

1

 

1

 

1

 

12

 

12

 

12

 

 

18

 

18

 

18

 

18

 

18

 

18

 

18

 

8

 

 

8

 

8

 

8

 

8

 

8

 

8

 

8

 

18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5

 

5

 

5

 

5

 

5

 

5

 

5

 

 

 

 

7

 

7

 

3

 

3

 

3

 

3

 

3

 

 

 

2ª pasada

3

 

3

 

7

 

4

 

4

 

4

 

4

 

 

 

6 iteraciones

4

 

4

 

4

 

7

 

1

 

1

 

1

 

 

 

 

1

 

1

 

1

 

1

 

7

 

7

 

7

 

 

 

 

12

 

12

 

12

 

12

 

12

 

12

 

8

 

 

 

 

8

 

8

 

8

 

8

 

8

 

8

 

12

 

 

 

 

18

 

18

 

18

 

18

 

18

 

18

 

18

 

 

 

 

Ya veis que sería un palo escribir todo el proceso. El algoritmo es sencillito pero muy ineficaz.

En la primera pasada queda ordenado el elemento mayor, en la segunda el siguiente número más grande, etc...

 

Clasificación por partición (quicksort)

Explicación:

Este método fue desarrollado por C.A.R. Hoare en el año 1960 y es el método más rápido que se conoce hasta la fecha. Es un método de clasificación avanzada.

Se basa en que cuanto mayor sea la distancia entre los elementos que se intercambian más eficaz será la clasificación. Para ello se elige un pivote. Está demostrado que la eficacia del algoritmo es mayor si esta llave es el elemento central, aunque lo ideal sería que el pivote fuera la mediana, pero claro, para saberla sería necesario ordenar antes el vector.

 

Se trata de buscar un elemento mayor que el pivote en la parte izquierda, y otro menor que el pivote en la parte derecha e intercambiarlos. S i en la parte izquierda o derecha no se encuentran valores superiores o inferiores al pivote respectivamente lo que se intercambia es el pivote. Este proceso se repite hasta que se cruzan el índice de incremento y el de decremento, en este momento nos queda dividido el vector en 2 partes, la parte izquierda con los elementos menores que el pivote y la parte derecha con los mayores que el pivote. A cada una de estas partes se le llama partición. Esta operación se repite con cada partición hasta que no haya particiones a ordenar. El algoritmo termina cuando no se encuentran valores superiores en la parte izquierda no se encuentran valores inferiores en la parte derecha cuando se llega a los dos últimos elementos.

 

Este método parece desmentir el famoso dicho popular que otorga una mayor eficacia a soluciones simples frente a otras más complejas. Es un método muy complejo y es probable que os cueste asimilar al principio.

Algoritmo:

Tradicionalmente este algoritmo se implementa de forma recursiva. Una función recursiva es una función que se llama a sí misma. ¿Verdad que parece raro?

  /*Algoritmo de clasificación por partición o quicksort*/  #include <stdio.h>  #include <arrays.h>  //#include <conio.h> //No es ANSI C  #include <time.h>  #define MAX 10 void quicksort (int v[], int l, int r);  void main () { int v[MAX]; int l, r; clock_t start, end; //clrscr(); puts ("nnQUICKSORTnn"); inicializar_vector_int (v, MAX); imprimir_vector_int (v, MAX); //puts("nnPresiona una tecla para ordenarlo"); //getch(); start = clock(); quicksort (v, 0, MAX-1); end = clock(); printf ("nnVector ordenado en %f segundosnn",(end - start) / CLK_TCK); //getch(); imprimir_vector_int (v, MAX); }  void quicksort (int v[], int l, int r) { int i, j, piv; i = l; j = r; piv = v[(l+r)/2]; /*Pivote central*/  do {      while (v[i] < piv) i++;    while (piv  v[j]) j--;     if (i = j)       {       itrcambiar (&v[i], &v[j]);       i++;       j--;       }    } while (i = j);    if (l  j) quicksort (v,l,j);    if (i  r) quicksort (v,i,r); } 

Pues allí lo tenéis. En este algoritmo he metido muchas pijaditas para que hagáis vuestros experimentos, ahora os aconsejo unos cuantos. En este algoritmo hay funciones que no son ANSIC pero las he puesto como comentarios, os las dejo por si queréis probar. Estas funciones son getch(), que esperaría a que tocásemos una tecla para seguir y clrscr() que borra el contenido de la pantalla.

También he metido un sencillo cronómetro que nos dice el tiempo que se ha tardado en ordenar el vector; para que sea apreciable podéis cambiar los 10 elementos por 30000 (por ejemplo), para hacerlo es suficiente con cambiar

 

#define MAX 10 

 

por

#define MAX 30000 

 

Puede que si metéis más de 32768 elementos se líe el compilador.

Si metéis este cronómetro a los otros ejercicios podréis hacer una comparación de la eficacia.

Ejemplo:

Como ya he dicho, este método es complicado, puede que con el ejemplo la cosa quede más clara y se entienda la recursividad.

Pondré en rojo el pivote, en negrita de diferentes colores los intercambios y muy clarito la parte del vector en la que no nos fijamos en la llamada recursiva. O sea, cuando llamemos recursivamente a la función se pasará una parte del vector, lo vemos:

5

12

7

3

4

1

18

8

Vector inicial, el pivote es el central.

5

12

7

3

4

1

18

8

Cambio el 5 por el 1. El 5 es mayor que el pivote y está en la izquierda, el 1 es menor que el pivote y está en la derecha. 
Lo mismo pasa con el pivote (3) y el 12, los intercambiamos.

1

3

7

12

4

5

18

8

En una llamada recursiva se pasan estos dos elementos y ya están ordenados.

1

3

7

12

4

5

18

8

Esta vez el pivote es el 4. Cambiamos el 7 por el 4

1

3

4

12

7

5

18

8

Tenemos como pivote el 5 y lo cambiamos por el 12. El 18 y el 8 son mayores que el pivote, los dejamos.

1

3

4

5

7

12

18

8

El 8 es menor que el pivote y está en la parte derecha, así que lo cambiamos por el pivote.

1

3

5

4

7

12

8

18

El 18 quedó ordenado, el nuevo pivote es el 12 y lo cambiamos por el 8.

1

3

4

5

7

8

12

18

Ordenado! Sólo quedaban 2 elementos.

Sigo diciendo que es un método complicado. Los puntos más complicados es ver los subarrays que se pasan a la función recursiva, éstos nos van quedando limitados por el lugar en el que queda el pivote.

 

Unas consideraciones

Existen otros muchos métodos de ordenación en memoria primaria y también existen otros métodos para la clasificación en memoria secundaria.

La clasificación en memoria secundaria no está incluida en el temario del curso pero me permito hacer una breve explicación para que se comprendan las limitaciones de los métodos expuestos anteriormente.

El acceso a un elemento en memoria primaria tiene el mismo coste siempre, esté donde esté el elemento. O sea, si estamos en el primer elemento tardamos lo mismo en acceder al segundo que al último. Este tipo de ordenación se hace sobre la memoria RAM: Random Acces Memory (Memoria de Acceso Aleatorio).

En cambio, en la memoria secundaria es secuencial (igual que una cinta de video). Para ir a una posición, antes tenemos que recorrer todas las anteriores; por lo tanto, los métodos de ordenación no pueden ser los mismos, ya que no interesa que los números hagan saltos grandes continuamente. Para poder ordenar cintas necesitaríamos de cintas auxiliares.

Por cierto, habéis visto superman 3 (creo que era 3), si recordáis se ven unos “superordenadores” del año catapún que controlaban unas cintas inmensas que se movían continuamente. Pues eso sería la memoria secundaría, y como podéis suponer los métodos para ordenar eso son bastante más complejos.

Para *entender la diferencia entre memoria secuencial y de acceso aleatorio podemos comparar en escuchar música con una cinta y con un CD. En la cinta, si queremos escuchar la última canción tendremos que correr la cinta hacia adelante pasando por todas las anteriores, en cambio en un CD de música eso no es necesario.

(*Nota: no digo que un CD sea de acceso aleatorio, simplemente pongo este ejemplo para que comprendamos la diferencia. Los CD's son de acceso directo (una combinación entre acceso aleatorio y acceso secuencial)).

 

Para acabar

Bueno, espero no haberos aburrido mucho, el tema es muy interesante pero es bastante complejo. Recomiendo programarlos todos, ejecutarlo paso a paso y ver como se van ordenando los vectores.

Agradecimientos: Agradezco los consejos de el_chaman y el fallo detectado por Vic_Thor, ambos del foro de hackxcrack.

Bibliografía: Para elaborar este documento me he ayudado del libro “Estructuras de Datos y Algoritmos” de la editorial “Prentice Hall”. Los programas han sido adaptados a C y tienen algunas modificaciones.