análisis de Algoritmos
Ordenamientos
Juan Felipe Davila Galvis
Juan Sebastian Davila Galvis
Programa Ordenamiento: SelectionSort vs ShellSort
SelectionSort
package applet;
import static [Link];
import [Link].*;
import [Link];
import [Link];
public class SeleccionSort {
static int[] arreglo;
static ArrayList tiempo =new ArrayList();//cambiar a arraylist
long tiempof;
/**
* Nombre Método: SeleccionSort
* Propósito: Metodo constructor de la clase que almacena el arreglo de datos
* Variables Utilizadas:a, arreglo, i
* Precondición: Tener el arreglo de datos
* Postcondición: Arreglo de datos asignado de manera local
*/
public SeleccionSort(int[] a){
arreglo=new int[[Link]];
for(int i=0;i<[Link];i++){
[Link][i]=a[i];
/**
* Nombre Método: Ordenar
* Propósito: Ordenar los datos del arreglo segun el algoritmo de ordenamiento SelectionSort
y calcular el tiempo ejecucion
* Variables Utilizadas: i, j, inicio1, fin, fin1, jMin, arreglo,tiempo, tiempof
* Precondición: N/A
* Postcondición: Algoritmo ejecutado, datos organizados y tiempo de ejecucion calculado
*/
public void ordenar() throws IOException{
int i, j;
long inicio1 = [Link]();
long fin, fin1 = 0;
for (i = 0; i < [Link] - 1; i++) {
/* find the min element in the unsorted a[i .. aLength-1] */
/* assume the min is the first element */
int jMin = i;
/* test against elements after i to find the smallest */
for (j = i + 1; j < [Link]; j++) {
/* if this element is less, then it is the new minimum */
if (arreglo[j] < arreglo[jMin]) {
/* found new minimum; remember its index */
jMin = j;
}
if (jMin != i) {
swap(arreglo[i], arreglo[jMin]);
fin = [Link]();
[Link]((fin - inicio1));
fin1 = [Link]();
tiempof = ((fin1 - inicio1));
guadardartiempo();
/**
* Nombre Método: guardarTiempo
* Propósito: Almacenar el tiempo de cada iteracion
* Variables Utilizadas: flwriter, archivo, bfwriter, i, tiempo
* Precondición: N/A
* Postcondición: Tiempo de iteraciones almacenado en un archivo de texto
*/
public void guadardartiempo() throws IOException{
FileWriter flwriter = null;
File archivo=new File("[Link]");
flwriter = new FileWriter(archivo);
BufferedWriter bfwriter = new BufferedWriter(flwriter);
for(int i=0;i<[Link]()&&.equals(0);i++){
[Link]((i+1)+" "+[Link](i)+"\n");
}
[Link]("fin");
[Link]();
private void swap(int i, int j) {
int aux = i ;
i = j;
j = aux;
RadixSort
package applet;
import static [Link];
import static [Link];
import [Link].*;
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
public class ShellSort {
static int[] arreglob;
static ArrayList tiempo =new ArrayList();
long tiempof;
/**
* Nombre Método: ShellSort
* Propósito: metodo constructor de la clase que almacena el arreglo de datos
* Variables Utilizadas: a, arreglob, i
* Precondición: Tener el arreglo de datos
* Postcondición: Arreglo de datos asignado de manera local
*/
public ShellSort(int[] a){
arreglob=new int[[Link]];
for(int i=0;i<[Link];i++){
[Link][i]=a[i];
/**
* Nombre Método: ordenar
* Propósito: Ordenar los datos del arreglo segun el algoritmo de ordenamiento shellsort y
calcular el tiempo ejecucion
* Variables Utilizadas: fin, fin1, inicio1, n, key, j
* Precondición: N/A
* Postcondición: Algoritmo ejecutado, datos organizados y tiempo de ejecucion calculado
*/
public void ordenar() throws IOException{
long fin, fin1 = 0;
long inicio1 = [Link]();
int n = [Link];
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int key = arreglob[i];
int j = i;
while (j >= gap && arreglob[j - gap] > key) {
arreglob[j] = arreglob[j - gap];
j -= gap;
fin = [Link]();
[Link]((fin - inicio1));
arreglob[j] = key;
fin1 = [Link]();
tiempof = ((fin1 - inicio1));
guadardartiempo();
/**
* Nombre Método: guardarTiempo
* Propósito: Almacenar el tiempo de cada iteracion
* Variables Utilizadas: flwriter, archivo, bfwriter, i, tiempo
* Precondición: N/A
* Postcondición: Tiempo de iteraciones almacenado en un archivo de texto
*/
public void guadardartiempo() throws IOException{
FileWriter flwriter = null;
File archivo=new File("[Link]");
flwriter = new FileWriter(archivo);
BufferedWriter bfwriter = new BufferedWriter(flwriter);
for(int i=0;i<[Link]()&&.equals(0);i++){
[Link]((i+1)+" "+[Link](i)+"\n");
[Link]("fin");
[Link]();
Captura Ejecucion