Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // NOT WEAPONS GRADE. Lacks many usability features.
- // It's only a proof of concept for swap-only sorting in C++
- #pragma once
- #ifndef __HEAPSORT_H__
- #define __HEAPSORT_H__
- namespace HeapSort
- {
- namespace detail
- {
- size_t left(size_t i)
- {
- return (2*i)+1;
- }
- size_t right(size_t i)
- {
- return (2*i)+2;
- }
- template<typename T, typename Comparator>
- void sink(T *begin, size_t n, size_t idx, Comparator const &c)
- {
- for(size_t leftIdx=left(idx); leftIdx<n; leftIdx=left(idx))
- {
- size_t rightIdx = right(idx);
- T &leftItem = *(begin+leftIdx);
- T &item = *(begin+idx);
- if(rightIdx>=n)
- {
- using namespace std; // It will be used only as last resort for resolving swap()
- if(c(item,leftItem))
- swap(item,leftItem);
- return;
- }
- T &rightItem = *(begin+rightIdx);
- if(c(rightItem,item) && c(leftItem,item))
- return;
- if(c(leftItem,rightItem))
- {
- using namespace std; // It will be used only as last resort for resolving swap()
- swap(item,rightItem);
- idx = rightIdx;
- continue;
- }
- {
- using namespace std; // It will be used only as last resort for resolving swap()
- swap(item,leftItem);
- }
- idx = leftIdx;
- }
- }
- } // namespace detail
- template<typename T, typename Comparator>
- void sort(T *begin, T *end, Comparator const &c = Comparator())
- {
- size_t n = end-begin;
- if(n<=1)
- return;
- if(n==2)
- {
- if(c(*(begin+1),*begin))
- {
- using namespace std; // It will be used only as last resort for resolving swap()
- swap(*(begin+1),*begin);
- }
- return;
- }
- // #2
- for(int idx=n/2-1; idx>=0; --idx)
- {
- detail::sink(begin, n, idx, c);
- }
- // #3
- while(n>1)
- {
- {
- using namespace std; // It will be used only as last resort for resolving swap()
- swap(*begin,*(begin+n-1));
- }
- --n;
- detail::sink(begin, n, 0, c);
- }
- }
- template<typename T>
- void sort(T *begin, T *end)
- {
- sort(begin,end,std::less<T>());
- }
- } // namespace HeapSort
- #endif // __HEAPSORT_H__
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement