Ordenamiento Ppt

Estructuras de Datos

Ordenamiento de
arreglos

Algoritmos de ordenamiento


Dado un arreglo de enteros A y su longitud TAM,
ordenar el arreglo de menor a mayor

Métodos de ordenamiento:
Selección
 Inserción
 Burbuja
 Quicksort

Método de Selección
Este algoritmo es sencillo. Consiste en lo siguiente:
 Buscas el elemento más pequeño de la lista.
 Lo intercambias con el elemento ubicadoen la
primera posición de la lista.
 Buscas el segundo elemento más pequeño de la
lista.
 Lo intercambias con el elemento que ocupa la
segunda posición en la lista.
 Repites este proceso hasta quehayas ordenado
toda la lista.

Ejemplo de selección
Lista a ordenar:
4-3-5-2-1
intercambiamos con el 4 y la lista queda así:
1-3-5-2-4
Lo intercambiamos con el elemento en la segunda
posición, esdecir el 3. La lista queda así:
1-2-5-3-4
intercambiamos con el 5:
1-2-3-5-4
intercambiamos con el 5:
1-2-3-4-5

Algoritmo (método de selección)
for (i=0; i pos_menor = Menor (A, TAM, i);temp = A[i];
A[i] = A [pos_menor];
A [pos_menor] = temp;

Método de inserción
Consideremos que en un momento dado, el segmento
izquierdo del arreglo está ordenado y el segmento
derecho no.
Podemostomar un elemento del segmento derecho e
insertarlo en su lugar correcto en el lado izquierdo

Parte ordenada

Parte desordenada








Se considera la lista partida en dos sublistas,
una ordenaday la otra para ordenar
En el primer paso, la lista ordenada contiene un
elemento y la lista por ordenar, TAM-1,
Se van extrayendo uno a uno los elementos de
la lista desordenada y se colocan en lasublista
ordenada, mediante comparaciones sucesivas,
hasta encontrar la posición correcta,
El proceso continúa hasta que la lista
desordenada queda vacía.

Ejemplo de inserción
8 12 4 9 3
8 12 4 9 3
4 812 9 3
4 8 9 12 3
3 4 8 9 12

Método de la burbuja
Supongamos que tenemos una función flota()
que “flota” el elemento más grande hasta el final
del arreglo.
 Ejemplo: int a[] = {8, 12, 4, 9, 3...

Leer documento completo

Regístrate para leer el documento completo.