Algoritmos De Ordenamiento

1

LIC. EN SISTEMAS
COMPUTACIONALES
ALGORITMOS
TAREA 1 : ANALISIS DE
ALGORITMOS DE
ORDENAMIENTO
MARITZA JAZMIN RODAS
DUQUE 1 “F”

2

INDICE
INTRODUCCION ……………………3
BUBBLE SORT

……………………4

SELECTION SORT …………………6
INSERTION SORT …………………8
MERGE SORT

……………………10

QUICK SORT

……………………12

RUBY SORT ………………………15
COMPARACION DE ALGORTIMOS …17
CONCLUSION
BIBLIOGRAFIA……………………21
…………………22

3
INTRODUCCION
Los algoritmos son programas creados para resolver diversos problemas de la vida
cotidiana.
Algunos de los algoritmos mas comunes son los algoritmos de comparacion. En las
siguientes paginas se mostrara el desempeño de los algoritmos de ordenamiento mas
comunes.
Los algoritmos que se manejaran fueron probados con numeros aleatorios entre el 0 y
el 10 000, a simismo, sufrieron un incremento de 10 digitos en cada nuevo bucle
hasta llegar a ser 5 000 numeros a ordenar y fueron probados en un ordenador con
procesador Intel Core Duo de 3.00GHz con 1.9GB de RAM

4
BUBBLE SORT
Es conocido como “ORDENAMIENTO DE BURBUJA”. Funciona revisando cada elemento de
la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si
están en elorden equivocado. 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 comparacionespara operar elementos, se lo considera un algoritmo de comparación, siendo el más
sencillo de implementar.
A continuación se presenta un ejemplo de este y su grafica de rendimiento.
#!/usr/bin/ruby
#Bubble sort
def bubble_sort(list)
list = list.dup
for i in 0...list.length
for j in 0..(list.length - i - 2)
list[j], list[j + 1] = list[j + 1], list[j] if list[j + 1] < list[j]
end
endreturn list
end
#Generador de las listas de numeros aletorios
def aleatorios(n)
list = []
(1..n).each do
num = (rand*10000+1).to_i
list.push(num)
end
list
end
#Profiler temporizador
class Prof
attr_accessor :initime, :endtime
def initialize
@initime = 0
@endtime = 0
end
def tic()
@initime=Time.now.to_f
end
def toc()
if @initime==0
else
@endtime = sprintf("%.4f",Time.now.to_f -@initime).to_f
end
end
end
#Tiempos de algoritmos
tbubble = []
#Parametros
n_inicial = 10
n_final = 5000
n_incremento = 10

5
n_listas = (n_final - n_inicial) / n_incremento
#n long de las listas
n_test = []
#inicia profiler
t = Prof.new
#Loop de prueba
(n_inicial..n_final).step(n_incremento) do |n|
print "n=#{n} "
list = aleatorios(n)
n_test.push(n)
#Bubble sort
t.ticbubble_sort(list)
tbubble.push(t.toc)
print "Bubble sort #{t.endtime}\n"
end

Al poner en funcionamiento este algoritmo obtenemos los siguientes datos:
Numeros
10
20
30
40
50
60
70
80
90
100
200
300
400
500
600
700
800
900
1000
1500
2000
2500
3000
3500
4000
4500
5000

Tiempo
0.0001
0.0003
0.0006
0.0012
0.0016
0.0022
0.0041
0.0042
0.0062
0.0071
0.02950.0628
0.1135
0.1791
0.2505
0.3428
0.4441
0.6036
0.7041
1.6044
2.8032
4.3059
6.247
16.7008
13.3687
19.9947
52.0787

6
SELECTION SORT

Conocido como “ALGORITMO POR SELEECION” es un algoritmo de ordenamiento que
requiere O

operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:





Buscar el mínimo elemento de la listaIntercambiarlo 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

#!/usr/bin/ruby
#Selection sort
def selection_sort(list)
list.size.times do |start|
min = start
start.upto(list.size-1) do |i|
min = i...