Mercurial > lbo > hg > ccplay
view sorting.cc @ 1:ec6009463e1c
Timing infrastructure, cmake build
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sun, 05 Mar 2023 10:01:51 +0100 |
parents | 85a51415f042 |
children | 86e76ae3ac8a |
line wrap: on
line source
#include <cassert> #include <algorithm> #include <iostream> #include <string> #include <vector> using std::vector, std::string; template<typename T> int partition(vector<T>& v, int left, int right) { int mid = (left+right)/2; while (left <= right) { while (v[left] < v[mid]) left++; while (v[right] > v[mid]) 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; } } int main(void) { vector<string> v{"hello", "olleh", "abc", "bca", "world", "wrlod"}; std::cout << shifted_binary_search({5,6,1,2,3}, 1) << "\n"; for (const auto& a : v) std::cout << a << " "; std::cout << "\n"; return 0; }