Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <vector>
- #include <iostream>
- #include <algorithm>
- template <typename T>
- std::ostream& operator << (std::ostream& out, const std::vector<T>& vec) {
- if (vec.empty()) {
- return out << "[]";
- }
- out << '[';
- auto begin = vec.cbegin();
- auto end = vec.cend() - 1;
- while (begin != end) {
- out << *begin << ", ";
- ++begin;
- }
- return out << *end << ']';
- }
- void bubble_sort(std::vector<int>& vec) {
- bool was_sorted = false;
- for (int i = 0; i < vec.size() && !was_sorted; i++) {
- was_sorted = true;
- for (int j = 0; j < vec.size() - 1 - i; j++) {
- if (vec[j + 1] < vec[j]) {
- std::swap(vec[j], vec[j + 1]);
- was_sorted = false;
- }
- }
- }
- }
- void selection_sort(std::vector<int>& vec) {
- for (int i = 0; i < vec.size(); i++) {
- auto min_pos = std::min_element(vec.begin() + i, vec.end());
- if (*min_pos < vec[i]) {
- std::swap(vec[i], *min_pos);
- }
- }
- }
- void insertion_sort(std::vector<int>& vec) {
- if (vec.size() <= 1) return;
- for (int i = 1; i < vec.size(); i++) {
- for (int j = i; j > 0 && vec[j - 1] > vec[j]; j--) {
- std::swap(vec[j - 1], vec[j]);
- }
- }
- }
- int main() {
- /**
- * QuickSort, MergeSort, BucketSort, IntroSort, BubbleSort,
- * HeapSort, SelectionSort, InsertionSort, CountingSort, RadixSort
- * TimSort, ShakerSort, ...
- */
- /**
- * BubbleSort [x] [x]
- * SelectionSort [x] [x]
- * InsertionSort [x] [x]
- * MergeSort [ ] [ ]
- * HeapSort [ ] [ ]
- * QuickSort [x] [ ]
- */
- /**
- * O(n^2):
- * SelectionSort
- * BubbleSort
- * InsertionSort
- * O(n*log_n):
- * QuickSort
- */
- std::vector<int> sample = {5, 0, 19, 9, 22, 18, 3, 1, 7};
- std::vector<int> to_sort = sample;
- std::cout << to_sort << '\n';
- bubble_sort(to_sort);
- std::cout << to_sort << '\n';
- to_sort = sample;
- std::cout << '\n';
- std::cout << to_sort << '\n';
- selection_sort(to_sort);
- std::cout << to_sort << '\n';
- to_sort = sample;
- std::cout << '\n';
- std::cout << to_sort << '\n';
- insertion_sort(to_sort);
- std::cout << to_sort << '\n';
- to_sort = sample;
- std::cout << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement