Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "stdafx.h"
- #include <string.h>
- #include <conio.h>
- #include <cstdlib>
- #include <ctime>
- #include <iostream>
- #include <thread>
- #include <chrono>
- using namespace std;
- //llena toda la cadena con numeros random
- void fill(int array[], int N, int min, int max)
- {
- srand(time(NULL));
- for (int i = 0; i<N; i++)
- {
- array[i] = (rand() % (max - min)) + min;
- }
- }
- //hace los cambios de un lugar a otro
- void swap(int &a, int &b)
- {
- int temp = a;
- a = b;
- b = temp;
- }
- //realiza el algoritmo de inserción
- void insertion(int array[], int N, int *cambios, int* comparaciones)
- {
- for (int i = 1; i < N; i++) {
- for (int x = i - 1; x >= 0; x--) {
- (*comparaciones)++;
- if (array[x + 1] < array[x]) {
- swap(array[x + 1], array[x]);
- (*cambios)++;
- }
- else {
- break;
- }
- }
- }
- }
- //ordenamiento shell
- void shell(int array[], int N, int *cambios, int* comparaciones)
- {
- //el ciclo se hara hasta que h==0
- for (int h = N / 2; h != 0; h /= 2) {
- bool noCambios = true;
- //si no hubo cambios en la esa fase, el ciclo se cierra.
- while (noCambios)
- {
- noCambios = false;
- //este ciclo se hace antes de que se llegue a aun desbordamiento
- for (int o = 0; o < h; o++)
- {
- for (int i = o; i + h < N; i += h)
- {
- (*comparaciones)++;
- if (array[i] > array[i + h]) {
- //se realizan los cambios de lugar
- swap(array[i], array[i + h]);
- (*cambios)++;
- if (i - h >= 0) {
- i -= (2*h);
- }
- noCambios = true;
- }
- }
- }
- }
- }
- }
- int main()
- {
- //tamaño del arreglo (se va modificando)
- int const x = 10;
- int totalcambiosS=0;
- int toatalcomparacionesS=0;
- int totalcambiosI = 0;
- int toatalcomparacionesI = 0;
- //hace el test de 10 pruebas
- for (int i = 0; i < 10; i++) {
- int array[x] = {};
- int array2[x] = {};
- //espera 1 segundo para que las cadenas tengan diferentes numeros en cada intento.
- std::this_thread::sleep_for(std::chrono::seconds(1));
- //llegna el arreglo
- fill(array, x, 0, 50);
- //copia el arreglo 1 en el 2
- for (int n = 0; n < x; n++) {
- array2[n] = array[n];
- }
- //se aplican los metodos
- insertion(array, x,&totalcambiosI,&toatalcomparacionesI);
- shell(array2, x, &totalcambiosS, &toatalcomparacionesS);
- }
- cout << "promedio comparaciones en insercion " << ((float)toatalcomparacionesI/10) << endl;
- cout << "promedio cambios en insercion " << ((float)totalcambiosI/10 )<< endl;
- cout << "promedio comparaciones en sell " << ((float)toatalcomparacionesS / 10) << endl;
- cout << "promedio cambios en sell " << ((float)totalcambiosS / 10) << endl;
- _getch();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement