Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <chrono>
- #include <ratio>
- #include <algorithm>
- #include <ctime>
- #include <cstdlib>
- namespace sort
- {
- void bubble_sort(int* t, size_t n)
- {
- for (unsigned int i = n-1; i >= 1; i--)
- for (unsigned int j = 0; j < i; j++)
- if (t[j+1] < t[j])
- std::swap(t[j], t[j+1]);
- }
- int partition(int* t, unsigned int s, unsigned int e)
- {
- int pivot = t[s];
- int l = s+1;
- int r = e;
- bool done = false;
- while(!done)
- {
- while (l <= r && t[l] <= pivot)
- l++;
- while (t[r] >= pivot && r >= l)
- r--;
- if (r < l)
- done = true;
- else
- std::swap(t[l], t[r]);
- }
- std::swap(t[s], t[r]);
- return r;
- }
- void quicksort(int* t, unsigned int s, unsigned int e)
- {
- if (s < e)
- {
- int p = partition(t, s, e);
- quicksort(t, s, p-1);
- quicksort(t, p+1, e);
- }
- }
- }
- int main(void)
- {
- const unsigned int s = 1000;
- int tab[s];
- int stab[s];
- srand(time(0));
- for (unsigned int i = 0; i < s; i++)
- {
- tab[i] = rand()%s;
- }
- std::chrono::high_resolution_clock::time_point sp;
- std::chrono::high_resolution_clock::time_point ep;
- std::chrono::duration<double, std::milli> d;
- std::memcpy(stab, tab, s*sizeof(int));
- std::cout << "Bubble sort:" << std::endl;
- sp = std::chrono::high_resolution_clock::now();
- sort::bubble_sort(stab, s);
- ep = std::chrono::high_resolution_clock::now();
- d = ep-sp;
- std::cout << "Time: " << d.count() << "ms" << std::endl << std::endl;
- std::memcpy(stab, tab, s*sizeof(int));
- std::cout << "Quick sort:" << std::endl;
- sp = std::chrono::high_resolution_clock::now();
- sort::quicksort(stab, 0, s-1);
- ep = std::chrono::high_resolution_clock::now();
- d = ep-sp;
- std::cout << "Time: " << d.count() << "ms" << std::endl << std::endl;
- //for (const auto& i : stab) std::cout << i << std::endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment