Download NetC.Time s - upcAnalisisAlgoritmos

Parcial
02
Historia
04/10/10
II Parcial Analisis de
. Algoritmos
NetC .Time
s
Metodo Shell Sort •
Tito Agudelo • Pedro Fula • Yesid Gutierrez • Oscar M unevar
El ordenamiento Shell (Shell sort en inglés) es un algoritmo de
ordenamiento. El método se denomina Shell en honor de su
inventor Donald Shell. Su implementación original, requiere O(n2)
comparaciones e intercambios en el peor caso. Un cambio menor
presentado en el libro de V. Pratt produce una implementación con
un rendimiento de O(nlog2 n) en el peor caso. Esto es mejor que las
O(n2) comparaciones requeridas por algoritmos simples pero peor
que el óptimo O(n log n). Aunque es fácil desarrollar un sentido
intuitivo de cómo funciona este algoritmo, es muy difícil analizar su
tiempo de ejecución.
Docente: Diana Mabel Diaz H. I n g e n i e r í a d e S i s t e m a s
Universida
d P i l o t o d e
C o l o m b i a
Tito Arturo Agudelo Flórez
Pedro Antonio Fula Perilla
Oscar Fernando Munevar
Yesid Fernando Gutierrez
Análisis de Algortimos El Shell sort 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
está "casi ordenada".
2. El ordenamiento por inserción es ineficiente, en general,
porque mueve los valores sólo 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 más
Parcial Número 02 Octubre 04 de 2010.
grandes" hacia su posición esperada. Los pasos múltiples sobre los
datos se hacen con tamaños de espacio cada vez más pequeños. El
último paso del Shell sort es un simple ordenamiento por inserción,
pero para entonces, ya está garantizado que los datos del vector
están casi ordenados.
Parcial II
Análisis de Algortimos CORRECTITUD Valores iníciales y estado inicial
public String Shell() {
long despues = 0;
long antes = System.currentTimeMillis();
int salto, cambios, aux, i;
for (salto = vector.length / 2; salto != 0; salto /= 2)
{
for (cambios = 1; cambios != 0;) {
cambios = 0;
for (i = salto; i < vector.length; i++)
Parcial Número 02 Octubre 04 de 2010.
if (vector[i - salto] > vector[i]) {
aux = vector[i];
vector[i] = vector[i - salto];
vector[i - salto] = aux;
cambios++;
}
}
}
despues = System.currentTimeMillis();
double x = (despues - antes) / 10;
System.out.println(x);
return "El tiempo de ordenacion para el metodo Shell con un vector "
+ vector.length + " fue de " + x + " microSeg ";
}
Parcial II
Análisis de Algortimos Inicio
Se crea un vector de tamaño n.
Se inicializa las variables –después- y –antes- para tomar los tiempos que se tarde el algoritmo con
diferentes cantidades de números.
Antes = System.currentTimeMillis ();  se inicia el tiempo de partida del algoritmo
Después =0;
 prerrequisito.
Después = System.currentTimeMillis ();  se inicia un tiempo apartar de que el algoritmo termina.
Antes > 0;  prerrequisito.
X= (después – antes) /100  se halla el resultado del tiempo que tarda en ejecutarse el algoritmo.
Se inicializa salto tomando el tamaño del vector dividido en 2 para empezar con el algoritmo
Parcial Número 02 Octubre 04 de 2010.
Salto = vector.length / 2;
Salto != 0;  prerrequisito para que empiece el algoritmo
Mantenimiento
Salto = vector.length / 2;

siempre está tomando el tamaño del vector dividido
en 2 para organizarlo.
Aux = vector[i];

depende del valor que tenga i.
Finalización
Vector[n]
 vector de tamaño n ordenado.
Parcial II
Análisis de Algortimos X = (antes – después)/100 tiempo de finalización del algoritmo
Parcial Número 02 Octubre 04 de 2010.
Algoritmo
Clase VectorArreglo
1. Método Principal
a. Declaraciones
Vector = vector []
antes = long : Real(System.currentTimeMillis())
después = 0 long : Real
salto = 0: Real
aux = 0: Real
cambios = 0: Real
i = 0: Real
x = doublé
lenght = Vector [n]
b. Ciclo para leer tamaño del archivo (vector)
Inicialice salto = vector.length/2;
Compare si salto ¡= 0;
Salto /= 2
c. Ciclo para leer cambio
Inicialice cambio = 1;
Si cambios ¡= 0;
Asigne cambio = 0;
d. Ciclo para leer i (vector)
Inicialice i = salto;
Compare i < vector.length
Incremente i++
e. Compare si (vector[i - salto] > vector[i])
Asigne aux = vector[i];
Asigne Vector[i] = vector[i - salto];
vector[i - salto] = aux;
Incremente cambio++
Complejidad
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden 1
orden n
orden k
orden k*n
orden 1
orden n
orden n
orden 1
orden 1
orden n
orden k
orden k
orden k*n
orden n
orden k
orden k
orden k
orden k
orden n
Parcial II
Análisis de Algortimos Parcial Número 02 Octubre 04 de 2010.
f. fin ciclo si
g. fin ciclo para
h. fin ciclo para
i. Operación
x = (después – antes / 10)
g. Imprima x
h. Return
“El tiempo de ordenación para el método
Shell con un vector” + vector.length +
“fue de un tiempo” + x + “microsegundos”;
Fin ciclo
Fin Método Principal
Fin Clase VectorArreglo
Fin
orden 1
orden 1
orden 1
orden k*n
orden k*n
orden 1
orden 1
orden 1
orden 1
orden 1
Parcial II
Análisis de Algortimos Determinando el nivel de complejidad del algoritmo Shell Sort es de O (n^2)
Se concluyo lo siguiente:
Mejor caso tiempo de 1 segundo para un vector de 140000 según el orden de complejidad.
1 = C * (140000^2)
C = 5,10 x 10^-11
Parcial Número 02 Octubre 04 de 2010.
Peor caso tiempo de 2 segundos para un vector 140000 según el orden de complejidad.
2 = C * (140000^2)
C= 1 x 10^-10
Donde C es la constante multiplicativa.
Parcial II
Análisis de Algortimos package Analisis;
import
import
import
import
import
import
import
import
java.awt.GridLayout;
java.awt.event.ActionEvent;
java.awt.event.ActionListener;
javax.swing.ImageIcon;
javax.swing.JButton;
javax.swing.JPanel;
javax.swing.JToolBar;
javax.swing.border.TitledBorder;
Clase Barra Botones
Parcial Número 02 Octubre 04 de 2010.
public class BarraBotones extends JPanel implements
ActionListener {
private JButton btnCrear;
private JButton btnShell;
private JButton btnAbout;
private InterfazPrincipal interfaz;
public static final String NUEVO = "Crear";
public static final String SHELL = "Shell";
public static final String ABOUT = "About";
private JToolBar tbBar;
public BarraBotones(InterfazPrincipal interfaz) {
this.interfaz = interfaz;
setLayout(new GridLayout(1, 9));
setBorder(new TitledBorder("Metodos de Ordenacion"));
Parcial II
Análisis de Algortimos btnCrear = new JButton();
btnCrear.setIcon(new ImageIcon("./icons/Nuevo.png"));
btnCrear.setToolTipText("Nuevo Arreglo");
btnCrear.addActionListener(this);
btnCrear.setActionCommand(NUEVO);
btnShell = new JButton();
btnShell.setIcon(new ImageIcon("./icons/Shell.png"));
btnShell.setToolTipText("Metodo Shell");
btnShell.addActionListener(this);
btnShell.setActionCommand(SHELL);
btnAbout = new JButton();
btnAbout.setIcon(new ImageIcon("./icons/About.png"));
btnAbout.setToolTipText("About");
btnAbout.addActionListener(this);
btnAbout.setActionCommand(ABOUT);
tbBar = new JToolBar();
Parcial Número 02 Octubre 04 de 2010.
tbBar.add(btnCrear);
tbBar.add(btnShell);
tbBar.add(btnAbout);
add(tbBar);
}
public void actionPerformed(ActionEvent ae) {
String comando = ae.getActionCommand();
if (comando.equals("Crear")) {
interfaz.inicializarVector();
}
else if (comando.equals("Shell")) {
interfaz.Shell();
}
else if (comando.equals("About")) {
interfaz.About();
}
Parcial II
Análisis de Algortimos }
}
package Analisis;
import java.awt.BorderLayout;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
public class InterfazPrincipal extends JFrame {
private
private
private
private
BarraBotones botones;
PanelLista lista;
PanelTiempo listat;
VectorArreglo vector;
public static void main(String[] arg) {
Clase Interfaz Principal
Parcial Número 02 Octubre 04 de 2010.
InterfazPrincipal interfaz = new InterfazPrincipal();
interfaz.setVisible(true);
}
public InterfazPrincipal() {
setTitle("Parcial Analisis de Algoritmos");
getContentPane().setLayout(new BorderLayout());
setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
vector = new VectorArreglo();
botones = new BarraBotones(this);
lista = new PanelLista();
listat = new PanelTiempo();
getContentPane().add(botones, BorderLayout.NORTH);
getContentPane().add(lista, BorderLayout.CENTER);
Parcial II
Análisis de Algortimos getContentPane().add(listat, BorderLayout.WEST);
pack();
}
public void inicializarVector() {
int numero = 0;
numero =
Integer.parseInt(JOptionPane.showInputDialog(this,
"Por favor ingrese el tamano del vector",
"Parcial Analisis",
JOptionPane.QUESTION_MESSAGE));
vector.Inicializar(numero);
lista.cambiarLista(vector.getVector());
}
Parcial Número 02 Octubre 04 de 2010.
public void Limpiar() {
lista.cambiarLista(vector.getVector());
}
public void Shell() {
listat.tiempos(vector.Shell());
Limpiar();
}
public VectorArreglo getVector() {
return vector;
}
public void About() {
JOptionPane.showMessageDialog(this, "Parcial
Analisis de Algoritmos"
+ "\nTito Agudelo" + "\nYesid Gutierrez" +
"\nOscar Munevar"
+ "\nPedro Fula", "About",
JOptionPane.INFORMATION_MESSAGE);
Parcial II
Análisis de Algortimos }
}
package Analisis;
import
import
import
import
import
import
import
import
import
java.awt.Color;
java.awt.Dimension;
java.awt.Font;
java.awt.GridLayout;
java.util.ArrayList;
javax.swing.JList;
javax.swing.JPanel;
javax.swing.JScrollPane;
javax.swing.border.TitledBorder;
public class PanelLista extends JPanel {
public PanelLista() {
Clase Panel Lista
Parcial Número 02 Octubre 04 de 2010.
private JList lista;
private InterfazPrincipal interfaz;
setLayout(new GridLayout(1, 1));
setBorder(new TitledBorder("Vectores"));
setPreferredSize(new Dimension(350, 350));
lista = new JList();
JScrollPane barra = new JScrollPane(lista);
lista.setBackground(new Color(230, 230, 230));
lista.setFont(new Font("Goudy Old Style", 1, 14));
lista.setForeground(new java.awt.Color(120, 120,
255));
add(barra);
}
public void cambiarLista(ArrayList vector) {
lista.setListData(vector.toArray());
Parcial II
Análisis de Algortimos }
}
package Analisis;
import
import
import
import
import
import
import
import
java.awt.Color;
java.awt.Dimension;
java.awt.Font;
java.awt.GridLayout;
javax.swing.JPanel;
javax.swing.JScrollPane;
javax.swing.JTextArea;
javax.swing.border.TitledBorder;
public class PanelTiempo extends JPanel {
private JTextArea tiempo;
setLayout(new GridLayout(1, 12));
setBorder(new TitledBorder("Tiempo de
Ordenacion"));
setPreferredSize(new Dimension(350, 350));
Clase Panel Tiempo
Parcial Número 02 Octubre 04 de 2010.
public PanelTiempo() {
tiempo = new JTextArea();
JScrollPane Barra = new JScrollPane(tiempo);
tiempo.setBackground(new Color(230, 230, 230));
tiempo.setFont(new Font("Goudy Old Style", 1, 14));
tiempo.setForeground(new java.awt.Color(120, 120,
255));
add(Barra);
}
public void tiempos(String tiempov) {
tiempo.append(tiempov + "\n");
Parcial II
Análisis de Algortimos }
}
package Analisis;
import java.util.ArrayList;
public class VectorArreglo {
private int vector[];
public VectorArreglo() {
Clase Vector Arreglo
Parcial Número 02 Octubre 04 de 2010.
}
public void Inicializar(int tamanoVector) {
vector = new int[tamanoVector];
int a = tamanoVector;
for (int i = 0; i < tamanoVector; i++) {
// vector[i] = a--;
vector[i] = (int) (Math.random() * 500000 +
1);
// vector[i]= i;
}
}
public ArrayList getVector() {
ArrayList lista = new ArrayList();
for (int i = 0; i < vector.length; i++) {
lista.add("" + (i + 1) + ") " + vector[i]);
}
return lista;
}
public String Shell() {
Parcial II
Análisis de Algortimos long despues = 0;
long antes = System.currentTimeMillis();
int salto, cambios, aux, i;
for (salto = vector.length / 2; salto != 0; salto /= 2)
{
for (cambios = 1; cambios != 0;) {
cambios = 0;
for (i = salto; i < vector.length; i++)
Parcial Número 02 Octubre 04 de 2010.
if (vector[i - salto] > vector[i]) {
aux = vector[i];
vector[i] = vector[i - salto];
vector[i - salto] = aux;
cambios++;
}
}
}
despues = System.currentTimeMillis();
double x = (despues - antes) / 10;
System.out.println(x);
return "El tiempo de ordenacion para el metodo Shell con
un vector "
+ vector.length + " fue de " + x + " microSeg
";
}
public int tamanoVector() {
return vector.length;
}
}
Parcial II
Análisis de Algortimos Parcial Número 02 Octubre 04 de 2010.
1. Ejecucion del programa, tenemos 3 iconos, primero crear nuevo vector, segundo Metodo Shell y el tercero Integrantes. 2. Escirbir Vector en este caso 140000 Parcial II
Análisis de Algortimos Parcial Número 02 Octubre 04 de 2010.
3. Nos genera 140000 numeros aleatorios, estos se pueden repetir 4. Le damos en metodo Shell y asi los ordena, como se pude ver tardo 8 mili segundos para un caso intermedio (Números Desordenados). Parcial II
Análisis de Algortimos Parcial Número 02 Octubre 04 de 2010.
5. Para el peor de los casos (Numeros invertidos) con un vector de 140000 6. Para el mejor de los casos (Numeros Ordenados) con un vector de 140000 el tiempo fue de 1 mili segundo. Parcial II
Análisis de Algortimos . REFERENCIAS BIBLIOGRÁFICAS . http://es.wikipedia.org/wiki/Ordenamiento_Shell
Mark Allen Weiss, Data Structures and Algorithm Analysis,
Benjamin/Cummings, 2a ed., 1995, pág. 216-220.
•Micha Hofri, Analysis of Algorithms: Computational Methods and
Mathematical Tools, Oxford University Press, 1995, pág. 431-437.
Parcial Número 02 Octubre 04 de 2010.
•Robert Sedgewick, Algorithms in C++, Addison-Wesley, 1992,
pág. 107-112.
•Sara Baase, Computer Algorithms: Introduction to Design and
Analysis, Addison-Wesley, 1978, pág.
Parcial II