// // Test of Sorting Algorithms // #include #include #include #include #include #include void bubbleSort( std::vector::iterator first, // First element of the segment, std::vector::iterator last // element after the last ); void directSort( std::vector::iterator first, // First element of the segment, std::vector::iterator last // element after the last ); void heapSort( std::vector::iterator first, // First element of the segment, std::vector::iterator last // element after the last ); void merge( std::vector::iterator a0, // Beginning of first array std::vector::iterator a1, // After-end of first array std::vector::iterator b0, // Beginning of second array std::vector::iterator b1, // After-end of second array std::vector::iterator c // Beginning of resulting array ); void mergeSortTopBottom( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last // After-end of array segment to sort ); void mergeSortRecursive( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last, // After-end of array segment to sort std::vector::iterator tmpMem // Beginnig of temporary memory ); void mergeSortBottomTop( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last // After-end of array segment to sort ); void bubbleDown( std::vector::iterator first, // First element of the segment, size_t n, // size of array segment, size_t k // Element to sieve ); void printArray( std::vector::iterator first, // First element of the segment, std::vector::iterator last // element after the last ); int main() { std::cout << "Test of Sorting Algorithms" << std::endl; // Initialize a random generator time_t tim, ttt; tim = time(&ttt); std::cout << "Seconds since beginning of epoche: " << tim << std::endl; srand((unsigned int) tim); while (true) { std::cout << "Which algorithm?" << std::endl << "1 -- Bubble Sort, 2 -- Direct Sort," << std::endl << "3 -- Heap Sort, 4 -- Merge Sort Bottom-Top" << std::endl << "5 -- Merge Sort Top-Bottom, 0 -- quit:" << std::endl; int alg = 1; std::cin >> alg; if (!std::cin.good() || alg <= 0 || alg > 5) break; size_t n; std::cout << "Size of array:" << std::endl; std::cin >> n; if (!std::cin.good() || n == 0) break; std::vector a(n); // Generate a random contents for (size_t i = 0; i < n; ++i) { double v = 1000.*double(rand())/double(RAND_MAX); a[i] = v; } std::cout << "Source array:" << std::endl; printArray(a.begin(), a.end()); std::cout << "--------" << std::endl; if (alg == 1) { bubbleSort(a.begin(), a.end()); } else if (alg == 2) { directSort(a.begin(), a.end()); } else if (alg == 3) { heapSort(a.begin(), a.end()); } else if (alg == 4) { mergeSortBottomTop(a.begin(), a.end()); } else if (alg == 5) { mergeSortTopBottom(a.begin(), a.end()); } std::cout << "Sorted array:" << std::endl; printArray(a.begin(), a.end()); std::cout << "--------" << std::endl; } return 0; } void printArray( std::vector::iterator first, // First element of the segment, std::vector::iterator last // element after the last ) { std::cout << std::fixed << std::setprecision(3); size_t n = last - first; if (n <= 1000) { for (size_t i = 0; i < n; ++i) { if (i > 0) { // Print a delimiter if (i%5 == 0) std::cout << std::endl; else std::cout << " "; } std::cout << first[i]; } } else { for (size_t i = 0; i < 100; ++i) { if (i > 0) { // Print a delimiter if (i%5 == 0) std::cout << std::endl; else std::cout << " "; } std::cout << first[i]; } std::cout << std::endl << "..." << std::endl; for (size_t i = n-100; i < n; ++i) { if (i > n-100) { // Print a delimiter if (i%5 == 0) std::cout << std::endl; else std::cout << " "; } std::cout << first[i]; } } std::cout << std::endl; } void bubbleSort( std::vector::iterator a, // First element of the segment, std::vector::iterator last // element after the last ) { bool wasInversions = true; int pass = 0; size_t n = last - a; while (wasInversions) { wasInversions = false; for (size_t i = 0; i < n-1-pass; ++i) { if (a[i] > a[i+1]) { std::swap(a[i], a[i+1]); wasInversions = true; } } ++pass; } } void directSort( std::vector::iterator a, // Beginning of array segment to sort std::vector::iterator last // After-end of array segment ) { size_t n = last - a; for (size_t i = 0; i < n-1; ++i) { size_t indMin = i; for (size_t j = i+1; j < n; ++j) { if (a[j] < a[indMin]) indMin = j; } if (indMin != i) std::swap(a[i], a[indMin]); } } void heapSort( std::vector::iterator a, // First element of the segment, std::vector::iterator last // element after the last ) { //... to be implemented... std::cout << "heapSort is not implemented yet..." << std::endl; } void bubbleDown( std::vector::iterator a, // First element of the segment, size_t n, // size of array segment, size_t k // Element to sieve ) { while (true) { size_t s1 = 2*k + 1; // Left son of k if (s1 >= n) break; size_t s2 = s1 + 1; // Right son of k size_t s = s1; // Elder son if (s2 < n && a[s2] > a[s1]) s = s2; if (a[k] >= a[s]) break; std::swap(a[k], a[s]); k = s; } } void mergeSortTopBottom( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last // After-end of array segment to sort ) { size_t n = last - first; std::vector tmpMem(n); mergeSortRecursive( first, last, tmpMem.begin() ); } void mergeSortRecursive( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last, // After-end of array segment to sort std::vector::iterator tmpMem // Beginnig of temporary memory ) { //... to be implemented... std::cout << "mergeSortRecursive is not implemented yet..." << std::endl; } void mergeSortBottomTop( std::vector::iterator first, // Beginning of array segment to sort std::vector::iterator last // After-end of array segment to sort ) { //... to be implemented... std::cout << "mergeSortBottomTop is not implemented yet..." << std::endl; } void merge( std::vector::iterator a0, // Beginning of first array std::vector::iterator a1, // After-end of first array std::vector::iterator b0, // Beginning of second array std::vector::iterator b1, // After-end of second array std::vector::iterator c // Beginning of resulting array ) { while (a0 != a1 && b0 != b1) { if (*a0 <= *b0) { *c = *a0; ++a0; } else { *c = *b0; ++b0; } ++c; } while (a0 != a1) { *c = *a0; ++c; ++a0; } while (b0 != b1) { *c = *b0; ++c; ++b0; } }