Programacion C++: METODOS DE ORDENAMIENTO:

MÉTODOS DE ORDENAMIENTO:

· ORDENAMIENTO POR SELECCIÓN:

· ORDENAMIENTO POR INSERCIÓN DIRECTA:

· ORDENAMIENTO POR INSERCIÓN BINARIA:

· ORDENAMIENTO SHELL SORT:

· ORDENAMIENTO QUICK SORT:

· ORDENAMIENTO HEAP SORT:

ORDENAMIENTO:

ES LA OPERACIÓN DE ARREGLAR LOS REGISTROS DE UNA TABLA EN ALGÚN ORDEN SECUENCIAL DE ACUERDO A UN CRITERIO DE ORDENAMIENTO. EL ORDENAMIENTO SE EFECTÚA CON BASE EN EL VALOR DE ALGÚN DATO EN UN REGISTRO. EL PROPÓSITO PRINCIPAL DE UN ORDENAMIENTO ES EL DE FACILITAR LA BÚSQUEDA DE LOS MIEMBROS DEL CONJUNTO ORDENADO.

EL ORDENAR UN GRUPO DE DATOS SIGNIFICA MOVER LOS DATOS O SUS DIFERENCIAS PARA QUE QUEDEN EN UNA SECUENCIA TAL QUE REPRESENTE UN ORDEN, EL CUAL PUEDE SER NUMÉRICO, ALFABÉTICO, O INCLUSO ALFANUMÉRICO, ASCENDENTE O DESCENDIENTE.

ORDENAMIENTO POR SELECCIÓN:

DESCRIPCION:

· BUSCAS EL ELEMENTO MÁS PEQUEÑO DE UNA LISTA.

· LO INTERCAMBIAS CON EL ELEMENTO UBICADO EN LA PRIMERA POSICION DE LA LISTA.

· BUSCAS EL SEGUNDO ELEMENTO MÁS PEQUEÑO DE LA LISTA.

· SE INTERCAMBIA CON EL ELEMENTO Q OCUPA EL SEGUNDO LUGAR DE LA LISTA.

· REPITES ESTE PROCESO HASTA UE HALLA TERMINADO DE ORDENAR LALISTA..!

ANÁLISIS DE ALGORITMO:

REQUERIMIENTO DE MEMORIA: AL IGUAL QUE EL ORDENAMIENTO BURBUJA, ESTE ALGORITMO SOLO NECESITA UNA VARIABLE ADICIONAL PARA REALIZAR LOS INTERCAMBIOS.

TIEMPO DE EJECUCIÓN:

EL CICLO EXTERNO SE EJECUTA N VECES PARA UNA LISTA DE UN N ELEMENTOS. CADA BÚSQUEDA REQUIERE COMPARAR TODOS LOS ELEMENTOS NO CLASIFICADOS.

VENTAJAS:

· • FÁCIL IMPLEMENTACIÓN

· • NO REQUIERE MEMORIA ADICIONAL

· •RENDIMIENTO CONSTANTE: POCA DIFERENCIA ENTRE EL PEOR Y EL MEJOR

DESVENTAJAS:

· • LENTO.

· • REALIZA NUMEROSAS COMPARACIONES

CODIFICACIÓN EN C++.

ORDENAMIENTO POR INSERCIÓN DIRECTA:

DESCRIPCIÓN:

EL ALGORITMO DE ORDENACIÓN POR MÉTODO DE INSERCIÓN DIRECTA ES UN ALGORITMO RELATIVAMENTE SENCILLO Y SE COMPORTA RAZONABLEMENTE BIEN EN GRAN CANTIDAD DE SITUACIONES.

DE ESTOS TRES ALGORITMOS ES EL Q MEJOR RESULTADO DE AFECTOS PRÁCTICOS. REALIZA UNA CANTIDAD E COMPARACIONES BASTANTE EQUILIBRADA CON RESPECTO A LOS INTERCAMBIOS, Y TIENE UN PAR DE CARACTERÍSTICAS QUE LO HACEN AVENTAJAR A LOS DOS EN LA MAYOR PARTE DE LAS SITUACIONES.

ESTE ALGORITMO SE BASA EN HACER COMPARACIONES, ASÍ QUE PAR QUE REALICE SU TRABAJO DE ORDENACIÓN SON IMPRESCINDIBLES DOS COSAS: UN ARRAY O ESTRUCTURA SIMILAR DE ELEMENTOS COMPARABLES Y UN CRITERIO CLARO DE COMPARACIÓN, TAL QUE DADOS LOS ELEMENTOS NOS DIGA SI ESTÁN EN ORDEN O NO. EN CADA ITERACIÓN DE SICLO EXTERNO LOS ELEMENTOS 0 A I FORMAN UNA LISTA ORDENADA.

ANÁLISIS DEL ALGORITMO:

ESTABILIDAD:

ESTE ALGORITMO NUNCA INTERCAMBIA REGISTROS CON CLAVES IGUALES. POR LO TANTO ES ESTABLE.

REQUERIMIENTOS DE MEMORIA:

UNA VARIABLE ADICIONAL PARA REALIZAR LOS INTERCAMBIOS.

TIEMPO DE EJECUCIÓN:

PARA UNA LISTA “N” ELEMENTOS EL CICLO EXTERNO SE EJECUTA N-1 VECES. EL CICLO INTERNO SE EJECUTA COMO MÁXIMO UNA VEZ EN AL PRIMERA ITERACIÓN, 2 VECES EN LA SEGUNDA, 3 VECES EN LA TERCERA, ETC...

VENTAJAS:

· • FÁCIL IMPLEMENTACIÓN.

· •REQUERIMIENTO MÍNIMO DE MEMORIA.

DESVENTAJAS:

· •LENTO

· •REALIZA NUMEROSAS COMPARACIONES.

CODIFICACIÓN EN C++.

MÉTODO DE ORDENACIÓN POR INSERCIÓN BINARIA:

ESTE MÉTODO ES UNA MEJORA DEL MÉTODO DE ASERCIÓN DIRECTA. PARA LOGRAR ESTA MEJORA SE RECURRE A UNA BÚSQUEDA BINARIA EN LUGAR DE UNA BÚSQUEDA SECUENCIAL PARA INSERTAR UN ELEMENTO EN LA PARTE IZQUIERDA DEL ARREGLO, QUE YA SE ENCUENTRA ORDENADO. EL RESTO DEL PROCEDIMIENTO ES SIMILAR AL DE INSERCIÓN DIRECTA, ES DECIR, SE REPITE ESTE MISMO PROCEDIMIENTO DESDE EL SEGUNDO TERMINO HASTA EN ULTIMO ELEMENTO.

CODIFICACIÓN EN C++.

ORDENAMIENTO POR EL MÉTODO DE SHEL:

ES UNA VERSIÓN MEJORADA DE EL MÉTODO DE INSERCIÓN DIRECTA. ESTE MÉTODO TAMBIÉN SE CONOCE CON EL NOMBRE DE INSERCIÓN CON INCREMENTOS DECRECIENTES. EN EL MÉTODO DE ORDENACIÓN POS INSERCIÓN DIRECTA CADA ELEMENTO SE COMPRARA POR SU UBICACIÓN CORRECTA EN EL ARREGLO, CON LOS ELEMENTOS QUE SE ENCUENTRAN EN LA PARTE IZQUIERDA DEL MISMO. SI EL ELEMENTO INSERTAR ES MAS PEQUEÑO QUE EL GRUPO DE ELEMENTOS QUE SE ENCUENTRAN A SU IZQUIERDA, ES NECESARIO EFECTUAR ENTONCES VARIAS COMPARACIONES ANTES DE SU UBICACIÓN.

SHELL PROPONE QUE LAS COMPARACIONES ENTRE ELEMENTOS SE EJECUTEN CON SALTOS DE MAYOR TAMAÑO PERO CON INCREMENTOS DECRECIENTES, ASÍ, LOS ELEMENTOS QUEDARAN ORDENADOS EN EL ARREGLO MAS RÁPIDAMENTE.

SHELL SOLO ES UNA GENERALIZACIÓN DEL ORDENAMIENTO POR INSERCIÓN, TENIENDO EN CUENTA DOS OBSERVACIONES:

1 EL ORDENAMIENTO POR INSERCIÓN ES EFICIENTE SI LA ENTRADA ESTA “CASI ORDENADA”

2 EL ORDENAMIENTO POR INSERCIÓN ES INEFICIENTE, EN GENERAL, PORQUE REMUEVE LOS VALORES SOLO 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 MAS GRANDES” HACIA SU POSICIÓN ESPERADA. LOS PASOS MÚLTIPLES SOBRE LOS DATOS SE HACEN CON TAMAÑOS DE ESPACIO CADA VEZ MAS PEQUEÑOS. EL ULTIMO PASO DE SHELLSORT ES UN SIMPLE ORDENAMIENTO POR INSERCIÓN, PERO PARA ENTONCES, YA ESTA GARANTIZADO QUE LOS DATOS EL VECTOR ESTÁN CASI ORDENADOS...

CÓDIGO EN C++...

ORDENAMIENTO QUICK SORT:

EL ORDENAMIENTO POR PARTICIÓN (QUICK SORT) SE PUEDE DEFINIR EN UNA FORMA MÁS CONVENIENTE COMO UN PROCEDIMIENTO RECURSIVO.

TIENE APARENTEMENTE LA PROPIEDAD DE TRABAJAR MEJOR PARA ELEMENTOS DE ENTRADA DESORDENADOS COMPLETAMENTE QUE PARA ELEMENTOS SEMI-ORDENADOS. ESTA SITUACIÓN ES PRECISAMENTE LA OPUESTA A ORDENAMIENTO EN BURBUJA.

ESTE TIPO DE ALGORITMOS SE BASA EN LA TÉCNICA “DIVIDE Y VENCERÁS”, ÓSEA ES MÁS RÁPIDO Y FÁCIL ORDENAR DOS ARREGLOS O LISTAS DE DATOS PEQUEÑOS, QUE UN ARREGLO O LISTA GRANDE.

NORMALMENTE AL INICIO DE LA ORDENACIÓN SE ESCOGE UN ELEMENTO APROXIMADAMENTE EN LA MITAD DEL ARREGLO, ASÍ AL EMPEZAR A ORDENAR, SE DEBE LLEGAR A QUE EL ARREGLO ESTE ORDENADO RESPECTO A PUNTO DE DIVISIÓN O LA MITAD DEL ARREGLO.

SE PODRÁ GARANTIZAR QUE LOS ELEMENTOS A LA IZQUIERDA DE LA MITAD SON MENORES Y LOS ELEMENTOS DE LA DERECHA SON MAYORES.

LOS SIGUIENTES PASOS SON LLAMADOS RECURSIVOS CON EL PROPÓSITO DE EFECTUAR LA ORDENACIÓN POR PARTICIÓN AL ARREGLO IZQUIERDO Y AL ARREGLO DERECHO, QUE SE OBTIENEN DE LA PRIMERA FASE. EL TAMAÑO DE ESOS ARREGLOS EN PROMEDIO SE REDUCE A LA MITAD.

ASÍ SE CONTINÚA HASTA QUE EL TAMAÑO DE LOS ARREGLOS A ORDENAR ES 1, ES DECIR, TODOS LOS ELEMENTOS YA ESTÁN ORDENADOS.

EL PROMEDIO PARA TODOS LOS ELEMENTOS DE ENTRADA DE TAMAÑO “N”, EL MÉTODO HACE “O” (n log n) COMPRARACIONES, EL CUAL ES RELATIVAMENTE EFICIENTE...

CODIFICACIÓN EN C++.

ORDENAMIENTO BEAP SORT:

EL ORDENAMIENTO POR MONTÍCULOS (HEAP SORT) ES UN ALGORITMO DE ORDENACIÓN NO RECURSIVO, NO ESTABLE, CON COMPLEJIDAD COMPUTACIONAL O (n log n).

ESTE ALGORITMO CONSISTE EN ALMACENAR TODOS LOS ELEMENTOS DEL VECTOR A ORDENAR EN UN MONTÍCULO (heap), Y LUEGO DE EXTRAER EL NODO QUE QUEDA COMO NODO RAÍZ DEL MONTÍCULO CIMA EN SUCESIVAS ITERACIONES OBTENIENDO EL CONJUNTO ORDENADO. BASA SU FUNCIONAMIENTO EN PROPIEDAD DE LOS MONTÍCULOS, POR LA CUAL, LA CIMA CONTIENE SIEMPRE EL MENOR ELEMENTO (O EL MAYOR, SEGÚN SE HAYA DEFINIDO EL MONTÍCULO) DE TODOS LOS ALMACENAMIENTOS EN EL.

EL SIGNIFICADO DE HEAP ES CIENCIA COMPUTACIONAL ES EL DE UNA COLA DE PRIORIDADES (PRIORITY QUEUE). TIENE LAS SIGUIENTES CARACTERÍSTICAS.

UN HEAP ES UN ARREGLO DE N POSICIONES AGRUPADO POR LOS ELEMENTOS DE LA COLA (NOTA: SE UTILIZA UN ARREGLO Q INICIA EN LA POSICIÓN 1 Y NO ES CERO, DE LA MANERA QUE EL IMPLEMENTARLA EN C SE TIENE n+ 1 POSICIONES EN EL ARREGLO.)

SE MAPEA UN ÁRBOL BINARIO DE LA MANERA EN EL ARREGLO QUE EL NODO EN LA POSICIÓN I ES EL PARTE DE LOS NODOS EN LAS POSICIONES (2*I) Y (2*I+1).

EL VALOR EN UN NODO ES MAYOR O IGUAL A LOS VALORES DE SUS HIJOS. POR CONSIGUIENTE, EL NODO PADRE TIENE EL MAYOR VALOR DE TODO SU ÁRBOL.

PROCEDIMIENTO:

HEAP SORT CONSISTE ESENCIALMENTE EN: