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 ("\n\nCLASIFICACION POR INSERCION BINARIA\n\n");
inicializar_vector_int (a,MAX);
printf("\nVector Desordenado:\n\n");
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 ("\n\nVector 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("\n\nCLASIFICACION POR INSERCION BINARIA\n");
inicializar_vector_int (v, MAX);
printf ("\nVector sin ordenar:\n\n");
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 ("\n\nVector 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("\n\nCLASIFICACION POR SELECCION DIRECTA\n");
inicializar_vector_int (v, MAX);
printf ("\nVector sin ordenar:\n\n");
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:\n\n");
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("\n\nCLASIFICACION POR BURBUJA\n");
inicializar_vector_int (v, MAX);
printf ("\nVector sin ordenar:\n\n");
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:\n\n");
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 ("\n\nQUICKSORT\n\n");
inicializar_vector_int (v, MAX);
imprimir_vector_int (v, MAX);
//puts("\n\nPresiona una tecla para ordenarlo");
//getch();
start = clock();
quicksort (v, 0, MAX-1);
end = clock();
printf ("\n\nVector ordenado en %f segundos\n\n",(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.