Ordenamiento por seleccion

Solo disponible en BuenasTareas
  • Páginas : 2 (319 palabras )
  • Descarga(s) : 38
  • Publicado : 28 de julio de 2010
Leer documento completo
Vista previa del texto
Ordenamiento por selección

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos.
Sufuncionamiento es el siguiente:
• Buscar el mínimo elemento de la lista
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo
Y en general:
•Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i
De esta manera se puede escribir el siguiente seudocódigo paraordenar una lista de n elementos indexados desde el 1:
para i=1 hasta n-1
minimo = i;
para j=i+1 hasta n
si lista[j] < lista[minimo] entonces
minimo = j /* (!) */fin si
fin para
intercambiar(lista[i], lista[minimo])
fin para

Este algoritmo mejora ligeramente el algoritmo de la burbuja. En el caso de tener que ordenar un vector de enteros,esta mejora no es muy sustancial, pero cuando hay que ordenar un vector de estructuras más complejas, la operación intercambiar() sería más costosa en este caso. Este algoritmo realiza muchas menosoperaciones intercambiar() que el de la burbuja, por lo que lo mejora en algo. Si la línea comentada con (!) se sustituyera por intercambiar(lista[i], lista[j]) tendríamos una versión del algoritmo dela burbuja (naturalmente eliminando el orden intercambiar del final).
Otra desventaja de este algoritmo respecto a otros como el de burbuja o de inserción directa es que no mejora su rendimientocuando los datos ya están ordenados o parcialmente ordenados. Así como, por ejemplo, en el caso de la ordenación de burbuja se requeriría una única pasada para detectar que el vector ya está ordenadoy finalizar, en la ordenación por selección se realizarían el mismo número de pasadas independientemente de si los datos están ordenados o no.

ALGORITMO DEL METODO

int minimo=0;
for(i=0 ;...
tracking img