Mercurial > lbo > hg > ccplay
view sorting.cc @ 24:b89680a8af68 default tip
graph: detect negative cycles
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 09 Apr 2023 17:27:20 +0200 |
parents | 68cf11026c57 |
children |
line wrap: on
line source
#include <cassert> #include "lib/exec.h" #include <algorithm> #include <functional> #include <iostream> #include <ranges> #include <span> #include <string> #include <utility> #include <vector> using namespace std; template<typename T> int partition(vector<T>& v, int left, int right) { int mid = (left+right)/2; T piv = v[mid]; while (left <= right) { while (v[left] < piv) left++; while (v[right] > piv) right--; if (left < right) { T b = v[left]; v[left] = v[right]; v[right] = b; left++; right--; } else if (left == right) { break; } } return left; } template<typename T> void quicksort(vector<T>& v, int start=0, int end=-1) { if (end < 0) end = v.size()-1; if (end-start < 2) return; int mid = partition(v, start, end); quicksort(v, start, mid); quicksort(v, mid, end); } template<typename T> void quicksort2(vector<T>& v, int start=0, int end=-1) { if (end < 0) end = v.size()-1; int mid = partition(v, start, end); if (mid-1 > start) quicksort(v, start, mid); if (end > mid) quicksort(v, mid, end); } template<typename T> void merge(vector<T>& v, int vlen, vector<T>& w) { // v must have space for w. assert(v.size()-vlen >= w.size()); // Pointers to individual arrays. int a = vlen-1, b = w.size()-1; int i = v.size()-1; while (i >= 0) { if (v[a] >= w[b]) { v[i] = v[a]; a--; } else { v[i] = w[b]; b--; } i--; } } void sort_anagram(vector<string>& in) { std::sort(in.begin(), in.end(), [](string a, string b) { std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); return a < b; }); } template<typename T> int shifted_binary_search(const vector<T>& v, const T& elem, int start=0, int end=-1, int off=-1) { if (end < 0) end = v.size()-1; // end is past-the-last element. if (off < 0) { // First find offset. int lo = start, mid = (start+end)/2, hi = end; while (lo < mid) { if (v[mid] > v[hi]) { lo = mid; mid = (lo+hi)/2; continue; } else if (v[lo] > v[mid]) { hi = mid; mid = (lo+hi)/2; continue; } else { break; } } return hi; } return end; } pair<size_t, size_t> heap_children(size_t i) { return make_pair(2*i+1, 2*i+2); } template<typename T> void heap_sift_down(span<T> v, size_t i) { if (i >= v.size()) return; pair<size_t, size_t> children = heap_children(i); // Special check if we are down in the tree. if (get<0>(children) >= v.size()) return; else if (get<1>(children) >= v.size()) { size_t left = get<0>(children); T& target = v[i] > v[left] ? v[i] : v[left]; swap(target, v[i]); return; } T& left = v[get<0>(children)], &right = v[get<1>(children)]; // Order already correct. if (max(left, right) < v[i]) return; // Recur: if (left > right) { swap(v[i], left); heap_sift_down(v, get<0>(children)); } else { swap(v[i], right); heap_sift_down(v, get<1>(children)); } } template<typename T> void heap_sift_up(vector<T>& v, size_t i) { if (i == 0 || i >= v.size()) return; size_t parent_ix = (i-1)/2; T& parent = v.at(parent_ix); T& current = v.at(i); if (parent < current) { swap(parent, current); heap_sift_up(v, parent_ix); } } enum class SiftDirection { Up, Down }; template<typename T> void make_into_heap(vector<T>& v, SiftDirection direction = SiftDirection::Down) { if (direction == SiftDirection::Down) for (ssize_t i = v.size()-1; i >= 0; i--) { heap_sift_down(span(v), i); } else for (size_t i = 0; i < v.size(); i++) { heap_sift_up(v, i); } } template<typename T> void flatten_heap(vector<T>& v) { for (int i = v.size()-1; i > 0; i--) { swap(v[0], v[i]); heap_sift_down(span(v.begin(), v.begin()+i), 0); } } //template<typename T, typename R> requires (range<R> and is_same<range_value_t<R>, T>) template<typename T> void heap_sort(vector<T>& rng) { make_into_heap(rng); flatten_heap(rng); return; } int main(void) { vector<string> v{"hello", "olleh", "abc", "bca", "world", "wrlod"}; vector<int> vi{5,5,6,1,3,2,5,8,9}; timeit_f([&]() { heap_sort(vi); }, "heapsort"); fmt::print("{}\n", vi); return 0; }