Ordenamiento De Vectores

Ordenamiento de Vectores

Joel Quatrocchi

Estructura de Datos

Índice

Introducción 3
Pruebas y Escenarios 4
Tipos de Ordenamientos 6
Intercambio Directo (Burbuja) 7
Sacudida 8
Inserción Directa 9
Inserción Binaria 10
Mezcla 11
Shellsort 13
Quicksort 14

Introducción

El objetivo de este informe es investigar sobre la eficiencia dedistintos algoritmos de ordenamiento de vectores, a saber:

Intercambio Directo (burbuja),
Sacudida,
Inserción Directa,
Inserción Binaria,
Mezcla,
Shellsort,
Quicksort,

utilizando arreglos de 10, 100, 1000, 10000 y 100000 elementos, obteniendo la cantidad de swaps(o intercambios) y comparaciones realizadas en cada caso.
De esta manera se busca lograr unacomprensión global sobre las ventajas y desventajas de cada algoritmo frente a arreglos de distintas dimensiones, encontrando aquel con óptimo rendimiento en cada caso.


Pruebas y Escenarios
Se llevarán a cabo pruebas sobre 3 escenarios distintos:
1. Orden inicial aleatorio (cargado mediante rand() % 100000).

2. Orden inicial ascendente (“ordenado”) desde 1hasta MAX, siendo MAX el tamaño del arreglo a generado.

3. Orden inicial descendente (“inverso”) desde MAX hasta 1, siendo MAX el tamaño del arreglo a generado.
donde la ejecución de cada algoritmo será sobre un mismo conjunto de partida; es decir, en la implementación se generará el arreglo a ordenar según los escenarios 1, 2 y 3, y luego por cada algoritmo se creara un arregloespecial, copia exacta del arreglo primeramente generado (a través de la función de C “memcpy”). De esta manera nos aseguramos una “justa” comparación de los métodos de ordenamiento.
Código Principal (Main)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// cantidad de arraysconst short nArrays = 5;

// preparar contadores
long compCount = 0;
long movesCount = 0;

/*! \brief Ejecuta las pruebas de todos los arrays
\author Joel Quatrocchi */
int main(int argc, char *argv[])
{
//numero de elementos de los arrays a investigar
int sizes[nArrays] = {10, 100, 1000, 10000, 100000};
// repetir prueba para todos los arrays
for (short i = 0; i < nArrays; i++)
{
// Crear el array de dimension correspondiente
int array[sizes[i]];// Cargar Vector
// Aleatorio
// srand( time(NULL) );
// for (int j = 0; j < sizes[i]; j++)
// {
// array[j] = rand() % 100000;
// }
// // ascendente (ordenado)
// for (int j = 0; j< sizes[i]; j++)
// {
// array[j] = j+1;
// }
// descendente (inverso)
int loadValue = sizes[i];
for (int j = 0; j < sizes[i]; j++)
{
array[j] = loadValue--;
}// copiar el array generado a otros para cada ordenamiento antes de aplicarlos
// para que cada ordenamiento sea en base a un mismo array(igualmente desordenado)
int arrayBurbuja[sizes[i]];
memcpy(arrayBurbuja, array, sizeof(arrayBurbuja));
int arraySacudida[sizes[i]];...