Name: Anonymous 2011-06-25 1:35
understand the selection sort algorithm. Should I continue to be a computer scinece major?
#ifndef PROG_ALGORITHM_SORT_HPP
#define PROG_ALGORITHM_SORT_HPP
#include <prog/algorithm/heap.hpp>
#include <prog/algorithm/move.hpp>
#include <prog/iterator/operations.hpp>
#include <prog/math/bitwise.hpp>
namespace prog
{
namespace detail
{
template <class ForwardIterator, class Compare>
void sort3(ForwardIterator x, ForwardIterator y, ForwardIterator z, Compare comp) {
if (!comp(*y, *x)) {
if (!comp(*z, *y)) {
return;
}
swap(*y, *z);
if (!comp(*y, *x)) {
return;
}
swap(*x, *y);
return;
}
if (!comp(*y, *z)) {
swap(*x, *z);
return;
}
swap(*x, *y);
if (!comp(*z, *y)) {
return;
}
swap(*y, *z);
}
template <class BidirectionalIterator, class Compare>
void insertion_sort(
BidirectionalIterator first,
BidirectionalIterator last,
Compare comp,
bidirectional_iterator_tag
) {
if (first != last) {
for (BidirectionalIterator current = first; ++current != last; ) {
typename iterator_traits<BidirectionalIterator>::value_type value(::prog::move(*current));
BidirectionalIterator next = current;
if (comp(value, *first)) {
::prog::move_backward(first, current, ++next);
*first = ::prog::move(value);
}
else {
for (BidirectionalIterator prev = next; comp(value, *(--prev)); next = prev) {
*next = ::prog::move(*prev);
}
*next = ::prog::move(value);
}
}
}
}
template <class RandomAccessIterator, class Compare>
void insertion_sort(
RandomAccessIterator first,
RandomAccessIterator last,
Compare comp,
random_access_iterator_tag
) {
typename iterator_traits<RandomAccessIterator>::difference_type count = last - first;
if (count <= 2) {
if ((count == 2) && comp(*(--last), *first)) {
swap(*first, *last);
}
return;
}
RandomAccessIterator prev = first + 2;
::prog::detail::sort3(first, first + 1, prev, comp);
for (RandomAccessIterator current = prev + 1; current != last; prev = current, ++current) {
if (comp(*current, *prev)) {
typename iterator_traits<RandomAccessIterator>::value_type value(::prog::move(*current));
RandomAccessIterator prev2 = prev;
prev = current;
do {
*prev = ::prog::move(*prev2);
prev = prev2;
}
while ((prev > first) && comp(value, *--prev2));
*prev = ::prog::move(value);
}
}
}
template <class RandomAccessIterator>
PROGFORCEINLINE unsigned int intro_sort_depth(RandomAccessIterator first, RandomAccessIterator last) {
typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
typedef typename make_unsigned<difference_type>::type size_type;
return static_cast<unsigned int>(::prog::log2(static_cast<size_type>(last - first)) << 1);
}
template <class RandomAccessIterator, class Compare>
void intro_sort(RandomAccessIterator first, RandomAccessIterator last, unsigned int depth, Compare comp) {
for (;;) {
typename iterator_traits<RandomAccessIterator>::difference_type count = last - first;
if (count <= 2) {
if ((count == 2) && comp(*(--last), *first)) {
swap(*first, *last);
}
return;
}
if (count <= 16) {
RandomAccessIterator prev = first + 2;
::prog::detail::sort3(first, first + 1, prev, comp);
for (RandomAccessIterator current = prev + 1; current != last; prev = current, ++current) {
if (comp(*current, *prev)) {
typename iterator_traits<RandomAccessIterator>::value_type value(::prog::move(*current));
RandomAccessIterator prev2 = prev;
prev = current;
do {
*prev = ::prog::move(*prev2);
prev = prev2;
}
while ((prev > first) && comp(value, *--prev2));
*prev = ::prog::move(value);
}
}
return;
}
if (depth == 0) {
::prog::make_heap(first, last, comp);
::prog::sort_heap(first, last, comp);
return;
}
RandomAccessIterator tail = last - 1;
RandomAccessIterator pivot = first;
RandomAccessIterator pivot2 = tail - 1;
::prog::detail::sort3(first, tail, first + (count >> 1), comp);
while (pivot <= pivot2) {
if (!comp(*pivot, *tail)) {
while (!comp(*pivot2, *tail)) --pivot2;
if (pivot >= pivot2) {
break;
}
swap(*pivot, *pivot2);
}
++pivot;
}
swap(*pivot, *tail);
depth = (depth >> 1) + (depth >> 4);
if ((first - pivot) < (last - pivot)) {
::prog::detail::intro_sort(first, pivot, depth, comp);
first = pivot + 1;
}
else {
::prog::detail::intro_sort(pivot + 1, last, depth, comp);
last = pivot;
}
}
}
template <size_t Size> struct radix_sort_key;
template <> struct radix_sort_key<1> { typedef uint8_t type; };
template <> struct radix_sort_key<2> { typedef uint16_t type; };
template <> struct radix_sort_key<4> { typedef uint32_t type; };
template <> struct radix_sort_key<8> { typedef uint64_t type; };
}
template <class ForwardIterator, class Compare>
PROGFORCEINLINE void bubble_sort(ForwardIterator first, ForwardIterator last, Compare comp) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
if (first == last) {
return;
}
bool swapped = true;
while (swapped) {
swapped = false;
for (ForwardIterator left = first, right = first; ++right != last; ++left) {
if (comp(*right, *left)) {
swap(*left, *right);
swapped = true;
}
}
}
}
template <class ForwardIterator>
PROGFORCEINLINE void bubble_sort(ForwardIterator first, ForwardIterator last) {
::prog::bubble_sort(first, last, detail::iter_less<ForwardIterator>());
}
template <class ForwardIterator, class Compare>
PROGFORCEINLINE void comb_sort(ForwardIterator first, ForwardIterator last, Compare comp) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
difference_type gap = ::prog::distance(first, last);
bool swapped = true;
while ((gap > 1) || swapped) {
if (gap > 1) {
gap = static_cast<difference_type>(gap / 1.247330950103979);
}
swapped = false;
for (ForwardIterator left = first, right = ::prog::next(first, gap); right != last; ++left, ++right) {
if (comp(*right, *left)) {
swap(*left, *right);
swapped = true;
}
}
}
}
template <class ForwardIterator>
PROGFORCEINLINE void comb_sort(ForwardIterator first, ForwardIterator last) {
::prog::comb_sort(first, last, detail::iter_less<ForwardIterator>());
}
template <class BidirectionalIterator, class Compare>
PROGFORCEINLINE void heap_sort(BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
PROG_ASSERT_BIDIRECTIONAL_ITERATOR(BidirectionalIterator);
::prog::make_heap(first, last, comp);
::prog::sort_heap(first, last, comp);
}
template <class BidirectionalIterator>
PROGFORCEINLINE void heap_sort(BidirectionalIterator first, BidirectionalIterator last) {
::prog::heap_sort(first, last, detail::iter_less<BidirectionalIterator>());
}
template <class BidirectionalIterator, class Compare>
PROGHIDDENINLINE void insertion_sort(BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
PROG_ASSERT_BIDIRECTIONAL_ITERATOR(BidirectionalIterator);
typedef typename iterator_traits<BidirectionalIterator>::iterator_category category;
return ::prog::detail::insertion_sort(first, last, comp, category());
}
template <class BidirectionalIterator>
PROGFORCEINLINE void insertion_sort(BidirectionalIterator first, BidirectionalIterator last) {
PROG_ASSERT_BIDIRECTIONAL_ITERATOR(BidirectionalIterator);
typedef typename iterator_traits<BidirectionalIterator>::iterator_category category;
return ::prog::detail::insertion_sort(first, last, detail::iter_less<BidirectionalIterator>(), category());
}
template <class RandomAccessIterator, class Compare>
void quick_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
PROG_ASSERT_RANDOM_ACCESS_ITERATOR(RandomAccessIterator);
typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
for (;;) {
typename iterator_traits<RandomAccessIterator>::difference_type count = last - first;
if (count <= 1) {
return;
}
RandomAccessIterator tail = last - 1;
RandomAccessIterator pivot = first;
RandomAccessIterator pivot2 = tail - 1;
::prog::detail::sort3(first, tail, first + (count >> 1), comp);
while (pivot <= pivot2) {
if (!comp(*pivot, *tail)) {
while (!comp(*pivot2, *tail)) --pivot2;
if (pivot >= pivot2) {
break;
}
swap(*pivot, *pivot2);
}
++pivot;
}
swap(*pivot, *tail);
if ((first - pivot) < (last - pivot)) {
::prog::quick_sort(first, pivot, comp);
first = pivot + 1;
}
else {
::prog::quick_sort(pivot + 1, last, comp);
last = pivot;
}
}
}
template <class RandomAccessIterator>
PROGFORCEINLINE void quick_sort(RandomAccessIterator first, RandomAccessIterator last) {
::prog::quick_sort(first, last, detail::iter_less<RandomAccessIterator>());
}
template <class RandomAccessIterator, class ExtractKey>
void radix_sort(
RandomAccessIterator first,
RandomAccessIterator last,
RandomAccessIterator buffer,
ExtractKey extract_key
) {
PROG_ASSERT_RANDOM_ACCESS_ITERATOR(RandomAccessIterator);
typedef typename detail::radix_sort_key<sizeof(extract_key(*first))>::type key_type;
ptrdiff_t count = last - first;
if (count > 0) {
RandomAccessIterator locations[256];
size_t histogram[256];
RandomAccessIterator source = first;
RandomAccessIterator destination = buffer;
for (size_t octet = 0; octet < sizeof(key_type); ++octet) {
key_type const shift = static_cast<key_type>(octet << 3);
::prog::memset(histogram, 0, sizeof(histogram));
for (ptrdiff_t index = 0; index < count; ++index) {
++histogram[(static_cast<key_type>(extract_key(*(source + index))) >> shift) & 255];
}
RandomAccessIterator location = destination;
for (size_t index = 0; index < 256; ++index) {
locations[index] = location;
location += histogram[index];
}
RandomAccessIterator current = source;
for (ptrdiff_t index = 0; index < count; ++current, ++index) {
*(locations[(static_cast<key_type>(extract_key(*(source + index))) >> shift) & 255]++) = ::prog::move(*current);
}
::prog::swap(source, destination);
}
}
}
template <class BidirectionalIterator, class Compare>
PROGFORCEINLINE void rake_sort(BidirectionalIterator first, BidirectionalIterator last, Compare comp) {
PROG_ASSERT_BIDIRECTIONAL_ITERATOR(BidirectionalIterator);
typedef typename iterator_traits<BidirectionalIterator>::difference_type difference_type;
for (difference_type gap = ::prog::distance(first, last); gap > 8; gap = static_cast<difference_type>(gap / 1.247330950103979)) {
for (BidirectionalIterator left = first, right = ::prog::next(first, gap); right != last; ++left, ++right) {
if (comp(*right, *left)) {
swap(*left, *right);
}
}
}
::prog::insertion_sort(first, last, comp);
}
template <class BidirectionalIterator>
PROGFORCEINLINE void rake_sort(BidirectionalIterator first, BidirectionalIterator last) {
::prog::rake_sort(first, last, detail::iter_less<BidirectionalIterator>());
}
template <class ForwardIterator, class Compare>
PROGFORCEINLINE void selection_sort(ForwardIterator first, ForwardIterator last, Compare comp) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
for ( ; first != last; ++first) {
ForwardIterator minimum = first;
for (ForwardIterator next = first; ++next != last; ) {
if (comp(*next, *minimum)) {
minimum = next;
}
}
if (first != minimum) {
swap(*first, *minimum);
}
}
}
template <class ForwardIterator>
PROGFORCEINLINE void selection_sort(ForwardIterator first, ForwardIterator last) {
::prog::selection_sort(first, last, detail::iter_less<ForwardIterator>());
}
template <class RandomAccessIterator, class Compare>
PROGFORCEINLINE void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) {
PROG_ASSERT_RANDOM_ACCESS_ITERATOR(RandomAccessIterator);
unsigned int depth = ::prog::detail::intro_sort_depth(first, last);
::prog::detail::intro_sort(first, last, depth, comp);
}
template <class RandomAccessIterator>
PROGFORCEINLINE void sort(RandomAccessIterator first, RandomAccessIterator last) {
PROG_ASSERT_RANDOM_ACCESS_ITERATOR(RandomAccessIterator);
unsigned int depth = ::prog::detail::intro_sort_depth(first, last);
::prog::detail::intro_sort(first, last, depth, detail::iter_less<RandomAccessIterator>());
}
template <class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp) {
PROG_ASSERT_RANDOM_ACCESS_ITERATOR(RandomAccessIterator);
::prog::make_heap(first, middle, comp);
for (RandomAccessIterator current = middle; current != last; ++current) {
if (comp(*current, *first)) {
swap(*current, *first);
::prog::push_heap(first, middle, comp);
}
}
::prog::sort_heap(first, middle, comp);
}
template <class RandomAccessIterator>
PROGFORCEINLINE void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last) {
::prog::partial_sort(first, middle, last, detail::iter_less<RandomAccessIterator>());
}
template <class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator partial_sort_copy(
InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp
) {
RandomAccessIterator result = result_first;
if (result != result_last) {
for ( ; (first != last) && (result != result_last); ++first, ++result) {
*result = *first;
}
::prog::make_heap(result_first, result, comp);
for ( ; first != last; ++first) {
if (comp(*first, *result_first)) {
*result_first = *first;
::prog::push_heap(result_first, result, comp);
}
}
::prog::sort_heap(result_first, result, comp);
}
return result;
}
template <class InputIterator, class RandomAccessIterator>
PROGFORCEINLINE RandomAccessIterator partial_sort_copy(
InputIterator first,
InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last
) {
return ::prog::partial_sort_copy(first, last, result_first, result_last, detail::iter_less<RandomAccessIterator>());
}
template <class ForwardIterator, class Compare>
ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
if (first != last) {
for (ForwardIterator next = first; ++next != last; ++first) {
if (comp(*next, *first)) {
return next;
}
}
}
return last;
}
template <class ForwardIterator>
PROGFORCEINLINE ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last) {
return ::prog::is_sorted_until(first, last, detail::iter_less<ForwardIterator>());
}
template <class ForwardIterator>
PROGFORCEINLINE bool is_sorted(ForwardIterator first, ForwardIterator last) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
return (last == ::prog::is_sorted_until(first, last));
}
template <class ForwardIterator, class BinaryPredicate>
PROGFORCEINLINE bool is_sorted(ForwardIterator first, ForwardIterator last, BinaryPredicate pred) {
PROG_ASSERT_FORWARD_ITERATOR(ForwardIterator);
return (last == ::prog::is_sorted_until(first, last, pred));
}
}
#endif