Scribd
Cargar
445 vistas5 páginas

Ordenamiento Merge Sort

El documento compara los tiempos de ejecución de los algoritmos de ordenamiento Insertion Sort y Merge Sort para diferentes cantidades de datos. Se implementaron ambos algoritmos en C++ siguiendo el libro Introduction to Algorithms. Los resultados mostraron que Insertion Sort es más rápido para cantidades menores a 30 elementos, mientras que Merge Sort es más eficiente para conjuntos de datos más grandes.

Cargado por

Rony Ramos
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
445 vistas5 páginas

Ordenamiento Merge Sort

El documento compara los tiempos de ejecución de los algoritmos de ordenamiento Insertion Sort y Merge Sort para diferentes cantidades de datos. Se implementaron ambos algoritmos en C++ siguiendo el libro Introduction to Algorithms. Los resultados mostraron que Insertion Sort es más rápido para cantidades menores a 30 elementos, mientras que Merge Sort es más eficiente para conjuntos de datos más grandes.

Cargado por

Rony Ramos
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Actividad.

Implementar y comparar los tiempos de ejecuci ́on de los algoritmos Insertion


Sort y el algoritmo Merge Sort. Verificar si el algoritmo Insertion Sort vence al
algoritmo Merge Sort para una cantidad menor de 30 elementos (n0).
Los algoritmos fueron implementados en el lenguaje c++, se uso como guia el
libro Introduction to Algorithms, Cormen.
Implementacion Algoritmo Insert Sort:
#include<iostream>
using namespace std;

void createVector( int a[], int tam );


void insertSort( int a[], int tam );

int main() {
int tam = 11;
int list[tam];
createVector( list, tam );
for( int i = 0; i < tam; i++ ) {
cout << list[i] << "; ";
}
cout << "\n";
insertSort(list, tam);
for( int i = 0; i < tam; i++ ) {
cout << list[i] << "; ";
}
return 0;
}
void insertSort( int a[], int tam) {
int i = 0;
for( int j = 1; j < tam; j++ ) {
int key = a[j];
i = j - 1;
while( i >= 0 && a[i] > key ) {
a[i + 1] = a[i];
i = i - 1;
}
a[i + 1] = key;
}
}
void createVector( int a[], int tam ) {
int value = tam - 1;
for( int i = 0; i < tam; i++ ) {
a[ i ] = value;
value--;
}
}
Implementacion Algoritmo Merge Sort:
#include<iostream>
using namespace std;
void merge(int a[], int p, int q, int r);
void mergeSort(int a[], int p, int r);

int main() {
int tam = 11;
int list[ tam];
// creamos el arreglo orden descendente
int value = tam;

for( int i = 0; i < tam; i++ ) {


list[ i ] = value;
value--;
}
// imprimer el arreglo
cout << "\n";
for( int i = 0; i < tam; i++ ) {
cout << list[i] << "; ";
}

// mandaamos a ordena rel arreglo


mergeSort(list, 0, tam - 1);

// imprimimos el arreglo ordenado


cout << "\n";
for( int i = 0; i < tam; i++ ) {
cout << list[i] << "; ";
}
return 0;
}

void merge(int *a, int p, int q, int r) {


int n1 = q - p + 1;
int n2 = r - q;
int *L = new int[n1];
int *R = new int[n2];

for(int i = 0; i < n1; i++) {


L[i] = a[p + i];
}
for( int j = 0; j < n2; j++ ) {
R[j] = a[q + j + 1];
}

int i = 0;
int j = 0;
int k = p;
for(; k < r && i < n1 && j < n2; k++) {
if(L[i] <= R[j]){
a[k] = L[i];
i = i + 1;
}
else {
a[k] = R[j];
j = j + 1;
}
}

for(; i < n1; i++, k++) {


a[k] = L[i];
}
for(; j < n2; j++, k++) {
a[k] = R[j];
}

delete[] L, R;
}

void mergeSort(int *a, int p, int r) {


if( p < r ) {
int q = (p + r)/2;
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
merge(a,p,q,r);
}
}

Comparacion:
Tiempo de ejecucion de los algoritmos Insertio Sort y Merge Sort, según el
numero de datos.

Tiempos de Ejecución: Algirtmo Merge Sort e Insert Sort.


N° Datos Insert Merge
4 0.02495 0.02659 Insert Merge
8 0.02726 0.0281
11 0.050.02814 0.02864
16 0.040.03013 0.03167
25 0.040.03274 0.03546 Probamos que
30 0.030.03948 0.03678
0.03
el Algoritmo
40 0.04 0.03886 Insert Sort tiene
0.02
0.02 menor tiempo
0.01 de
0.01
0
4 8 11 16 25 30 40

ejecucion cuando el numero de datos de entrada es menor a 30, en otros casos el


algoritmo Merge Sort, tiene mejor tiempo de ejecucion.
Capturas de Pantalla:

También podría gustarte