Estructuras Básicas de Datos:

Introducción:
Dato: Cualquier información correspondiente a una entidad susceptible de un tratamiento informático. Ej.: (Entidad: Empresa / Datos: Nombre, Dirección, Nº Empleados…)

Para un ordenador la información que maneja es numérica (ceros y unos) “binario”, aún así, los datos tienen que estar clasificados para poder tratarlos de forma conveniente.

La clasificación de los datos determina las ESTRUCTURAS DE DATOS de un lenguaje.

Un dato se caracteriza por llevar asociado los siguientes elementos:
Identificador: nombre que permite referenciar el dato.

Los identificadores de los datos deben cumplir una serie de condiciones:
a-   Pueden estar constituidos por letras, dígitos y el carácter “_”
b-   No pueden contener espacios.
c-   El nº de caracteres y dígitos máximos dependen del compilador utilizado.
d-   Deben comenzar por una letra
e-   Deben dar alguna pista para reconocer el dato que van a referenciar.
Tipo: Determina el rango de valores que van a ser posibles para ese dato.
Ej.: EDAD: Nº entero.

Valor inicial: Valor perteneciente al rango determinado por el tipo asociado al identificador.

Tipos de datos:
Clasificación de los datos:
Datos Básicos
Numéricos: Entero, Real

No Numéricos: Carácter, Lógico

Derivados: Puntero

Datos Estructurados:

Internos:
Estáticos lineales: Tablas
Dinámicos   Lineales: Listas, Pilas, Colas
No lineales: Árboles, Grafos

Externos: Ficheros, Bases de Datos

Compuestos: Estructura de Datos, Registro

Puntero: Funciona con direcciones de memoria asociadas.
Existe un operador que permite obtenerlas, pero ya lo trataremos más adelante.

Datos estructurados: Compuestos de datos básicos.
(Internos: Memoria Temporal / Externos: Dispositivos de Almacenamiento)

Datos dinámicos: Reservas de memoria en tiempo de ejecución.
   Lista: Se accede y llena en cualquier orden.
   Pila: Se insertan los datos en orden, se extraen en orden inverso.
   Cola: Obligatorio insertarlos en orden y extraerlos en ese mismo orden.

Datos estáticos: Reservan una cantidad fija de memoria (En tiempo de compilación)

Datos Básicos:

Datos numéricos: Se utilizan para contener magnitudes y se dividen en enteros y reales.
a-   Enteros: Se emplean para representar números enteros, el rango de representación depende del compilador y del ordenador. Los datos de tipo entero aparecen representados por los dígitos decimales, que pueden ir precedidos por los signos + o -. Ej.: -35 +3200.

b-   Reales: Se emplean para representar números con parte fraccionaria o números Enteros muy grandes o muy pequeños que están fuera del rango establecido para los enteros.

Para su representación se utilizan dos formatos:

• Decimal: Dígitos del 0 a 9 y el punto decimal que separa la parte entera de la fraccionaria.
• Formato Científico o Exponencial: <mantisa><E><característica>

   Mantisa: Nº real decimal.
   E: Base 10
   Característica: Exponente.

La representación interna viene determinada por la precisión:
•   Para simple precisión    (32 bits)
o   Signo - 1bit - (posición 31)
o   Exponente - 8bits - (posiciones 23 a 30)
o   Mantisa - 23bits - (posiciones 0 a 22)
•   Para doble precisión    (64 bits)
o   Signo - 1bit - (posición 63)
o   Exponente - 11bits - (posiciones 52 a 62)
o   Mantisa - 52bits - (posiciones 0 a 51)

Datos No numéricos:
a-   Carácter: Se emplea para representar un carácter dentro de un conjunto definido por el fabricante del ordenador, de tal manera que cada carácter se corresponda con un nº entero, según un determinado código. Ej.: Código ASCII.
Se representan encerrando el carácter entre comillas simples, existen los siguientes tipos de caracteres:
o   Dígitos: ‘1’,’0’,’9’…
o   Alfabéticos: ‘A’,’a’,’b’…
o   Especiales: ‘*’,’_’…

La representación interna depende del código utilizado, los códigos más empleados son los que utilizan 8 bits, como por ejemplo el ASCII (American Standard Code for Information Interchange) o el EBCDIC (Extended Binary Coded Decimal Interchange Code)

Ej.: A = 65 = 01000001

En algunos lenguajes como el COBOL se considera tipo de dato básico a las cadenas alfanuméricas. Estas se representan encerradas entre dobles comillas.
Ej.: “I.E.S Dr. Fleming Nº25”

En C no es un tipo de dato básico (Se usan tablas)

b-   Lógico: Es un tipo de dato que solo puede tomar dos valores, se pueden representar como Cierto y Falso, True y False, V y F.
Internamente se representa con un ‘0’ para false y un ‘1’ para true.
En C ‘0’ es false, mientras que cualquier otra cosa se considera como true.

Variables y Constantes:

Memoria Central: Dispositivo de almacenamiento temporal de:
•   Datos
•   Instrucciones
•   Resultados de un programa:
o   Intermedios
o   Finales

Consideremos la memoria como una caja dividida en compartimentos. Cada compartimento es del mismo tamaño y está identificado por una dirección de memoria. Los compartimentos se suelen denominar celdas, las direcciones, posiciones de memoria.

Cada celda tiene una dirección distinta que permite identificarla. Esto nos permite almacenar y recuperar datos de la Memoria Central.

Nota: Las cadenas no se pueden meter en una sola dirección de memoria, sino que usan varias simultáneamente.

Almacenar algo en una posición usada sobrescribe lo anterior por lo tanto:
La escritura en memoria es destructiva, mientras que la lectura no lo es.
Las zonas de memoria no están vacías a menos que se sobrescriban intencionadamente.
Las direcciones de memoria se pueden identificar con un nombre, el sistema se encarga de asignar una dirección concreta a ese nombre. (En lenguajes de programación de alto nivel)[C o superior].

Variable: Zona de memoria referenciada con un nombre de variable que va a contener un dato.
Nota: Una variable NO es un dato, contiene un dato.
Para que una variable esté perfectamente definida hay que indicarle:
•   Un nombre (identificador)
•   Un tipo de dato
•   Un valor inicial

Para introducir un valor en una variable se realiza lo siguiente:
A este hecho se le llama Asignación de Variables.

Para recuperar el valor basta con nombrar la variable:
(haciendo esto la máquina tomará <valor> de la memoria y sustituirá la variable por dicho valor en la ejecución)

En función del dato asignado a la variable, se pueden clasificar en numéricas, enteras, reales, alfanuméricas, caracteres y lógicas.

Asignación: Introducción de un valor o del contenido de otra variable en una zona de memoria referenciada por ese nombre de variable. = se usa tanto como asignación, como para preguntar al sistema si es igual.

Nota: Se aconseja usar ‘==’ para preguntar si es igual y ‘=’ para asignar, esto ayudará a diferenciar ambas tareas de forma sencilla a la hora de revisar el código.

Tanto la variable receptora como la otra tienen que ser del mismo tipo para realizar la asignación del valor de una variable a otra.

Constante: Es una zona de memoria referenciada con un nombre de constante, cuyo valor no puede cambiar a lo largo de la ejecución de un programa.
Las constantes pueden ser numéricas, enteras o reales, alfanuméricas o de carácter.
Las constantes lógicas no tienen sentido.

Operadores:
Operadores: Símbolos que permiten conectar datos, variables y constantes con el fin de realizar una operación determinada.
Operador - Símbolo - Significado

Paréntesis - () - Paréntesis

Aritméticos - **,^ - Potencia
* - Producto
/ - División Real
DIV,\    - División Entera
%,mod - Resto de una división entera
+ - Suma
- - Resta
+ - Concatenación
- - Concatenación eliminando espacios en blanco
Relacionales - ==,= - Igual, Asignación
!=,<> - Distinto
< - Menor
<= - Menor o Igual
> - Mayor
>= - Mayor o Igual

Lógicos - !,NOT,NO - Negación
ff,AND,Y - Conjunción
||,OR,O - Disyunción

AB AND   AB OR   A NOT
00 0         00 0      0 1
01 0         01 1      1 0
10 0         10 1      
11 1         11 1      

Existen reglas de prioridad entre los distintos operadores, dependen de los lenguajes de programación, pero en general son los siguientes:
1.   Paréntesis
2.   Signo
3.   Potencia
4.   Producto, División y Módulo (Resto)
5.   Suma y Resta
6.   Concatenación
7.   Relacionales
8.   Negación
9.   Conjunción
10.   Disyunción

Expresiones:
Expresiones: Son un conjunto de valores variables (operandos) y operadores relacionados o combinados entre si, según unas reglas establecidas. Los operandos pueden ser también valores retornados por funciones.

En función del resultado obtenido, las expresiones se clasifican en:
•   Aritméticas: El resultado de la evaluación de la expresión es numérico.
•   Relacionales: Utilizan operadores relacionales y el resultado es un valor lógico.
•   Lógicas: Utilizan operadores lógicos y se aplican expresiones relacionales. El resultado de la evaluación es un valor lógico.
•   Alfanuméricas: Utilizan operandos y operadores alfanuméricos.

--

ESTRUCTURAS ESTÁTICAS DE DATOS:
Tablas: Está formada por un número fijo de elementos (variables) todos ellos del mismo tipo de datos y situados en posiciones contiguas de memoria.
Elemento: Es cada uno de los datos que constituyen la tabla.

Nombre de Tabla: Es un nombre de variable que permite referenciar toda la tabla de forma global y nos permitirá acceder a cada elemento de forma individual.

Tipo de Tabla: Es el tipo de dato de todos los elementos de la lista.

Índices: Un entero positivo que nos permite identificar cada elemento de una tabla.

Tamaño de Tabla: Número máximo de elementos que componen la tabla.

ACCESO A LOS ELEMENTOS: Los elementos de una tabla tratados individualmente son variables que reciben el mismo trato que cualquier otra variable simple, con un tipo de dato que coincide con el tipo de la tabla y una denominación propia que la distingue de los diversos elementos. Para acceder o referenciar un elemento en particular es suficiente con indicar el nombre de la tabla seguido por el índice correspondiente entre paréntesis.

Dimensión: El número de índices que necesitamos para referenciar una tabla.

CLASIFICACIÓN DE LAS TABLAS:
•   Unidimensionales: (Vectores) En este caso, solo es necesario un índice para acceder a los elementos de la misma.
•   Bidimensionales: (Matrices) Son aquellas que necesitan dos índices para acceder a cada uno de sus elementos.

Programación Estructurada:
Introducción:
Desde el nacimiento de la informática, se han ido desarrollando métodos y herramientas con el objetivo de facilitar y mejorar el diseño y resolución de programas. Hay dos clases:
Programación estructurada: Conjunto de técnicas que incorporan:
a-   Diseño descendente (Top-Down) “Diseño por capas”
b-   Descomposición de tareas en tareas más simples
c-   Solo se pueden utilizar 3 tipos de estructuras
a.   Alternativa
b.   Repetitiva
c.   Secuencial

Programación modular: Consiste en la división de un programa en módulos, de tal forma que cada uno de ellos se encargue de la ejecución de una tarea. Los módulos pueden ser subprogramas, subrutinas, funciones o procedimientos.

Partes de un programa:
Todo programa está constituido por un conjunto de instrucciones o de órdenes capaces de manipular los datos. Estas órdenes pueden ser divididas en tres grandes grupos que determinan las partes de un programa.
Entrada de datos -> Proceso -> Salida de resultados

•   Instrucciones de entrada de datos: Conjunto de instrucciones que permiten llevar datos desde el exterior (tomar datos a través de un dispositivo de entrada y almacenarlos en la memoria central).
•   Instrucciones de proceso: Conjunto de instrucciones encargadas de procesar o realizar un tratamiento de datos obteniendo unos resultados que se almacenan en la memoria central.
•   Instrucciones de salida: Permiten extraer datos (resultados) de la memoria central mostrándolos a través de un dispositivo de salida.

Datos ->
Dispositivo Externo <-> Memoria Principal <-> Proceso o algoritmo
<- Resultados

Algoritmo:
Es la descripción abstracta de todas las acciones u operaciones que debe realizar un ordenador de forma clara y detallada así como el orden en el que estas deberán ejecutarse junto con la descripción de todos aquellos datos que deberán ser manipulados por dichas acciones y que nos conducen a la solución del problema. Un algoritmo deberá reflejar las 3 partes de un programa (entrada, proceso, salida) es importante tener en cuenta que todo algoritmo debe ser totalmente independiente del lenguaje de programación utilizado. Las características que debe cumplir el diseño de todo algoritmo son las siguientes.
a-   Debe ser conciso y detallado. Debe reflejar con el máximo detalle el orden de ejecución de cada acción u operación que vaya a realizar el ordenador.
b-   Debe ser flexible, permitiendo y facilitando así las futuras modificaciones o actualizaciones del diseño realizado.
c-   Debe ser finito, tener comienzo y final.
d-   Ser lo más claro y sencillo posible.

Diagramas de Flujo:
Son representaciones gráficas que mediante símbolos estandarizados permiten describir las acciones y la lógica que ha de seguir un algoritmo junto con el flujo de datos para la obtención de los resultados convenidos.
Ordinogramas: Diseño
Organigramas: Análisis
Pseudocódigo: Lenguaje intermedio entre el natural y el lenguaje de programación (el cual vamos a tratar en este tutorial). Todo algoritmo en pseudocódigo debe reflejar las distintas partes de un programa.

Tipos de Instrucciones:
Instrucción: Hecho o suceso de duración limitada que permite generar unos cambios previstos en la ejecución de un programa.
Instrucciones de definición de datos: Permiten reservar la memoria necesaria para almacenar los datos que se van a manejar en el programa. Mediante el uso de variables simples o complejas.

Las instrucciones de definición consisten únicamente en dar un nombre y un tipo de dato a las zonas de memoria que quiero reservar.

Instrucciones primitivas:
•   Instrucciones de Entrada: Permiten almacenar un dato en la memoria central durante el uso de una o más variables procedentes de un dispositivo externo (generalmente el teclado).
Esta instrucción para el proceso de ejecución hasta que se introduzcan tantos datos como variables aparezcan en la lista de variables.
•   Instrucciones de Asignación: Consiste en introducir en una variable el resultado de evaluar una expresión.
•   Instrucciones de Salida: Permiten recuperar un dato de la memoria central para mostrarlo desde un periférico de salida.
Instrucciones Compuestas:
No pueden ser ejecutadas directamente por el procesador y están constituidas por un bloque de acciones agrupadas en subrutinas, subprogramas, funciones o módulos.

Instrucciones de control: Se utilizan para controlar la secuencia de ejecución de un programa y también para determinar si se ejecutan o no bloques de instrucciones:

•   Alternativas:
o   Simple: Permite la ejecución de un grupo de instrucciones en función de que se cumpla o no una condición.
o   Doble: Permite decidir por un grupo de instrucciones u otro en función de si se cumple la condición o no.
o   Múltiple: Ejecuta distintos grupos de instrucciones en función del resultado de la evaluación de una expresión.

Instrucciones repetitivas:
Nos permiten variar o alterar la secuencia normal de ejecución de un programa haciendo posible que un grupo de acciones se ejecute más de una vez de forma consecutiva, también se denomina bucles o lazos.
-   Estructura Mientras: Se caracteriza por la repetición de un conjunto de instrucciones en función de que se cumpla o no la condición, pueden repetirse de 0 a n veces.

o   Se evalúa la condición, si se cumple, se ejecutan las instrucciones comprendidas entre el mientras y el fin mientras y de nuevo se evalúa. El proceso termina cuando la condición se cumple.

-   Estructura Repetir: Permite la repetición de un proceso mientras se cumpla una condición evaluando la condición al final de cada repetición, el proceso se repite de 1 a n veces.

o   El conjunto de instrucciones entre repetir y mientras, se ejecuta (al menos una vez) evaluando la condición y volviendo a repetir en caso de que se cumpla.

-   Estructura Para: Repetición de un proceso un número determinado de veces

Donde el incremento indica la cantidad a aumentar la variable dentro del proceso repetitivo.

Contadores y Acumuladores:
Contador: Es una variable que se incrementa o decrementa en una cantidad constante.
Acumulador: Variable que se incrementa en un valor no constante.

Tenéis disponibles en este otro post varios ejercicios resueltos de pseudocódigo con los que podéis poner en práctica lo aprendido en este.

Ejercicios de Pseudocódigo

Iré actualizando ambos post según me vaya siendo posible.

ALGORITMOS RECURSIVOS:

Para definir algoritmos recursivos, es necesario establecer una relación de recurrencia en términos del tamaño del problema.
Las relaciones recurrentes más simples se establecen disminuyendo el tamaño del problema en una unidad o dos (cantidad fija) aunque también puede reducirse en algunos casos en cantidades no fijas (mitad) dado que la solución del problema se plantea como una relación recurrente del tamaño del mismo, para poder obtener la solución, es necesario poder disponer de unas series (o solo una en muchos casos) de soluciones particulares, lo que se denomina caso base.

Ejemplo1: Algoritmo recursivo para el calculo factorial de un número n.
Caso Base: n=0 f=1 {ya que el factorial de 0 es 1}
Hipótesis de Recurrencia: Sé resolver el factorial de n-1 f=FACTORIAL(n-1) {haremos posteriormente esa función FACTORIAL, que será la que haga la recurrencia}
¿Cómo lo resuelvo para un término más? n*FACTORIAL(n-1) {ya que un termino más sería FACTORIAL(n) que es exactamente lo mismo que n*FACTORIAL(n-1) la diferencia es que el primero no nos permite la recurrencia pero el segundo si.}

FUNCION FACTORIAL

Ahora paso a explicar su funcionamiento, aunque a la hora de plantearlo no hace falta verlo así, basta con saber que va a funcionar, si se intenta ver el funcionamiento en algoritmos con recursiones muy complejas, solo se conseguirá liarse y no llegar a nada.

Este algoritmo realizará lo siguiente, por ejemplo para n=3:

Arranca el módulo FACTORIAL(3):
n=3, como n!=0
llama a f=n*factorial(2)

Arranca el módulo FACTORIAL(2):
n=2, como n!=0
llama a f=n*factorial(1)

Arranca el módulo FACTORIAL(1):
n=1, como n!=0
llama a f=n*factorial(0)

Arranca el módulo FACTORIAL(0):
n=0
Termina el modulo FACTORIAL(0) devolviendo un 1
Termina el módulo FACTORIAL(1) devolviendo un 1*1 = 1
Termina el módulo FACTORIAL(2) devolviendo un 2*1 = 2
Termina el módulo FACTORIAL(3) devolviendo un 3*2 = 6

En conclusión, sacamos que, cuando se ejecuta un programa recursivo, las llamadas recursivas no se ejecutan inmediatamente, lo que se hace es colocarlas en una pila hasta que se encuentra la condición de terminación de la recursividad, entonces se ejecutan las llamadas a la función en orden inverso a como se generaron como si se fueran sacando de la pila. *si no lo recordáis ya, ver pila en posts superiores*

Ejemplo ilustrado:

Tras unos cuantos algoritmos que cubren el uso de casi todas las funciones explicadas en la teoría. Paso a la explicación simple de algunos algoritmos estándar.

BUSQUEDA DE DATOS:

Búsqueda Lineal: Se trata de determinar si un elemento x está en un vector, para ello buscaremos una posición pos donde se encuentre ese elemento. (Dado un vector a de n elementos se debe cumplir que a(pos)==x)
La búsqueda lineal consiste en recorrer el vector a hasta que encuentre el elemento, o bien hasta que acabe el recorrido (si no está).

Programa: Búsqueda_Lineal

Datos:
n: valor constante.
a: vector de tamaño n, tipo T (debe tener el mismo tipo que x, para poder poner "x" como el dato que queremos buscar dentro del vector)
x: variable de tipo T
pos: número entero
encontrado: variable booleana.


Búsqueda lineal con centinela: Este método es parecido al anterior, y se basa en dimensionar el vector a una dimensión más que las definidas en el tamaño del vector. Esta posición se va a utilizar para introducir el elemento a buscar. De esta forma, nos aseguraremos que siempre va a estar, con el objeto de simplificar las condiciones del proceso repetitivo.

Programa: Busqueda_centinela

Datos:
n: valor constante
a: vector de tamaño n+1 de tipo T
x: variable de tipo T
encontrado: variable booleana


Búsqueda Dicotómica: Si los elementos del vector están ordenados bien de forma creciente o decreciente, no es necesario examinar todos los elementos, ya que comparando el valor buscado x con el valor central, se puede eliminar la búsqueda en una de las dos mitades, con lo cual el algoritmo resulta mucho más rápido. Supondremos que tenemos el vector ordenado en sentido creciente.
Si en cada paso del algoritmo comparamos el valor de x como el de la posición central (k), podemos obtener lo siguiente:

Caso 1: Que a(k) == x -> Acaba la búsqueda y el elemento está en k.
Caso 2: Que a(k) > x -> Eliminamos la parte del vector superior a k.
Caso 3: Que a(k) < x -> Eliminamos la parte del vector inferior a k.

Programa: Busqueda_Dicotomica

Datos:
izq, der: variables que delimitarán la dimensión del vector en la que estamos buscando. Servirán para ir recortando la búsqueda según el resultado de la comparación de a(k) con x.
a: vector de n elementos de tipo T
x: variable de tipo T


ORDENACIÓN DE DATOS:

Generalmente se considera ordenar con reorganizar un conjunto dado de objetos. Por ejemplo, los elementos de un vector en una secuencia especificada. El objetivo es facilitar la búsqueda de los elementos del conjunto ordenado. En particular vamos a practicar la ordenación a los elementos de un vector n>0 elementos de un tipo ordenable, así, los elementos del vector son a(n), deberemos encontrar una permutación de los mismos tal que: a(b1) <= a(b2) ... <= a(bn)

La primera condición a imponer a los métodos de ordenación de vectores es la utilización económica de la memoria disponible, esto implica que las permutaciones de elementos con vista a su ordenación, debe realizarse usando el espacio ocupado por el vector.

Los métodos que trasladan los elementos de un vector a otro no tienen interés (ya que implicaría duplicar el espacio necesario para realizar la operación).

Ordenación por inserción directa:
Para realizar este algoritmo partimos de la siguiente situación hipotética. (NOTA: Nunca se dará esta situación, esto solo sirve para considerar el programa tanto desde el comienzo, como durante el proceso intermedio)

La sección [1, i-1] está ordenada, pero no se asegura que los elementos estén en la posición final de ordenación, a esto se le llama ordenación no clasificada.

Para extender la ordenación al elemento i deberemos insertar el mismo en la posición correspondiente de la sección a(1...i)

Concluimos pues que necesitaremos:

** Extender la ordenación de la sección a**

Una posibilidad sería esta:

(Nótese que usamos uno de los algoritmos de búsqueda tratados anteriormente para buscar la posición correcta del elemento a ordenar.)


Esta disposición es correcta (y si no lo es, corregidme, que os lo agradeceré), pero no es lo más eficiente, aquí he introducido el algoritmo de búsqueda tal cual, para que pudieseis ver facilmente un ejemplo de su utilidad.

Ahora que ya tenemos el algoritmo planteado, vamos a hacerlo más eficiente. Para ello, intentaremos meter ambos bucles en uno. Para ello debemos tener en cuenta que la búsqueda y ordenación de los elementos se pueda hacer de forma simultánea y no en bucles separados. Para conseguir esto, ambos bucles deberían realizarse en el mismo sentido.

Teniendo en cuenta que el desplazamiento en sentido inverso es más simple en el proceso de desplazamiento de datos, mientras que las búsqueda se hace de forma análoga en un sentido u otro, es preferible modificar el algoritmo de ésta.


Si se compara este bucle con el desplazamiento de elementos, se puede observar lo siguiente.

1.- La variable de control de ambos comienza y termina con el mismo valor y i - 1, el correspondiente al valor de inserción.
2.- En ambos casos, la variable se modifica en cada paso de la misma forma, decrementándola, por tanto, ambos ejecutan el mismo númeor de veces. Con los mismos valores de la variable de control.
En consecuencia, las dos variables, y los dos algoritmos pueden combinarse en uno solo.


Quedándonos como resultado el programa final:

Programa: Ordenación_inserción_directa

Datos:
n: constante
a: vector de tamaño n tipo T
x: var de tipo T
encontrado: var lógica (booleana)
pos, i: nº enteros.


Ordenación por selección directa: Partimos del supuesto de que tenemos una sección (1 ... i-1) ordenada y clasificada (recordad que esto era para considerar ambos casos de algoritmo durante inicio y proceso).
El objetivo en ese caso sería extender la ordenación al elemento i del vector. Para ello buscamos el mínimo de la sección (i ... n)

Programa: Inserción_Directa

Datos:
n: cte
a: vec de n elementos tipo T
x: var tipo T
i,j,pos: nºentero

Algoritmo:


Ordenación por intercambio (o método de la burbuja):
Al igual que antes, suponemos que está ordenada y clasificada la sección a(1 ... i-1) y queremos extender la ordenación al elemento i.

La diferencia con el método anterior es que aquí no se busca el mínimo, sino que este se lleva hasta la posición i mediante intercambios de pares de elementos adyacentes del vector.

Si los elementos se consideran burbujas en un depósito de agua, con pesos acordes a sus valores, en cada pasada sobre el vector, asciende una burbuja hasta su posición correspondiente. (También hay la posibilidad de que otras se acerquen a su posición final, por ello hay casos en los que esta ordenación acelera el proceso)


A que éste ha parecido sencillito? Pues es lo que parece. (Cuando lo saqué por primera vez pensé que tenía que haber algo mal porque era demasiado sencillo. Pero no, es correcto. ^^