Facultad De Ciencias De La Computación
Análisis y Desarrollo de Algoritmos
ALUMNO:
Octavio Misael
Otoño 2025
Chart Title
300000
250000
200000
150000
100000
50000
0
100000 150000 200000 250000 300000
Mejor Caso (ms) Peor Caso (ms)
Caso Promedio Run 1 (ms) Caso Promedio Run 2 (ms)
Caso Promedio Run 3 (ms)
Codigo
import [Link];
import [Link];
import [Link];
public class Burbuja_Quick {
static class Resultados {
long comparaciones;
long intercambios;
Resultados(long c, long i) { comparaciones = c; intercambios = i; }
//BURBUJA
public static Resultados bubbleSort(int[] lista) {
int n = [Link];
boolean elementosIntercambiados = true;
int numeroDePares = n;
long comparaciones = 0;
long intercambios = 0;
while (elementosIntercambiados) {
numeroDePares = numeroDePares - 1;
elementosIntercambiados = false;
for (int i = 0; i < numeroDePares; i++) {
comparaciones++;
if (lista[i] > lista[i + 1]) {
int temp = lista[i];
lista[i] = lista[i + 1];
lista[i + 1] = temp;
elementosIntercambiados = true;
intercambios++;
return new Resultados(comparaciones, intercambios);
// QUICKSORT
public static Resultados quickSort(int[] arr) {
long comparaciones = 0;
long intercambios = 0;
int n = [Link];
Stack<int[]> stack = new Stack<>();
[Link](new int[]{0, n - 1});
while (![Link]()) {
int[] range = [Link]();
int low = range[0];
int high = range[1];
if (low < high) {
// Partición
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
comparaciones++;
if (arr[j] <= pivot) {
i++;
// Intercambiar arr[i] y arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
intercambios++;
// Intercambiar arr[i + 1] y arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
intercambios++;
int p = i + 1;
// Agregar las dos subparticiones a la pila
[Link](new int[]{low, p - 1});
[Link](new int[]{p + 1, high});
return new Resultados(comparaciones, intercambios);
}
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Ingrese el número de elementos del arreglo: ");
int n = [Link]();
[Link]("----------------------------------------------------------");
//LISTAS
//peor caso
int[] listaPeor = new int[n];
for (int i = 0; i < n; i++) {
listaPeor[i] = n - i;
//caso promedio
int[] listaPromedio = new int[n];
Random rand = new Random();
for (int i = 0; i < n; i++) {
listaPromedio[i] = [Link](n * 10);
//lista ordenada por burbuja
int[] arregloParaOrdenar = [Link]();
long startTime, endTime, duration;
[Link]("Algoritmo, Caso, Tiempo (ms)");
[Link]("----------------------------------------------------------");
// lista ordenada QS
startTime = [Link]();
quickSort([Link]()); // Se clona para no modificarla
endTime = [Link]();
duration = (endTime - startTime) / 1000000;
[Link]("QuickSort,-mejor- (lista ya ordenada), " + duration);
// PEOR CASO
startTime = [Link]();
quickSort([Link]());
endTime = [Link]();
duration = (endTime - startTime) / 1000000;
[Link]("QuickSort, Peor (lista inversa), " + duration);
[Link]("----------------------------------------------------------");
// CASO PROMEDIO
for (int i = 1; i <= 3; i++) {
startTime = [Link]();
quickSort([Link]());
endTime = [Link]();
duration = (endTime - startTime) / 1000000;
[Link]("QuickSort, Promedio (Run " + i + "), " + duration);
}
[Link]();