You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
491 lines
16 KiB
C++
491 lines
16 KiB
C++
// Copyright (C) 2005 Davis E. King (davis@dlib.net)
|
|
// License: Boost Software License See LICENSE.txt for the full license.
|
|
#ifndef DLIB_SORt_
|
|
#define DLIB_SORt_
|
|
|
|
#include "algs.h"
|
|
#include <functional>
|
|
|
|
namespace dlib
|
|
{
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
inline void qsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right,
|
|
const compare& comp
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp where comp is a function
|
|
object with the same syntax as std::less<>
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using a quick sort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void hsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right,
|
|
const compare& comp
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp where comp is a function
|
|
object with the same syntax as std::less<>
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using a heapsort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void isort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right,
|
|
const compare& comp
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp where comp is a function
|
|
object with the same syntax as std::less<>
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using an insertion sort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
inline void qsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by std::less
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using a quick sort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
void hsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by std::less
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using a heapsort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
void isort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
);
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by std::less
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
- left <= right
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- sorts using an insertion sort algorithm
|
|
!*/
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
// ----------------------------------------------------------------------------------------
|
|
// IMPLEMENTATION DETAILS
|
|
// ----------------------------------------------------------------------------------------
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
namespace sort_helpers
|
|
{
|
|
template <typename T>
|
|
inline const std::less<T> comp (const T&)
|
|
{
|
|
return std::less<T>();
|
|
}
|
|
|
|
template <
|
|
typename T,
|
|
typename Y,
|
|
typename compare
|
|
>
|
|
inline unsigned long qsort_partition (
|
|
T& array,
|
|
Y& pivot,
|
|
const unsigned long left,
|
|
const unsigned long right,
|
|
const compare& comp
|
|
)
|
|
/*!
|
|
requires
|
|
- &pivot == &array[right]
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp
|
|
- left and right are within the bounts of the array
|
|
- left < right
|
|
ensures
|
|
- returns a number called partition_element such that:
|
|
- left <= partition_element <= right
|
|
- all elements in #array < #array[partition_element] have
|
|
indices >= left and < partition_element
|
|
- all elements in #array > #array[partition_element] have
|
|
indices > partition_element and <= right
|
|
!*/
|
|
{
|
|
DLIB_ASSERT (&pivot == &array[right] && left < right,
|
|
"\tunsigned long qsort_partition()"
|
|
<< "\n\t&pivot: " << &pivot
|
|
<< "\n\t&array[right]: " << &array[right]
|
|
<< "\n\tleft: " << left
|
|
<< "\n\tright: " << right );
|
|
|
|
exchange(array[(right-left)/2 +left],pivot);
|
|
|
|
unsigned long i = left;
|
|
for (unsigned long j = left; j < right; ++j)
|
|
{
|
|
if (comp(array[j] , pivot))
|
|
{
|
|
swap(array[i],array[j]);
|
|
++i;
|
|
}
|
|
}
|
|
exchange(array[i],pivot);
|
|
|
|
return i;
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void qsort_array_main (
|
|
T& array,
|
|
const unsigned long left,
|
|
const unsigned long right,
|
|
unsigned long depth_check,
|
|
const compare& comp
|
|
)
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp
|
|
- the items in array must be swappable by a global swap()
|
|
- left and right are within the bounds of array
|
|
i.e. array[left] and array[right] are valid elements
|
|
ensures
|
|
- for all elements in #array between and including left and right the
|
|
ith element is < the i+1 element
|
|
- will only recurse about as deep as log(depth_check) calls
|
|
- sorts using a quick sort algorithm
|
|
!*/
|
|
{
|
|
if ( left < right)
|
|
{
|
|
if (right-left < 30 || depth_check == 0)
|
|
{
|
|
hsort_array(array,left,right,comp);
|
|
}
|
|
else
|
|
{
|
|
// The idea here is to only let quick sort go about log(N)
|
|
// calls deep before it kicks into something else.
|
|
depth_check >>= 1;
|
|
depth_check += (depth_check>>4);
|
|
|
|
unsigned long partition_element =
|
|
qsort_partition(array,array[right],left,right,comp);
|
|
|
|
if (partition_element > 0)
|
|
qsort_array_main(array,left,partition_element-1,depth_check,comp);
|
|
qsort_array_main(array,partition_element+1,right,depth_check,comp);
|
|
}
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void heapify (
|
|
T& array,
|
|
const unsigned long start,
|
|
const unsigned long end,
|
|
unsigned long i,
|
|
const compare& comp
|
|
)
|
|
/*!
|
|
requires
|
|
- T implements operator[]
|
|
- the items in array must be comparable by comp
|
|
- the items in array must be swappable by a global swap()
|
|
- start, end, and i are within the bounds of array
|
|
i.e. array[start], array[end], and array[i] are valid elements
|
|
- start <= i <= end
|
|
- array[i/2] is a max heap
|
|
- array[i/2+1] is a max heap
|
|
- start and end specify the range of the array we are working with.
|
|
ensures
|
|
- array[i] is now a max heap
|
|
!*/
|
|
{
|
|
DLIB_ASSERT (start <= i && i <= end,
|
|
"\tvoid heapify()"
|
|
<< "\n\tstart: " << start
|
|
<< "\n\tend: " << end
|
|
<< "\n\ti: " << i );
|
|
|
|
bool keep_going = true;
|
|
unsigned long left;
|
|
unsigned long right;
|
|
unsigned long largest;
|
|
while (keep_going)
|
|
{
|
|
keep_going = false;
|
|
left = (i<<1)+1-start;
|
|
right = left+1;
|
|
|
|
if (left <= end && comp(array[i] , array[left]))
|
|
largest = left;
|
|
else
|
|
largest = i;
|
|
|
|
if (right <= end && comp(array[largest] , array[right]))
|
|
largest = right;
|
|
|
|
if (largest != i)
|
|
{
|
|
exchange(array[i],array[largest]);
|
|
i = largest;
|
|
keep_going = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
}
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
inline void qsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
)
|
|
{
|
|
using namespace sort_helpers;
|
|
qsort_array(array,left,right,comp(array[left]));
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
void hsort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
)
|
|
{
|
|
using namespace sort_helpers;
|
|
hsort_array(array,left,right,comp(array[left]));
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T
|
|
>
|
|
void isort_array (
|
|
T& array,
|
|
unsigned long left,
|
|
unsigned long right
|
|
)
|
|
{
|
|
using namespace sort_helpers;
|
|
isort_array(array,left,right,comp(array[left]));
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void isort_array (
|
|
T& array,
|
|
const unsigned long left,
|
|
const unsigned long right,
|
|
const compare& comp
|
|
)
|
|
{
|
|
DLIB_ASSERT (left <= right,
|
|
"\tvoid isort_array()"
|
|
<< "\n\tleft: " << left
|
|
<< "\n\tright: " << right );
|
|
using namespace sort_helpers;
|
|
|
|
unsigned long pos;
|
|
for (unsigned long i = left+1; i <= right; ++i)
|
|
{
|
|
// everything from left to i-1 is sorted.
|
|
pos = i;
|
|
for (unsigned long j = i-1; comp(array[pos] , array[j]); --j)
|
|
{
|
|
exchange(array[pos],array[j]);
|
|
pos = j;
|
|
|
|
if (j == left)
|
|
break;
|
|
}
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void qsort_array (
|
|
T& array,
|
|
const unsigned long left,
|
|
const unsigned long right,
|
|
const compare& comp
|
|
)
|
|
{
|
|
DLIB_ASSERT (left <= right,
|
|
"\tvoid qsort_array()"
|
|
<< "\n\tleft: " << left
|
|
<< "\n\tright: " << right );
|
|
|
|
sort_helpers::qsort_array_main(array,left,right,right-left,comp);
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
template <
|
|
typename T,
|
|
typename compare
|
|
>
|
|
void hsort_array (
|
|
T& array,
|
|
const unsigned long left,
|
|
const unsigned long right,
|
|
const compare& comp
|
|
)
|
|
{
|
|
DLIB_ASSERT (left <= right,
|
|
"\tvoid hsort_array()"
|
|
<< "\n\tleft: " << left
|
|
<< "\n\tright: " << right );
|
|
|
|
if (right-left < 30)
|
|
{
|
|
isort_array(array,left,right,comp);
|
|
return;
|
|
}
|
|
|
|
// turn array into a max heap
|
|
for (unsigned long i = left+((right-left)>>1);; --i)
|
|
{
|
|
sort_helpers::heapify(array,left,right,i,comp);
|
|
if (i == left)
|
|
break;
|
|
}
|
|
|
|
// now sort the array
|
|
for (unsigned long i = right; i > left;)
|
|
{
|
|
exchange(array[i],array[left]);
|
|
sort_helpers::heapify(array,left,--i,left,comp);
|
|
}
|
|
}
|
|
|
|
// ----------------------------------------------------------------------------------------
|
|
|
|
}
|
|
|
|
#endif // DLIB_SORt_
|
|
|