ESTRUCTURA Y ORGANIZACION DE DATOS

INTRODUCCIÓN (COMPLEJIDAD)

El ordenamiento de burbuja es uno de los más simples algoritmos de ordenamiento, pero NO ES EL MÁS EFICIENTE.

FUNCIONAMIENTO

Este algoritmo coloca los elementos en orden creciente, sucesivamente comparando los elementos adyacentes, intercambiándose entre ellos si el orden está de forma incorrecta. Para llevar a cabo el ordenamiento de burbuja, se lleva a cabo una operación básica, cambiando el elemento más grande, por el más pequeño que lo sigue. Se pueden imaginar los elementos en la lista, colocados en una columna

PSEUDOCÓDIGO (ALGORITMO)

procedure bubblesort(a1, …, an : números reales con n >= 2)
for i := 1 to n – 1
for j := 1 to n – i
if aj > aj+1 then intercambiar
aj
and aj+1
{a1, …, an está en orden creciente}

EJEMPLO

Los pasos de este algoritmo están ilustrados en la figura de arriba. Empezando por comparar los dos primeros elementos 3 y 2. Porque 3 > 2, intercambiando 3 y 2, produciendo la lista 2, 3, 4, 1, 5. Porque 3 < 4, continua comparando 4 y 1. Porque 4 > 1, intercambiando 1 y 4, produciéndola lista 2, 3, 1, 4, 5. Porque 4 < 5, el primer paso está completo. El primer paso garantiza que el elemento más grande, 5, está en la correcta posición.

El segundo paso empieza comparando2 y 3. Porque estos están en correcto orden, 3 y 1 son comparados. Porque 3 > 1, estos números son intercambiados, produciendo 2, 1, 3, 4, 5. Porque 3 < 4, estos números están en orden correcto. No es necesario hacer más comparaciones en este paso, porque 5 está en la correcta posición. El segundo paso garantiza que los dos elementos más grandes, 4 y 5, están en la posición correcta.

El tercer paso empieza comparando 2 y 1. Estos son intercambiados porque 2 > 1, produciendo 1, 2, 3, 4, 5. Porque 2 < 3, estos dos elementos están en la posición correcta. No es necesario hacer más comparaciones en este paso porque 4 y 5 están ubicados en la posición correcta. El tercer paso garantiza que los tres elementos más grandes 3, 4 y 5, están en su posición correcta.

El cuarto paso consiste de una comparación entre 1 y 2. Porque 1 < 2 estos elementos están en orden correcto. Así termina el ordenamiento de burbuja.

ALGORITMO DE ORDENAMIENTO RAPIDO O QUICKSORT

Este algoritmo esta basado en la tecnica divide y vencerás (consiste en dividir el problema en pequeños subproblemas mas sencillos para luego estos ser resueltos con un calculo mas sencillo) asi crearemos arreglos mas pequeños para ordenar estos.

Los pasos que realiza este algoritmo son:

Selecciona un valor del arreglo como pivote es decir un numero por el cual todos los elementos van a ser comparados.
se realizan dos búsquedas: una de izquierda a derecha, buscando un elemento mayor que el pivote, y otra de derecha a izquierda, buscando un elemento menor que el pivote. Cuando se han encontrado los dos, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
luego se organizan los subarreglos que quedaron a mano derecha y izquierda.

Ejemplo:

Tenemos un arreglo que esta definido con los valores {22,40,4,10,12,35} los pasos en quicksort para arreglarlo son los siguientes:

se toma como pivote el numero 22 recuerden puede ser cualquier numero.
la búsqueda de izquierda a derecha encuentra el valor 40 que es mayor a pivote y la búsqueda de derecha a izquierda encuentra el valor 35 no lo toma porque es mayor a el numero pivote (recuerden que la búsqueda de derecha a izquierda busca los menores) entonces continua y encuentra a 12 que es menor que el pivote y se intercambian el resultado seria {21,12,4,10,40,35}
si seguimos la búsqueda la primera encuentra el valor 40, y la segunda el valor 10,pero ya se han cruzado,así que paramos. Para terminar la división, se coloca el pivote en su lugar el numero encontrado por la segunda busqueda, el 10 quedando: {10,12,4,22,40,35}
ahora tenemos dividido el arreglo en dos arreglos mas pequeños que son {10,12,4} y el {40,35}, y en ellos se repetirá el mismo proceso.

PSEUDOCODIGO

  Principal
    variables A: arreglo[1..100] entero
    variables i,j,central:entero
    variables primero, ultimo: entero
    para i = 1 hasta 100
            leer(A[i])
        Fin para
    primero = 1
    ultimo = 100
    qsort(A[],100)
Fin
Funcion qsort(primero, ultimo:entero)
        i = primero
        j = ultimo
        central = A[(primero,ultimo) div 2]
        repetir
                mientras A[i]
                        j = j - 1
                    fin mientras
                si i < = j
                        aux = A[i]
                        A[j] = A[i]
                        A[i] = aux
                        i = i + 1
                        j = j - 1
                    fin si
            hasta que i > j
        si primero < j
                partir(primero,j)
            fin si
        si i < ultimo
                partir(i, ultimo)
            fin si
    fin funcion qsort

IMPLEMENTACION EN JAVA

public void ordenarQuicksort(int[] vector, int primero, int ultimo){
int i=primero, j=ultimo;
int pivote=vector[(primero + ultimo) / 2];
int auxiliar;
do{
while(vector[i]<pivote) i++;
while(vector[j]>pivote) j--;
if (i<=j){
auxiliar=vector[j];
vector[j]=vector[i];
vector[i]=auxiliar;
i++;
j--;
}
} while (i<=j);
if(primero<j) ordenarQuicksort(vector,primero, j);
if(ultimo>i) ordenarQuicksort(vector,i, ultimo);
}
ALGORITMO DE ORDENAMIENTO SHELLSORT
El Shell Sort es una generalización del ordenamiento por inserción , teniendo en cuenta dos observaciones:

El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.

El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.

La sucesión propuesta por Shell:
Peor Caso = O( n^2).
Caso Medio = O(n^2 ).
Con la sucesión
: 2^k-1
Peor Caso = O( n^1.5)

Caso Medio = O( n^1.5 )
Con la sucesión :(4^k+1+3 2^k+1)

Peor Caso = O(n^1.333)
Caso Medio=O(n^1.166)

El mejor caso sería O(n logn).

Método:

public static void shellSort( int a[ ])
{
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < a.length; i++ ){
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){
a[ j ] = a[ j - gap ];
}

Ejemplo JAVA:
public class ShellSort {

public static void main(String args[]){
int arrayEntrada[]={321, 123, 213, 234, 1, 4, 5, 6}; Este es el array de elementos que vamos a ordenar

shellSort(arrayEntrada); llamada al metodo shellSort
for (int i=0;i < arrayEntrada.length;i++){ Este bucle imprime el contenido del array
System.out.print(arrayEntrada[i]+" ");
}fin del for
}fin del main

public static void shellSort( int a[ ]){
for( int gap = a.length / 2; gap > 0; gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) ){
for( int i = gap; i < a.length; i++ ){
int tmp = a[ i ];
int j;
for(j = i; j >= gap && tmp < a[ j - gap ] ; j -= gap ){
a[ j ] = a[ j - gap ];
}
a[ j ] = tmp;
}
}
}
}class ShellSort
ORDENAMIENTO RADIX

Este ordenamiento se basa en los valores de los dígitos reales en las representaciones de posiciones de los números que se ordenan.
Por ejemplo el número 235 se escribe 2 en la posición de centenas, un 3 en la posición de decenas y un 5 en la posición de unidades.

Reglas para ordenar.

Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números.

El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales).

Este mismo principio se toma para Radix Sort, para visualizar esto mejor tenemos el siguiente ejemplo. En el ejemplo anterior se ordeno de izquierda a derecha. Ahora vamos a ordenar de derecha a izquierda.
Archivo original.

25 57 48 37 12 92 86 33

Asignamos colas basadas en el dígito menos significativo.

Parte delantera Parte posterior0
1
2 12 92
3 33
4
5 25
6 86
7 57 37
8 48
9
10
Después de la primera pasada:

12 92 33 25 86 57 37 48

Colas basadas en el dígito más significativo.

Parte delantera Parte posterior0
1 12
2 25
3 33 37
4 48
5 57
6
7
8 86
9 92
10

Archivo ordenado: 12 25 33 37 48 57 86 92

A S O R T I N G E X A M P L E
A E O L M I N G E A X T P R S
A E A E G I N M L O
A A E E G
A A
A A
E E G
E E
I N M L O
L M N O
L M
N O
S T P R X
S R P T
P R S
R S

#include 
#include  $#define NUMELTS 20

void radixsort(int x[], int n)
{
  int front[10], rear[10];
  struct {
    int info;
    int next;
  } node[NUMELTS];
  int exp, first, i, j, k, p, q, y;

  /* Inicializar una lista viculada */
  for (i = 0; i < n-1; i++) {
    node[i].info = x[i];
    node[i].next = i+1;
  } /* fin del for */
  node[n-1].info = x[n-1];
  node[n-1].next = -1;
  first = 0; /*first es la cabeza de la lista vinculada */
  for (k = 1; k < 5; k++) {
    /* Suponer que tenemos n£meros de cuatro dÁgitos */
    for (i = 0; i < 10; i++) {
      /*Inicializar colas */
      rear[i] = -1;
      front[i] = -1;
    } /*fin del for */
    /* Procesar cada elemento en la lista */
    while (first != -1) {
      p = first;
      first = node[first].next;
      y = node[p].info;
      /* Extraer el kâsimo dÁgito */
      exp = pow(10, k-1); /* elevar 10 a la (k-1)âsima potencia */
      j = (y/exp) % 10;
      /* Insertar y en queue[j] */
      q = rear[j];
      if (q == -1)
 front[j] = p;
      else
 node[q].next = p;
      rear[j] = p;
    } /*fin del while */

    /* En este punto, cada registro est  en su cola bas ndose en el dÁgito k
       Ahora formar una lista £nica de todos los elementos de la cola. Encontrar
       el primer elemento. */
    for (j = 0; j < 10 && front[j] == -1; j++);
      ;
    first = front[j];

    /* Vincular las colas restantes */
    while (j <= 9) {  /*Verificar si se ha terminado */
      /*Encontrar el elemento siguiente */
      for (i = j+1; i < 10 && front[i] == -1; i++);
 ;
      if (i <= 9) {
 p = i;
 node[rear[j]].next = front[i];
      } /* fin del if */
      j = i;
    } /* fin del while */
    node[rear[p]].next = -1;
  } /* fin del for */

  /* Copiar de regreso al archivo original */
  for (i = 0; i < n; i++) {
    x[i] = node[first].info;
    first = node[first].next;
  } /*fin del for */
} /* fin de radixsort*/


int main(void)
{
  int x[50] = {NULL}, i;
  static int n;

  printf("\nCadena de n£meros enteros: \n");
  for (n = 0;; n++)
    if (!scanf("%d", &x[n])) break;
  if (n)
    radixsort (x, n);
  for (i = 0; i < n; i++)
    printf("%d ", x[i]);
  return 0;
}$

Estado de la lista

i	Node[i].info	Node[i].nextInicialización K = 1 K = 2 K = 3
0	65	1	3	1	2
1	789	2	-1	-1	-1
2	123	3	0	3	3
3	457	-1	1	0	1

rear = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
2 0 3 1
front = {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1}
2 0 3 1

k = 1
p = 0 p = 1 p = 2 p = 3
first = 1 first = 2 first = 3 first = -1
y = 65 y = 789 y = 123 y = 457
exp = 1 exp = 1 exp = 1 exp = 1
j = 5 j = 9 j = 3 j = 7
q = -1 q = -1 q = -1 q = -1
si q == -1 si q == -1 si q == -1 si q == -1
front[5] = 0 front[9] = 1 front[3] = 2 front[7] = 3
rear[5] = 0 rear[9] = 1 rear[3] = 2 rear[7] = 3

 j = 3
 first = 2
 while ( j <= 9)
  i = 5
  si i <= 9
                     p = 5
                     node[2].next = 0
                     j = 5
               i = 7
                 si i <= 9
                     p = 7
                     node[0].next = 3
                     j = 5
               i = 9
                 si i <= 9
                     p = 9
                     node[2].next = 1
                     j = 9
 fin del while
 p = 9
 node[1].next = -1

Características.

Debido a que el ciclo for (k = 1; k <= m; k++) externo se recorre m veces (una para cada dígito) y el ciclo interior n veces (una para cada elemento en el archivo) el ordenamiento es de aproximadamente (m*n).

Si las llaves son complejas (es decir, si casi cada número que puede ser una llave lo es en realidad) m se aproxima a log n, por lo que (m*n) se aproxima a (n log n).

Si la cantidad de dígitos es grande, en ocasiones es más eficiente ordenar el archivo aplicando primero el ordenamiento de raíz a los dígitos más significativos y después utilizando inserción directa sobre el archivo ordenado.

Ventajas.

El ordenamiento es razonablemente eficiente si el número de dígitos en las llaves no es demasiado grande.

Si las máquinas tienen la ventaja de ordenar los dígitos (sobre todo si están en binario) lo ejecutarían con mucho mayor rapidez de lo que ejecutan una comparación de dos llaves completas.

ORDENAMIENTO QUICKSORT

El método de ordenamiento Quick Sort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Es también conocido con el nombre del método rápido y de ordenamiento por partición, en el mundo de habla hispana.

Este método es una mejora sustancial del método de intercambio directo y recibe el nombre de Quick Sort por la velocidad con que ordena los elementos del arreglo. Su autor C.A. Hoare lo bautizó así.

La idea central de este algoritmo consiste en los siguiente:

Se toma un elemento x de una posición cualquiera del arreglo.

Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.

Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo.

Ejemplo:
A: 15,67,08,16,44,27,12,35
Se selecciona A[i]  x=15

Primera pasada (DER-IZQ)
A[8] >= x 35 >= 15 No hay intercambio
A[7] >= x 12 >= 15 Si hay intercambio

A: 12,67,08,16,44,27,15,35

(IZQ-DER)
A[2] < = X 67 < = 15 Si hay intercambio

A:12,15,08,16,44,27,67,35

2da. Pasada (DER-IZQ)
A[6] >= x 27 >= 15 No hay intercambio
A[5] >= x 44 >= 15 No hay intercambio
A[4] >= x 16 >= 15 No hay intercambio
A[3] >= x 08 >= 15 Si hay intercambio

A: 12,08,15,16,44,27,67,35

Como el recorrido de izquierda a derecha debería iniciarse en la misma posición 
donde se encuentra el elemento x, el proceso se termina ya que el elemento x, se 
encuentra en la posición correcta.

A: 12, 08, 15, 16, 44, 27, 67, 35
1er 2do Conjunto
Conjunto
16, 44, 27, 67, 35
x16

(DER-IZQ)
A[8]>=x No hay intercambio
A[7]>=x No hay intercambio
A[6]>=x No hay intercambio
A[5]>=x No hay intercambio

A: 12, 08, 15, 16, 44, 27, 67, 35
xß44

(DER-IZQ)
A[8]>= x Si hay intercambio

A: 12, 08, 15, 16, 35, 27, 67, 44

(IZQ-DER)
A[6] < = x No hay intercambio
A[7] < = x Si hay intercambio
12, 08, 15, 16, 35, 27, 44, 67
12, 08, 15, 16, 35, 27, 44, 67
35, 27, 44, 67
xß35

(DER-IZQ)
A[8] >= x No hay intercambio
A[7] >= x No hay intercambio
A[6] >= x Si hay intercambio
12, 08, 15, 16, 27, 35, 44, 67
12,08
xß12

(DER-IZQ)
A[2]>=x Si hay intercambio

EL VECTOR ORDENADO:
08,12,15,16,27,35,44,67

Análisis

Diversos estudios realizados sobre el comportamiento del mismo demuestran que si se escoge en cada pasada el elemento que ocupa la posición central del conjunto de datos a analizar, el número de pasadas necesarias para ordenar es del orden de Log n. Respecto al número de comparaciones, si el tamaño del arreglo es una potencia de 2, en la primera pasada realizará (n-1) comparaciones, en la 2ª pasada realizará (n-1)/2 comparaciones, pero en 2 conjuntos diferentes, en la tercera pasada realizará (n-1)/4 comparaciones pero en 4 conjuntos diferentes y así sucesivamente.

Por lo tanto: C = (n-1) + 2(n -1)/2 + 4(n - 1)/4 + ....... + (n - 1)(n - 1)/(n - 1)

Lo cual es lo mismo que: C= (n - 1) + (n- 1) + ....... + (n - 1)

ORDENAMIENTO SHELLSORT

El método Shell (en honor a su descubridor) mejor del método de inserción simple ordenando subarrreglos del arreglo original en forma separada. Para crear estos nuevos subarreglos, se toman elementos saltados del areglo original en relación a incrementos predeterminados.

Por ejemplo suponiendo un arreglo X, y tomando un incremento (salto) igual a 5, se generarían los siguientes subarreglos:

Subarreglo 1:	X[0] X[5] X[10] ...
Subarreglo 2:	X[1] X[6] X[11] ...
Subarreglo 3:	X[2] X[7] X[12] ...
Subarreglo 4:	X[3] X[8] X[13] ...
etc.

Con un salto igual a 3 se obtendrían:

Subarreglo 1:	X[0] X[3] X[6] ...
Subarreglo 2:	X[1] X[4] X[7] ...
Subarreglo 3:	X[2] X[5] X[8] ...
Subarreglo 4:	X[3] X[6] X[9] ...
etc.

Lo habitual es tomar un valor de incremento, y ordenar mediante inserción los subarreglos obtenidos. Luego se toma otro valor de incremento, y se ordenan ahora los asubarreglos generados a partir de este incremento. Y así sucesivamente para diferentes valores de incremento o salto.

Supongamos que tenemos el siguienmte arreglo:

y que se elige la secuencia de incrementos (5,3,1), los archivos a ordenar para esta secuencia serían:

con incremento = 5:

(x[0], x[5])

(x[1], x[6])

(x[2], x[7])

(x[3])

(x[4])

con incremento = 3:

(x[0], x[3], x[6])

(x[1], x[4], x[7])

(x[2], x[5])

con incremento = 1:

(x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7])

A continuación se muestra el resultado del ordenamiento Shell sobre este arreglo. Las líneas indican los subarreglos que se procesan por separado.

arreglo original	o	25	57	48	37	12	92	86	33
paso 1 salto = 5	o	25	57	48	37	12	92	86	33



paso 2 salto = 3		25	57	33	37	12	92	86	48



paso 3 salto = 1		25	12	33	37	48	92	86	57

Arreglo ordenado		25	12	33	37	48	57	86	92

Habitualmente lo que se hace es generar un arreglo que contenga los incrementos. Suponiendo que se tiene un arreglo con los incrementos, a continuación se muestra un ejemplo del método Shell en el siguiente fragmento de código en C:

.
.
.
int X[n]; /* será el número de elementos del arreglo */
int i,j,K /* K será el elemento que se inserte para mantener el orden */
int incre[numinc]; /* incre contiene la secuencia de incrementos,
           y numinc es el número total de incrementos */
int salto, numi;
.
.
.
for (numi=0;numi<numinc;numi++)
{
 salto = incre[numi]; /* salto es el incremento actual */
 for (j=salto;j<n;j++)
 { 
  K=X[j];
  for(i=j-salto;i>=0&&K<X[i];i-=salto)
  {
   X[i+salto]=X[i];
   X[i]=K;
  }
 }
}