/* The next code implements some of the common sort methods, sorting 100000 random numbers, and thrwo the total time * that takes to sort. Remember that the time that takes each sort method to sort 100000 can depends of the computer. * * Tested on ubuntu. * * Author: Eduardo Perez Regin. * Date: 09/13/2019 */ /************************** main.cpp *******************************/ #include #include #include "Elements.hpp" #include "SortMethods.hpp" int main(){ std::cout << "Tiempo que le toma a cada metodo de ordenamiento para ordenar 100,000 numeros aleatorios, medidos en segundos." << std::endl << "IMPORTANTE: EL TIEMPO TOTAL PUEDE VARIAR DEPENDIENDO DE LA COMPUTADORA..." << std::endl << std::endl; SortMethods bubbleSort; SortMethods shellSort; SortMethods insertSort; SortMethods selectSort; SortMethods mergeSort; SortMethods quickSort; // Obtaining the execution time for bubble sort. clock_t start, end; start = clock(); bubbleSort.bubbleSort(); end = clock(); double durationBubble = double(end-start) / CLOCKS_PER_SEC; // Obtaining the execution time for shell start = clock(); shellSort.shellSort(); end = clock(); double durationShell = double(end-start) / CLOCKS_PER_SEC; // Obtaining the execution time for insertion sort. start = clock(); insertSort.insertSort(); end = clock(); double durationInsert = double(end-start) / CLOCKS_PER_SEC; // Obtaining the execution time for select sort. start = clock(); selectSort.selectSort(); end = clock(); double durationSelect = double(end-start) / CLOCKS_PER_SEC; // Obtaining the execution time for merge sort. start = clock(); shellSort.mergeSort(0, mergeSort.index()); end = clock(); double durationMerge= double(end-start) / CLOCKS_PER_SEC; // Obtaining the execution time for quicksort. start = clock(); quickSort.quickSort(0, quickSort.index()); end = clock(); double durationQuickSort = double(end-start) / CLOCKS_PER_SEC; std::cout << "Burbuja Mejorada: " << durationBubble << " segundos." << std::endl; std::cout << "Shell: " << durationShell << " segundos." << std::endl; std::cout << "Insercion: " << durationInsert<< " segundos." << std::endl; std::cout << "Seleccion: " << durationSelect<< " segundos." << std::endl; std::cout << "Mezcla: " << durationMerge<< " segundos." << std::endl; std::cout << "Quicksort: " << durationQuickSort << " segundos." << std::endl; return 0; } /************************************* Elements.hpp **************************************************/ #ifndef ELEMENTS_HPP #define ELEMENTS_HPP #include class Elements{ private: int value; // Used to store the random number. public: // Constructor. Elements(); // Copy constructor. Elements(const Elements& copy); /* OPERATORS. */ Elements& operator = (const Elements& element); bool operator == (const Elements& element) const; bool operator > (const Elements& element) const; bool operator < (const Elements& element) const; bool operator >= (const Elements& element) const; bool operator <= (const Elements& element) const; friend std::ostream& operator << (std::ostream& os, Elements& element); }; #endif /************************************** Elements.cpp ***********************************************/ #include #include "Elements.hpp" // Constructor. Elements::Elements(){ std::random_device rd; std::mt19937 generator(rd()); std::uniform_int_distribution<> dis(0, 1000000); value = dis(generator); } // Constructor copy. Elements::Elements(const Elements& copy) : value(copy.value) { } /* Operators. */ Elements& Elements::operator = (const Elements& element){ value = element.value; return *this; } bool Elements::operator == (const Elements& element) const { return this->value == element.value; } bool Elements::operator < (const Elements& element) const { return this->value < element.value; } bool Elements::operator <= (const Elements& element) const { return this->value <= element.value; } bool Elements::operator > (const Elements& element) const { return this->value > element.value; } bool Elements::operator >= (const Elements& element) const { return this->value >= element.value; } std::ostream& operator << (std::ostream& os, Elements& e){ os << e.value << " "; return os; } /*********************************************** SortMethods.hpp *************************************/ #include template class SortMethods{ private: static const int MAX = 100000; T elements[MAX]; public: // Constructor. SortMethods(); int index(); // Swap elements. void swapData(T& a, T& b); /* SORT METHODS. */ void bubbleSort(); void shellSort(); void insertSort(); void selectSort(); void mergeSort(const int& leftEdge, const int& rightEdge); void quickSort(const int& leftEdge, const int& rightEdge); /* METHODS. */ void print(); }; // Constructor. template SortMethods::SortMethods() { } // Index. template int SortMethods::index(){ return MAX; } template void SortMethods::print(){ for(size_t i(0); i < MAX; i++){ std::cout << elements[i] << std::endl;; } } template void SortMethods::swapData(T& a, T& b){ T aux(a); a = b; b = aux; } // SORT METHODS. template void SortMethods::bubbleSort(){ int i(MAX - 1), j; bool flag; do{ flag = false; j = 0; while(j < i){ if(elements[j] > elements[j + 1]){ swapData(elements[j], elements[j + 1]); flag = true; } j++; } i--; } while(flag); } template void SortMethods::shellSort(){ float fact(3.0 / 4.0); int dif(MAX * fact), lim, i; while(dif > 0){ lim = MAX - dif; i = 0; while(i <= lim){ if(elements[i] > elements[i + dif]){ swapData(elements[i], elements[i + dif]); } i++; } dif *= fact; } } template void SortMethods::insertSort(){ T aux; int i(1),j; while(i <= MAX - 1){ aux = elements[i]; j = i; while(j > 0 and aux < elements[j - 1]){ elements[j] = elements[j - 1]; j--; } if(i != j){ elements[j] = aux; } i++; } } template void SortMethods::selectSort(){ int i,j,menor; i=0; while(i void SortMethods::mergeSort(const int& leftEdge, const int& rightEdge){ int m, j, x, i; // Copiar a temporal. static T temp[MAX]; // Criterio de paro. if(leftEdge >= rightEdge){ // Criterio de paro. return; } // Divide y venceras. m = (leftEdge + rightEdge) / 2; // Separa el agoritmo. mergeSort(leftEdge, m); mergeSort(m + 1, rightEdge); /* INTERCALACION. */ for(int i(leftEdge); i <= rightEdge; i++){ temp[i] = elements[i]; } // Intercalacion. i = leftEdge; j = m + 1; x = leftEdge; while(i <= m and j <= rightEdge){ while(i <= m and temp[i] <= temp[j]){ elements[x++] = temp[i++]; } if(i <= m){ while(j <= rightEdge and temp[j] <= temp[i]){ elements[x++] = temp[j++]; } } } //while(i <= m and temp[i] <= temp[j]){ while(i <= m){ elements[x++] = temp[i++]; } while(j <= rightEdge){ elements[x++] = temp[j++]; } } template void SortMethods::quickSort(const int& leftEdge, const int& rightEdge){ // Criteorio de paro. if(leftEdge >= rightEdge){ return; } // Separacion. int i(leftEdge), j(rightEdge); while(i < j){ while(i < j and elements[i] <= elements[rightEdge]){ i++; } while(i < j and elements[j] >= elements[rightEdge]){ j--; } if(i != j){ swapData(elements[i], elements[j]); } } if(i != rightEdge){ swapData(elements[i], elements[rightEdge]); } // Divide y venceras. quickSort(leftEdge, i - 1); // i - 1 para no caer en el pivote. quickSort(i + 1, rightEdge); }

Sort Methods Total TIme