• Categories
• Algoritmos
• Estructura de datos de matriz
• Lógica matemática
• Programación de computadoras
• Ingeniería informática

Citation preview

UNIVERSIDAD NACIONAL MICAELA BASTIDAS DE APURÍMAC FACULTAD DE INGENIERÍA ESCUELA ACADÉMICO PROFESIONAL DE INGENIERÍA INFORMÁTICA Y SISTEMAS

CURSO: ALGORÍTMICA II ALGORITMOS DE ORDENAMIENTO ING. FRANCISCO CARI INCAHUANACO

ABANCAY – APURÍMAC 2018

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

ÍNDICE Pág. I.

BUBBLE SORT (BURBUJA) ............................................................................................................... 1

1.1

Concepto ..................................................................................................................................... 1

1.2

Descripción.................................................................................................................................. 1

1.3

Algoritmo de Burbuja ................................................................................................................. 1

1.4

Pseudocódigo de Algoritmo Burbuja ......................................................................................... 1

1.5

Algoritmo de Burbuja en C ++ .................................................................................................... 2

1.6

Análisis del Algoritmo ................................................................................................................. 2

1.7

Ventajas y Desventajas ............................................................................................................... 2

II.

ORDENAMIENTO POR SELECCIÓN (SELECTION SORT) ................................................................... 3

2.1

Definición .................................................................................................................................... 3

2.2

Su funcionamiento:..................................................................................................................... 3

2.3

Características ............................................................................................................................. 3

2.4

Pseudocodigo .............................................................................................................................. 3

2.5

Análisis del Costo Computacional .............................................................................................. 4

2.6

Estabilidad, Ventajas y Desventajas........................................................................................... 4

III.

COUNTING SHORT ...................................................................................................................... 7

3.1

Definición .................................................................................................................................... 7

3.2

Tipos de ordenamientos por cuentas ........................................................................................ 7

3.3

Análisis del algoritmo ................................................................................................................. 7

3.4

Pseudocódigo .............................................................................................................................. 8

3.5

código en c++ .............................................................................................................................. 9

IV.

QUICK SORT .............................................................................................................................. 11

4.1

Definición .................................................................................................................................. 11

4.2

El ordenamiento de QuickSort ................................................................................................. 11

4.3

Pseudocodigo ............................................................................................................................ 13

4.4

Codificación en C++ ................................................................................................................. 14

4.5

Análisis del Algoritmo ............................................................................................................... 15

4.6

Técnicas de elección del Pivote ................................................................................................ 16

4.7

Técnicas de Reposicionamiento ............................................................................................. 16

V.

MERGE SORT ................................................................................................................................. 17

5.1

Definición .................................................................................................................................. 17

5.2

Paso para realizar este algoritmo............................................................................................. 17

5.3

Descripción................................................................................................................................ 17

5.4

Pseudocódigo ............................................................................................................................ 17

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

5.5

Ventajas y Desventajas ............................................................................................................. 19

5.6

Conclusiones ............................................................................................................................. 19

VI.

SHELL SORT ............................................................................................................................... 20

6.1

Definición .................................................................................................................................. 20

6.2

Análisis del Algoritmo ............................................................................................................... 20

6.3

Ventajas y desventajas ............................................................................................................. 20

6.4

Complejidad .............................................................................................................................. 20

6.5

Complejidad Experimental ....................................................................................................... 21

6.6

Pseudocódigo ............................................................................................................................ 22

6.7

Código en C++ ........................................................................................................................... 22

6.8

Conclusiones ............................................................................................................................. 24

VII.

SHAKER SORT ............................................................................................................................ 25

7.1

Definición .................................................................................................................................. 25

7.2

Ventajas y Desventajas ............................................................................................................. 27

7.3

Pseudocódigo ............................................................................................................................ 27

7.4

Código en C++ ........................................................................................................................... 28

7.5

Conclusiones ............................................................................................................................. 29

VIII.

HEAP SORT ................................................................................................................................ 30

8.1

Definición .................................................................................................................................. 30

8.2

¿Qué se Heap Sort?................................................................................................................... 30

8.3

¿Cómo funciona el Heap Sort ? ................................................................................................ 30

8.4

Montículo .................................................................................................................................. 30

8.5

Operaciones con Montículos .................................................................................................... 30

8.6

Complejidad Computacional .................................................................................................... 31

8.7

Código en C++ ........................................................................................................................... 31

IX.

INSERTION SORT(INSERIÓN DIRECTA Y INSERCIÓN BINARIA) ................................................ 33

9.1

Inserción Directa ....................................................................................................................... 33

9.2

El Funcionamiento .................................................................................................................... 33

9.3

Ejemplo de Inserción Directa ................................................................................................... 33

9.4

Código en C++ ........................................................................................................................... 34

9.5

Ventajas y Aplicaciones ............................................................................................................ 35

9.6

Inserción Binaria ....................................................................................................................... 35

9.7

Clasificaciones ........................................................................................................................... 35

9.8

Características ........................................................................................................................... 35

9.9

Análisis ...................................................................................................................................... 36

9.10

Pseudocódigo de Inserción Binaria .......................................................................................... 37

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

9.11

Código en C++ ........................................................................................................................... 38

9.12

Complejidad .............................................................................................................................. 38

9.13

Conclusiones ............................................................................................................................. 39

9.14

Recomendaciones ..................................................................................................................... 39

X.

MÉTODO DE ORDENAMIENTO RADIX SORT ................................................................................ 40

10.1

Historia ...................................................................................................................................... 40

10.2

Método De Ordenamiento Radix Sort ..................................................................................... 40

10.3

¿En qué consiste este método? ................................................................................................ 40

10.4

Características ........................................................................................................................... 40

10.5

Ordenamiento por radix intercambio. .................................................................................... 40

10.6

Ordenamiento por radix directo. ............................................................................................. 41

10.7

Clasificación .............................................................................................................................. 41

10.8

¿Cómo funciona el método de ordenamiento Radix Sort? ..................................................... 42

10.9

Código en C++ ........................................................................................................................... 42

10.10

El procedimiento para aplicar el algoritmo de Radix. ......................................................... 44

10.11

Ventajas y desventajas de Radix Sort .................................................................................. 45

10.12

Conclusión ............................................................................................................................. 45

BIBLIOGRAFÍA .................................................................................................................................... 46

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

INTRODUCCIÓN Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar información de una manera especial basándonos en un criterio de ordenamiento. En la computación el ordenamiento de datos cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. En este caso, nos sirven para ordenar vectores o matrices con valores asignados aleatoriamente. Nos centraremos en los métodos más populares, analizando la cantidad de comparaciones que realizan, el tiempo que demora y la complejidad de cada algoritmo. El propósito principal de un ordenamiento es el de facilitar las búsquedas de los registros del conjunto ordenado. Un ordenamiento es conveniente usarlo cuándo se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo. Es importante destacar que existen diferentes técnicas de ordenamiento como lo es; el Método Burbuja, que consiste en comparar pares de valores de llaves; Método Selección, el cual consiste en encontrar el menor de todos los elementos del arreglo e intercambiarlo; y entre otros métodos. Esta guía nos permitirá conocer más a fondo cada método de ordenamiento, desde uno que es más simple hasta el más complejo. Se realizaran comparaciones en tiempo de ejecución, pre-requisitos de cada algoritmo, funcionalidad, alcance, etc.

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

ALGORTIMOS DE MÉTODOS DE ORDENAMIENTO I.

BUBBLE SORT (BURBUJA)

1.1 Concepto La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Revisa cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden incorrecto. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo. Dado que solo usa comparaciones para operar elementos, se lo considera un algoritmo de comparación, siendo el más sencillo de implementar. Este algoritmo es esencialmente un algoritmo de fuerza bruta lógica. 1.2 Descripción Este es el algoritmo más sencillo probablemente, ideal para empezar, consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. Un ejemplo del algoritmo Vamos a ver un ejemplo. Esta es nuestra lista: 4 - 3 - 5 - 2 - 1 Tenemos 5 elementos, es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos: 3-4-5-2-1 Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos: 3-4-2-5-1 Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente: 3-4-2-1-5 Repitiendo este proceso vamos obteniendo los siguientes resultados: 3-2-1-4-5 2-1-3-4-5 1-2-3-4–5 1.3 Algoritmo de Burbuja Generalizando el proceso de ordenación se obtiene el siguiente pseudocódigo estructurado para el algoritmo de burbuja. i –Variable ordenaciones j -Variable comparaciones n - Número de elementos del vector (en C representa el índice mayor) 1.4

Pseudocódigo de Algoritmo Burbuja inicio desde i ← 1 hasta n-1 hacer desde j ← 1 hasta n-i hacer si elemento[j] > elemento[j+1] entonces

Ing. Francisco Cari I.

1

Escuela Académico Profesional de Ingeniería Informática y Sistemas – UNAMBA

aux ← V*j+ V*j+ ← V*j+1+ V*j+1+ ← aux fin_si fin_desde fin_desde fin 1.5

Algoritmo de Burbuja en C ++ int v[]={3, 34, 1, 53, 15, 6}; int j,i, aux; // Ordenación for(i=0; i