More
Array Sorting
by Malcolm Phillips
<
Back to other Array Sorting Techniques
Binary Tree Sort
Well, Exchanging, Inserting and
Merging techniques have already provided plenty to talk about. But wait, we're only just
getting started! One conceptually easy way to
sort items is to insert them into a binary tree, and then read out all the items using an in-order traversal. This
is known, of course, as Tree sort. Beginners often mistake this for an O(n)
sorting algorithm, because they fail to take into account two things:
The tree grows as you insert more items, meaning that future inserts take
longer, and
The tree might degenerate into a linked-list, if for example, items are inserted
in sorted order.
It is in fact O(n2), but with some luck in the order items are
inserted, it can run in O(nlogn) time.
Tree Sort is stable.
[hide source code]
template <class T>
void
BinaryTreeSort(T a[], int n) {
int idx = 0;
Node<T> *head = NULL, *const buf =
new Node<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
TreeInsert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
template
<class T, class TNode>
void
TreeDumpToArray(T a[], int &idx, const TNode *node) {
while (node != NULL) {
TreeDumpToArray(a, idx, node->left);
a[idx++] = node->item;
node = node->right;
}
}
template <class T>
struct Node {
Node *left, *right;
T item;
inline bool operator < (const
Node &rhs) const {
return item < rhs.item; }
};
http://en.wikipedia.org/wiki/Binary_tree_sort
http://www.nist.gov/dads/HTML/treeSort.html
Randomised Binary Tree Sort
The problem with Tree Sort is
that the tree can be rather unbalanced, especially if the data was already
sorted. Such a case would be really easy for many algorithms, but alas makes
Tree Sort as bad (if not worse) than Insertion Sort. The fix is to use some kind
of balanced tree. There are a number of self-balancing tree
algorithms out there, or other means of ensuring a tree is reasonably well
balanced.
Although we know that tree sort performs poorly when there is a lot of order in
the data, it performs reasonably well when the data is quite randomised. So we
could either insert items in random order, or we could insert them into a
randomised binary search tree. The approach I've taken here is the former.
Randomised Binary Tree Sort is stable.
[hide source code]
template <class T>
void RandomisedBinaryTreeSort(T a[], int n) {
int idx = 0;
Node<T> *head = NULL, *const buf =
new Node<T>[n];
Shuffle(a, n);
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
TreeInsert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
http://www.cs.princeton.edu/~rs/strings/paper.pdf
Splay Tree Sort / AVL
Tree Sort / Red Black Tree Sort / AA (Anderson) Tree Sort / Scapegoat Tree Sort
Random insertion might be better
than ordinary insertion, but it's still possible to have it perform poorly,
however unlikely that may become. The principle for all balanced
binary tree sorts is the same as for a normal binary tree sort except that they
in turn employ other algorithms to keep the tree balanced, and some may require
additional memory to do so. Here are a bunch of four common self-balancing tree
sorting algorithms.
Tree Sorts are stable.
Splay Sort and Scapegoat Sort
are of particular
interest in that it doesn't require any extra variables on top of what is used
in an ordinary tree sort. The others store extra data in each node. Splay Sort adapts extremely well to data containing various patterns, but other tree sorts
give more uniform sort times. Actually when Splay-sorting a
doubly-linked list, the previous and next pointers of the doubly-linked list can be reused as left and right
nodes whilst in the tree, meaning that no extra memory is required for the sort.
[hide source code]
template <class T>
struct Node {
Node *left, *right;
T item;
inline bool operator < (const Node &rhs) const { return item < rhs.item; }
};
template <class T>
void SplaySort(T a[], int n) {
int idx = 0;
Node<T> *head = NULL, *const buf = new Node<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
SplayTree::Insert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
template <class T>
struct AVLNode {
AVLNode *left, *right;
int bal;
T item;
inline bool operator < (const AVLNode &rhs) const { return item < rhs.item; }
};
template <class T>
void AVLSort(T a[], int n) {
int idx = 0;
AVLNode<T> *head = NULL, *const buf = new AVLNode<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
AVLTree::Insert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
template <class T>
struct RBNode {
RBNode *left, *right;
bool red;
T item;
inline bool operator < (const RBNode &rhs) const { return item < rhs.item; }
};
template <class T>
void RedBlackSort(T a[], int n) {
int idx = 0;
RBNode<T> *head = NULL, *const buf = new RBNode<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
RBTree::Insert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
template <class T>
struct AANode {
AANode *left, *right;
int level;
T item;
inline bool operator < (const AANode &rhs) const { return item < rhs.item; }
};
template <class T>
void AASort(T a[], int n) {
int idx = 0;
AANode<T> *head = NULL, *const buf = new AANode<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
AATree::Insert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
template <class T>
void ScapegoatSort(T a[], int n) {
int idx = 0;
Node<T> *head = NULL, *const buf = new Node<T>[n];
for (int i = 0; i < n; ++i) {
buf[i].item = a[i];
ScapegoatTree::Insert(head, &buf[i],
i);
}
TreeDumpToArray(a, idx, head);
delete[] buf;
}
http://en.wikipedia.org/wiki/Binary_tree_sort
Heap Sort
A heap is a data structure
designed to allow constant time access to the maximum item (or minimum, but not
both), without
using any extra memory. The problem with tree sorts is that the trees themselves
take up a lot of memory. But hang on; we can store a tree implicitly in an array
without the need for pointers or rebalancing. Here's how we do that:
The first item is the root.
The next two items are the children of the root.
The next four items are the children of the root's two children.
etc.
Now the math to go between items
and their parent's and children:
First child = parent*2+1.
Second child = parent*2+2.
However we'll store items in the
order of a heap rather than a tree, because an ordered tree wouldn't really help
much. In a heap, the parent value is not between the values of its children
(unlike an ordered binary tree). Instead, the parent is greater than either of
its children (or small in a min-heap).
Heap Sorts are NOT stable.
[hide source code]
template <class T>
void HeapSortDownHeap(T a[], int l,
const int r) {
const T tempItem = a[l];
int child = (l<<1) + 1;
while (child < r) {
if ((child + 1 < r) && (a[child] < a[child + 1]))
++child;
if (!(tempItem < a[child]))
break;
a[l] = a[child];
l = child;
child = (child<<1) + 1;
}
a[l] = tempItem;
}
template <class T>
void HeapSort(T a[], int n) {
for (int i = n>>1; i >= 0; --i)
HeapSortDownHeap(a, i, n);
for (int j = n-1; j > 0; --j) {
Swap(a[0], a[j]);
HeapSortDownHeap(a, 0, j);
}
}
http://en.wikipedia.org/wiki/Heapsort
http://www.nist.gov/dads/HTML/heapSort.html
Fibonacci Heap Sort
Someone once had this crazy idea
for nodes to have three children instead of two. To go to a child you multiply
by 3 and add -1, 0 or 1. To go back to the parent, you add 1 then divide by 3.
You need to start at 1 of course since 3 x 0 = 0. This modification adds a lot
of complexity, but actually seems to give Fibonacci Heap Sort a speed advantage
over regular Heap Sort.
Heap Sorts are NOT stable.
[hide source code]
#define FibonacciPartialDownheap(b, i, j) do{ \
int k = j-1; \
if (b[k] < b[j]) k = j; \
if (b[k] < b[j+1]) k = j+1; \
b[i] = b[k]; \
i = k; \
j = i * 3; \
}while(false)
#define FibonacciPartialUpheap(b, i, j) do{ \
b[i] = b[j]; \
i = j; \
j = (j+1) / 3; \
}while(false)
template <class T>
while FibonacciHeapSort(T a[], int n) {
int i, j, l;
if (n > 4) {
T *b = a-1;
const int M = (n-1) / 3;
const int M1 = (M * 3) + 2;
if (M1 <= n) {
const int M2 = ((M1 < n) && (b[M1] < b[n])) ? n : M1;
if (b[1] < b[M2])
Swap(b[1], b[M2]);
}
for (l = M; l > 0; --l) {
const T X = b[l];
i = l;
j = i * 3;
do {
FibonacciPartialDownheap(b, i, j);
} while (j <= M1);
j = (i+1) / 3;
do {
if (!(b[j] < X)) break;
FibonacciPartialUpheap(b, i, j);
} while (j >= l);
b[i] = X;
}
for (l = M1; l <= n; ++l) {
i = l;
j = (i+1) / 3;
if (b[j] < b[l]) {
T X = b[l];
do {
FibonacciPartialUpheap(b, i, j);
} while (b[j] < X);
b[i] = X;
}
}
l = n;
while (l > 4) {
const T X = b[l];
b[l] = b[1];
--l;
i = 1;
j = 3;
do {
FibonacciPartialDownheap(b, i, j);
} while (j < l);
if (--j <= l) {
if ((j < l) && (b[j] < b[l])) j = l;
b[i] = b[j];
i = j;
}
j = (i+1) / 3;
while (b[j] < X) {
FibonacciPartialUpheap(b, i, j);
}
b[i] = X;
}
}
InsertionSort(a, (n < 4) ? n : (int)4);
}
#undef FibonacciPartialDownheap
#undef FibonacciPartialUpheap
http://en.wikipedia.org/wiki/Fibonacci_heap
Weak Heap Sort
Some speed gains can be made by
relaxing the heap condition such that only right nodes need to be less than
their parent. It does mean that we need to store an extra bit of info for each
node though. This also tends to beat ordinary Heap Sort, but at the cost of
using extra memory.
Heap Sorts are NOT stable.
[hide source code]
#define GETFLAG(r, x) ((r[(x)>>3] >> ((x)&7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x)>>3] ^= 1<<((x)&7))
template <class T>
while WeakHeapMerge(T a[],
unsigned char *r, int i, int j) {
if (a[i] < a[j]) {
TOGGLEFLAG(r, j);
Swap(a[i], a[j]);
}
}
template <class T>
while WeakHeapSort(T a[], int n) {
if (n > 1) {
int i, j, x, y, Gparent;
unsigned char *const r = new unsigned char[(n + 7) / 8)];
for (i=0; i<n/8; ++i) r[i] = 0;
for (i = n-1; i>0; --i) {
j = i;
while ((j & 1) == GETFLAG(r, j>>1)) j >>= 1;
Gparent = j>>1;
WeakHeapMerge(a, r, Gparent, i);
}
for (i = n-1; i>=2; --i) {
Swap(a[0], a[i]);
x = 1;
while ((y = 2*x + GETFLAG(r, x)) < i) x = y;
while (x > 0) {
WeakHeapMerge(a, r, 0, x);
x >>= 1;
}
}
Swap(a[0], a[1]);
delete[] r;
}
}
#undef GETFLAG
#undef TOGGLEFLAG
http://www.nist.gov/dads/HTML/weakheapsort.html
http://en.wikipedia.org/wiki/Heap_%28data_structure%29
http://books.google.co.nz/books?id=4SHZRSV5emYC&pg=PA39&lpg=PA39&dq=Weak+Heap+Sort+algorithm&source=bl&ots=5ZMm9KiqHB&sig=I9rFijVOxajxrdet-4jfdRuP3ns&hl=en&ei=u9GjS-fFOZiekQWMzcXJCA&sa=X&oi=book_result&ct=result&resnum=9&ved=0CC4Q6AEwCA#v=onepage&q=Weak%20Heap%20Sort%20algorithm&f=false
Smooth Sort
Dijkstra
made a modification to Heap Sort which allowed it to run in O(n) time
best case, for (almost) already sorted arrays. It's quite complex and slower
than other heap sorting algorithms, much of the time. It is in fact too complex
for me to describe here.
Heap Sorts (of which this is one) are NOT stable.
[hide source code]
#define SMOOTH_UP(b, c) do{ int oldb = b; b = b+c+1; c = oldb; }while(false)
#define SMOOTH_DOWN(b, c) do{ int oldb = b; b = c; c = oldb-c-1; }while(false)
template <class T>
while sift(T a[], int r1, int b1, int c1) {
while (b1 >= 3) {
int r2 = r1-b1+c1;
if (a[r2] < a[r1-1]) {
r2 = r1-1;
SMOOTH_DOWN(b1, c1);
}
if (!(a[r1] < a[r2])) b1 = 1;
else {
Swap(a[r1], a[r2]);
r1 = r2;
SMOOTH_DOWN(b1, c1);
}
}
}
template <class T>
while trinkle(T a[], int p1, int r1, int b1, int c1) {
while (p1 > 0) {
while ((p1 & 1) == 0) {
p1 >>= 1; SMOOTH_UP(b1, c1);
}
const int r3 = r1-b1;
if ((p1 == 1) || !(a[r1] < a[r3])) p1 = 0;
else {
--p1;
if (b1 == 1) {
Swap(a[r1], a[r3]);
r1 = r3;
} else if (b1 >= 3) {
int r2 = r1-b1+c1;
if (a[r2] < a[r1-1]) {
r2 = r1-1;
SMOOTH_DOWN(b1, c1);
p1 <<= 1;
}
if (!(a[r3] < a[r2])) {
Swap(a[r1], a[r3]);
r1 = r3;
} else {
Swap(a[r1], a[r2]);
r1 = r2;
SMOOTH_DOWN(b1, c1);
p1 = 0;
}
}
}
}
sift(a, r1, b1, c1);
}
template <class T>
while semitrinkle(T a[], int p, int r, int b, int c) {
const int r1 = r-c;
if (a[r] < a[r1]) {
Swap(a[r], a[r1]);
trinkle(a, p, r1, b, c);
}
}
template <class T>
while SmoothSort(T a[], int n) {
int q=1, r=0, p=1, b=1, c=1;
while (q < n) {
if ((p & 7) == 3) {
sift(a, r, b, c);
p = (p+1)>>2;
SMOOTH_UP(b, c); SMOOTH_UP(b, c);
} else if ((p & 3) == 1) {
if (q+c < n)
sift(a, r, b, c);
else
trinkle(a, p, r, b, c);
do {
SMOOTH_DOWN(b, c); p <<= 1;
} while (b != 1);
++p;
}
++q; ++r;
}
trinkle(a, p, r, b, c);
while (q > 1) {
--q;
if (b == 1) {
--r; --p;
while ((p & 1) == 0) {
p >>= 1;
SMOOTH_UP(b, c);
}
} else if (b >= 3) {
r += c-b;
--p;
if (p > 0) semitrinkle(a, p, r, b, c);
SMOOTH_DOWN(b, c); p = 2*p+1;
r += c;
semitrinkle(a, p, r, b, c);
SMOOTH_DOWN(b, c); p = 2*p+1;
}
}
}
#undef SMOOTH_UP
#undef SMOOTH_DOWN
http://en.wikipedia.org/wiki/Smoothsort
http://www.nist.gov/dads/HTML/smoothsort.html
Beap Sort
Beap is
short for "Bi-Parental Heap". In a beap, nodes have two children, and two
parents. Other than that it is quite similar to a heap, and the algorithm itself
is also very similar. Adjacent nodes share a child and a parent. This forms more
of a grid structure as opposed to a tree structure. It has no practical usage
due to being far less efficient than a binary heap. I've only really implemented
it out of curiosity. Operations tend to take O(sqrt(n)) time. The sort itself is
O(n1.5).
Beap Sort is NOT stable.
[hide source code]
template <class T>
while BeapSortDownHeap(T a[], int l, const int r, int level) {
const T tempItem = a[l];
int child = l + level;
while (child < r) {
if ((child + 1 < r) && (a[child] < a[child+1]))
++child;
if (!(tempItem < a[child]))
break;
a[l] = a[child];
l = child;
child += ++level;
}
a[l] = tempItem;
}
template <class T>
while BeapSort(T a[], int n) {
int sum = 0, level = 0;
while (sum < n)
sum += ++level;
sum -= level--;
for (int i=sum; i >= 0; --i) {
if (i < sum)
sum -= level--;
BeapSortDownHeap(a, i, n, level);
}
for (int j=n-1; j > 0; --j) {
Swap(a[0], a[j]);
BeapSortDownHeap(a, 0, j, 1);
}
}
http://en.wikipedia.org/wiki/Beap
Quick Sort
A quick way to sort items is to
pick one of them and divide the rest into two partitions, one with items less
than the item picked, and one with items greater than the item picked. Then you
do the same with each partition, and finally join the splitter and the sorted
partitions together. This is one of the many algorithms that uses what is known
as the divide and
conquer approach. The problem is divided into smaller sub-tasks, each of which
is divided again in the same manner until the problem becomes trivial (there is
only one item). The
easiest way to pick a splitter is to pick the first item, however that is a
horrible choice for when the list is already sorted or reverse sorted, as might
often be the case. A fairly good and quick method is to pick the middle item of
the array, which is what is done here.
Quick Sorts are NOT
stable.
[hide source code]
#define CUTOFF 16
template <class T>
while QuickSortAux(T a[], int l, int r) {
while (r - l > CUTOFF) {
int i = l-1, j = r;
const T tempItem = a[(l+r)>>1];
for (;;) {
do ++i; while (a[i] < tempItem);
do --j; while (tempItem < a[j]);
if (j <= i) break;
Swap(a[i], a[j]);
}
if (i-l <= r-i) {
QuickSortAux(a, l, i);
l = i;
} else {
QuickSortAux(a, i, r);
r = i;
}
}
}
template <class T>
while QuickSort(T a[], int n) {
QuickSortAux(a, 0, n);
#if CUTOFF > 1
InsertionSort(a, n);
#endif
}
http://en.wikipedia.org/wiki/Quicksort
http://www.nist.gov/dads/HTML/quicksort.html
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quicken.htm
http://www.sorting-algorithms.com/quick-sort
Randomised Quick Sort
Whilst the inner loop which
partitions the items in two runs very fast, unfortunately picking the first item
can have bad consequences. If the array is already sorted then one of the
partitions will contain all of the remaining items, meaning that each
partitioning step only reduces the workload by one, and performance becomes
terrible. Picking the middle item can be just as bad depending on the order of
the data. This can be improved in several ways. First off, you can try picking a
random splitter. That way you'd have to be very unlucky to pick a very bad
splitter many times over. Quick Sorts are NOT stable.
[hide source code]
#define CUTOFF 16
template <class T>
while RandomisedQuickSortAux(T a[], int l, int r, long &holdrand) {
while (r - l > CUTOFF) {
int randNo = (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
int i = l-1, j = r;
const T tempItem = a[l + randNo%(r-l)];
for (;;) {
do ++i; while (a[i] < tempItem);
do --j; while (tempItem < a[j]);
if (j <= i) break;
Swap(a[i], a[j]);
}
if (i-l <= r-i) {
RandomisedQuickSortAux(a, l, i, holdrand);
l = i;
} else {
RandomisedQuickSortAux(a, i, r, holdrand);
r = i;
}
}
}
template <class T>
while RandomisedQuickSort(T a[], int n) {
long defaultSeed = DEFAULT_SEED;
RandomisedQuickSortAux(a, 0, n, defaultSeed);
#if CUTOFF > 1
InsertionSort(a, n);
#endif
}
http://en.wikipedia.org/wiki/Quicksort#Randomized_quicksort_expected_complexity
Median-of-Three Quick Sort
Some people might not be too
keen on using a random splitter. You never know when it might perform badly one
time, yet quickly the next, sorting exactly the same sequence. Also with picking
the middle item, you can still get poor results every now and then. A better alternative is to
sample a few items and then pick the middle (median) value. This generally gives
very good results, and makes hitting the worst case extremely unlikely. Quick Sorts are NOT
stable.
[hide source code]
#define CUTOFF 16
template <class T>
while MedianOf3QuickSortAux(T a[], int l, int r) {
while (r - l > CUTOFF) {
int i = (l+r)>>1, j = r-1;
if (a[i] < a[l]) Swap(a[i], a[l]);
if (a[j] < a[l]) Swap(a[j], a[l]);
if (a[j] < a[i]) Swap(a[j], a[i]);
const T tempItem = a[i];
i = l;
for (;;) {
do ++i; while (a[i] < tempItem);
do --j; while (tempItem < a[j]);
if (j <= i) break;
Swap(a[i], a[j]);
}
if (i-l <= r-i) {
MedianOf3QuickSortAux(a, l, i);
l = i;
} else {
MedianOf3QuickSortAux(a, i, r);
r = i;
}
}
}
template <class T>
while MedianOf3QuickSort(T a[], int n) {
MedianOf3QuickSortAux(a, 0, n);
#if CUTOFF > 1
InsertionSort(a, n);
#endif
}
http://en.wikipedia.org/wiki/Quicksort
http://www.people.carleton.edu/~grossm/
Mean Sort
The key to good Quick Sort
performance really is in picking good splitter values. If we're prepared to
spend a little time to first look at all the values, then we can find a close to
ideal splitter. All we need is to find the minimum and maximum value and pick
halfway between, thus using an artificial cut-off value. This is what I have
called as Mean Sort. The drawback, besides having to iterate over the array
first, is that it assumes that the distribution of the items is roughly linear.
If it is not, then this wont work well.
Mean Sort is NOT stable.
[hide source code]
#define CUTOFF 16
template <class T>
while MeanSortAux(T a[], int l, int r, int lo, int hi) {
if (r - l > CUTOFF) {
while (hi - lo > 1) {
int i = l-1, j=r;
const int mid = (lo+hi)>>1;
for (;;) {
do ++i; while (i < j && a[i]-a[0] <= mid);
do --j; while (i < j && a[j]-a[0] > mid);
if (j <= i) break;
Swap(a[i], a[j]);
}
if (i-l <= r-i) {
MeanSortAux(a, l, i, lo, mid);
l = i; lo = mid;
} else {
MeanSortAux(a, i, r, mid, hi);
r = i; hi = mid;
}
}
}
}
template <class T>
while MeanSort(T a[], int n) {
if (n > 1) {
int min=0, max=0;
for (int i=1; i<n; ++i) {
if (a[i] < a[min]) min = i;
else if (a[max] < a[i]) max = i;
}
const int range = int(a[max] - a[min]) + 1;
if (range > 0) {
Swap(a[0], a[min]);
MeanSortAux(a, 1, n, 0, range);
}
}
#if CUTOFF > 1
InsertionSort(a, n);
#endif
}
Proportion Extend Sort
The main problem with Quick Sort
is when the chosen splitter is not close to placing half of the items on either
side. In this algorithm the median technique is again used, however the median
is chosen from more than 3 items. In order to pick the median of more than three
items, you have to select m items, and then sort those items and choose
the one in the middle. This brings us back to the original problem of sorting some
number of items, in order to do that. Since we're picking a median from a smaller number of items
than we actually want to sort overall, we do the logical thing of using a
recursive call. So in order to pick the median we first have to pick the median
of a smaller number of items, and to do that we may have to pick the median of
an even smaller number of items etc. Typically the number of items m for
picking the mean is n/16. This algorithm therefore has three logical
recursive calls (I always convert the last one to iterative, for performance). However since it is likely to pick a better median than the
median-of-three technique, it can actually perform faster.
Proportion-Extend Sort is NOT stable.
[hide source code]
template <class T>
int Partition(T a[], int mid, int u1, int u2) {
int i=u1, j=u2;
for (;;) {
while (i <= j && !(a[mid] < a[i])) ++i;
while (i < j && !(a[j] < a[mid])) --j;
if (i >= j) break;
Swap(a[i], a[j]);
++i; --j;
}
return i;
}
template <class T>
while ProportionExtendSortAux(T a[], int s1, int s2, int ua2) {
int i, prop, mid, se2, sl2, sr1, sr2, u1, u2, ul2, ur1;
const int p=16;
if (s2 < s1) s2 = s1;
while (s2 < ua2) {
prop = (1+p)*(s2-s1+1);
se2 = (p*prop > ua2-s1+1) ? ua2 : s1 + prop - 1;
mid = (s1+s2) >> 1;
u1 = s2+1;
u2 = se2;
sl2 = mid-1;
ur1 = Partition(a, mid, u1, u2);
sr1 = ur1-(s2-mid);
sr2 = ur1-1;
ul2 = sr1-2;
for (i=0; i<=s2-mid; ++i)
Swap(a[s2-i], a[sr2-i]);
if (ul2-sl2 < u2-sr2) {
ProportionExtendSortAux(a, s1, sl2, ul2);
ProportionExtendSortAux(a, sr1, sr2, u2);
} else {
ProportionExtendSortAux(a, sr1, sr2, u2);
ProportionExtendSortAux(a, s1, sl2, ul2);
}
s2 = se2;
}
}
template <class T>
while ProportionExtendSort(T a[], int n) {
ProportionExtendSortAux(a, 0, 0, n-1);
}
http://epubs.siam.org/SICOMP/volume-31/art_34290.html
Introspective Sort
Unfortunately it's still
possible to get crappy performance, just extremely unlikely. One can modify
Quick Sort to monitor the recursion depth and if it gets too deep, switch to
Heap Sort. Heap Sort is not quite as fast as Quick Sort most of the time, but is
much faster than Quick Sort when it comes to the worst case. This change
guarantees that it will never take far too long. Quick sort variants also often
only sort until the items are approximately in order, and at the end a final
pass with insertion sort is done. This ends up being faster than letting Quick
sort mess around with the fiddly little unsorted portions. So this algorithm is
a blend of 3 others!
Intro Sort is NOT stable because it uses Quick Sort and Heap Sort internally,
which are not stable, even though it also uses Insertion Sort which is stable.
[hide source code]
#define CUTOFF 16
template <class T>
while IntroSortAux(T a[], int l, int r, int depth_limit) {
while (r - l > CUTOFF) {
if (depth_limit == 0) {
HeapSort(&a[l], r - l);
return;
}
--depth_limit;
int i = (l+r)>>1, j = r-1;
if (a[i] < a[l]) Swap(a[i], a[l]);
if (a[j] < a[l]) Swap(a[j], a[l]);
if (a[j] < a[i]) Swap(a[j], a[i]);
const T tempItem = a[i];
i = l;
for (;;) {
do ++i; while (a[i] < tempItem);
do --j; while (tempItem < a[j]);
if (j <= i) break;
Swap(a[i], a[j]);
}
if (i-l <= r-i) {
IntroSortAux(a, l, i, depth_limit);
l = i;
} else {
IntroSortAux(a, i, r, depth_limit);
r = i;
}
}
}
template <class T>
while IntroSort(T a[], int n) {
IntroSortAux(a, 0, n, lg(n)*2);
#if CUTOFF > 1
InsertionSort(a, n);
#endif
}
http://www.cs.rpi.edu/~musser/gp/introsort.ps
Shear Sort
This algorithm treats the input array as it it were
a two-dimensional i * j (grid) of items rather than a one dimensional
array of n items. This works alright when n can be factorised into
approximately equal factors. The nature of the algorithm also means that it can
run well on multiple process or cores at once. However it works terribly when n
is prime.
Shear Sort is NOT stable.
[hide source code]
template <class T>
while ShearSortAux(T a[], const int Lo, const int Hi, const int Nx, bool ascend) {
for (int j = Lo; j+Nx<Hi; j+=2*Nx)
if (ascend == a[j+Nx] < a[j])
Swap(a[j], a[j+Nx]);
}
template <class T>
while ShearSort(T a[], int n) {
int pow=1, Rows=1, Log, i, j, k;
for (i = 1; i*i <= n; ++i)
if (n % i == 0) Rows = i;
const int Cols = n / Rows;
for (Log = 0; pow <= Rows; ++Log) pow<<=1;
for (k = 0; k < Log; ++k) {
for (j = 0; j<(Cols+1)>>1; ++j) {
for (i = 0; i<Rows; ++i)
ShearSortAux(a, i*Cols, (i+1)*Cols, 1, (i&1)==0);
for (i = 0; i<Rows; ++i)
ShearSortAux(a, i*Cols+1, (i+1)*Cols, 1, (i&1)==0);
}
for (j = 0; j<(Rows+1)>>1; ++j) {
for (i = 0; i<Cols; ++i)
ShearSortAux(a, i, n+i, Cols, true);
for (i = 0; i<Cols; ++i)
ShearSortAux(a, i+Cols, n+i, Cols, true);
}
}
for (j = 0; j<(Cols+1)>>1; ++j) {
for (i = 0; i<Rows; ++i)
ShearSortAux(a, i*Cols, (i+1)*Cols, 1, true);
for (i = 0; i<Rows; ++i)
ShearSortAux(a, i*Cols+1, (i+1)*Cols, 1, true);
}
}
http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html
Optimistic Sort
This algorithm is a simple fixed network of n*logn
compare-exchange operations, which when repeated at most logn times produces a
sorted array. I dreamt this up on 13th April 2007. It can't
realistically compete with Quick Sorts average case, but is on par with Bitonic
Sort algorithms in terms of Big-Oh notation. However this algorithm can finish in fewer than logn passes, in
which case it beats Bitonic Sort. The lower bound is O(nlogn) and the upper
bound is O(nlog2n).
Each pass is very simple. Perform a compare and swap of items from the first
half with the second half. Do this by starting from each end and proceeding
towards the middle. Compare and swap the items from each location as you go,
swapping if out or order. Repeat on each half, until the there is only 1 item.
This often does not in itself fully sort the items, and usually more passes are
needed.
It does guarantee that the smallest and largest items find their way to
the correct positions in one pass, however. It also unexpectedly seems to be the
case that
after each compete pass, there are no strictly decreasing runs of length three or
greater.
Care must be taken to deal with the middle item wherever the portion to
sort is not an even size. The middle item must be compared to another item so
that it too is allowed to move.
Although this algorithm is so far not quite competitive with techniques such as
quicksort, I encourage others to explore the idea further as it may have some
usefulness when combined with merging, or perhaps a final insertion sort pass.
If this algorithm can be made more adaptive it may indeed one day become
competitive with quicksort. I certainly believe there is more potential for
speed gains here.
This algorithm is NOT stable.
As far as I am aware, this
algorithm is my own creation. Therefore I do not yet have any links to other
sites with the algorithm.
[hide source code]
template <class T>
void OptimisticSortAux(T a[], int l, int r, bool &swapped) {
while (r - l > 1) {
int i = l, j = r;
do {
--j;
if (a[j] < a[i]) {
Swap(a[i], a[j]);
swapped = true;
}
++i;
} while (i < j);
if (i > j) {
if (a[i] < a[j]) {
Swap(a[i], a[j]);
swapped = true;
}
}
OptimisticSortAux(a, l, i, swapped);
l = i;
}
}
template <class T>
void OptimisticSort(T a[], int n) {
bool swapped;
do {
swapped = false;
OptimisticSortAux(a, 0, n, swapped);
} while (swapped);
}
Squeeze Sort
This algorithm is in some ways similar to Strand Sort, except
that the runs are not obtained from consecutive items. The runs are instead
obtained by scanning through the array looking for items that can extend the run
in either direction. This starts with the first item in the array each time, and
builds the longest run it can from there, by examining every item in order. In
the process, the unsorted items are moved over to fill up the gap where each
item taken for the run was. The run, which is stored in a secondary buffer, is
then merged with the sorted portion after each pass, and put back into the
original array where space was made for it when items were moved over earlier.
This algorithm is NOT stable.
[hide source code]
template <class T>
void SqueezeMerge(T a[], T sorted[], int &sorted_so_far, int unsorted_so_far, int start, int end, int n) {
int h = 0, j = start, i = unsorted_so_far;
int mid = sorted_so_far;
while (h < mid) {
if (!(sorted[j] < sorted[h]))
a[i++] = sorted[h++];
else {
a[i++] = sorted[j++];
if (j == n) j = mid;
if (j == end) break;
}
}
if (h >= mid) {
for (int k=j;;) {
a[i++] = sorted[k++];
if (k == n) k = mid;
if (k == end) break;
}
} else {
for (int k=h; k<=mid-1;) {
a[i++] = sorted[k++];
}
}
sorted_so_far = 0;
for (int k = unsorted_so_far; k<n; ++k)
sorted[sorted_so_far++] = a[k];
}
template <class T, class int>
void SqueezeSortAux(T a[], T sorted[], int sorted_so_far, int n, int realn) {
int unsorted_so_far;
do {
int start = realn, end = sorted_so_far;
T max = a[0], min = a[0];
unsorted_so_far = 0;
for (int i=0; i < n; ++i) {
if (!(min < a[i]))
sorted[--start] = min = a[i];
else if (max < a[i])
sorted[end++] = max = a[i];
else
a[unsorted_so_far++] = a[i];
}
SqueezeMerge(a, sorted, sorted_so_far, unsorted_so_far, start, end, realn);
n = unsorted_so_far;
} while (unsorted_so_far > 0);
}
template <class T, class int>
void SqueezeSort(T a[], int n) {
if (n > 1) {
T *sorted = new T[n];
SqueezeSortAux(a, sorted, 0, n, n);
delete[] sorted;
}
}
http://www.codeproject.com/useritems/SQ_Srt_New.asp
http://www.articleboy.com/Article/Squeeze-Sort--A-New-Sorting-Technique/1188
Flash Sort
All of the algorithms so far are
comparison-based, and as such cannot do better than O (nlogn) running time in the worse case. To
do any better we need to compare keys in a more useful manner than simply
determining which of two is bigger. We can take advantage of extra information,
such as the difference between the keys to get a much better idea of how far
apart they should be. Once we find the lowest and the highest items, we can work
out approximately where the other items should go, by the relative distance of
their keys. This is the principle behind Flash Sort. As with Mean Sort, this
algorithm works best when the distribution of values is roughly linear.
Flash Sort allows a great degree of control with regards to the
memory-usage/speed tradeoff. In the following implementation I have pinned the
minimum and maximum memory usage as well.
Flash Sort is NOT stable.
[hide source code]
template <class T>
while FlashSort(T a[], int n) {
const int THRESHOLD = 64;
const int MIN_CLASS_SIZE = 32;
const int MAX_CLASS_SIZE = 16384;
const int AVERAGE_BUCKET_SIZE = 10;
int nmin, nmax, i, j, k, nmove, nx;
if (n <= 1) return;
nmin = nmax = 0;
for (i=1; i < n; ++i) {
if (a[i] < a[nmin])
nmin = i;
else if (a[nmax] < a[i])
nmax = i;
}
if (!(a[nmin] < a[nmax])) return;
int m = n/AVERAGE_BUCKET_SIZE;
if (m < MIN_CLASS_SIZE) m = MIN_CLASS_SIZE;
else if (m > MAX_CLASS_SIZE) m = MAX_CLASS_SIZE;
int *l = new int[m];
const double c1 = (double)(m-1.0)/(a[nmax]-a[nmin]);
const T c2 = a[nmin];
l[0] = -1;
for (k=1; k < m; ++k) l[k] = 0;
for (i=0; i < n; ++i) {
k = static_cast<int>(floor(c1*(a[i]-c2)));
++l[k];
}
for (k=1; k < m; ++k) l[k] += l[k-1];
Swap(a[0], a[nmax]);
nmove = j = 0;
k = m-1;
while (nmove < n) {
while (j > l[k]) {
++j;
k = static_cast<int>(floor(c1*(a[j]-c2)));
}
T flash = a[j];
while (j <= l[k]) {
k = static_cast<int>(floor(c1*(flash-c2)));
const int lk = l[k];
const T hold = a[ lk ];
a[ lk ] = flash;
--l[k];
flash = hold;
++nmove;
}
}
for (k = 0; k < (m-1); ++k) {
if ( (nx = l[k+1]-l[k]) > THRESHOLD )
FlashSort(&a[l[k]+1], nx);
else {
for (i=l[k+1]-1; i > l[k]; --i) {
if (a[i+1] < a[i]) {
const T hold = a[i];
j = i;
do {
a[j] = a[j+1];
++j;
} while (a[j+1] < hold);
a[j] = hold;
}
}
}
}
delete[] l;
}
http://www.neubert.net/FSOIntro.html
http://www.nist.gov/dads/HTML/flashsort.html
Radix Sort
One can go even further towards
extracting more information from the keys. Going beyond subtracting keys as in
Flash Sort, you can actually sort by the exact bytes of the key, one at a time,
or by some other number of bits of the key at once.
This technique is not very general as it can't work for every type of data, and
typically requires modifications for each data type you wish to use it on. As it
sorts according to the least-significant bits first, the internal algorithm used
"Counting Sort" is required to be a stable algorithm. Counting Sort is so
data-specific that I don't bother with it at all.
The great news is that unlike Flash Sort, this is not affected by non-linear
distributions.
Radix Sort is stable.
[hide source code]
template <class T>
const int NUM_BITS_AT_ONCE = 8;
const int MAX_BIN = (1<<NUM_BITS_AT_ONCE);
const bool SIGNEDVALUES = false;
template <class T>
while RadixSort(T a[], int n) {
if (n > 1) {
int histogram[MAX_BIN], i, val = 0;
int
shift, mask;
int *idx1, *idx2, *idx3, *const l = new int[2 * n];
idx1 = &l[0]; idx2 = &l[n];
for (i=0; i<n; ++i)
idx1[i] = i;
for
(shift=0; shift<32; shift+=NUM_BITS_AT_ONCE) {
for (i=MAX_BIN; i>0;)
histogram[--i] = 0;
for (i=n; i>0;) {
val = (a[--i]>>shift) & (MAX_BIN-1);
++histogram[val];
}
if (histogram[val] == n) continue;
if (SIGNEDVALUES &&
shift+NUM_BITS_AT_ONCE>=32) {
mask = (MAX_BIN>>1);
for (i=1; i<MAX_BIN; ++i)
histogram[i^mask] += histogram[(i-1)^mask];
} else {
for (i=1; i<MAX_BIN; ++i)
histogram[i] += histogram[i-1];
}
for (i=n; i>0;) {
const int thisIndex = idx1[--i];
val = (a[thisIndex]>>shift) & (MAX_BIN-1);
idx2[--histogram[val]] = thisIndex;
}
idx3 = idx1; idx1 = idx2; idx2 = idx3;
}
ReorderAccordingTo(a, n, idx1);
delete[] l;
}
}
while ReorderAccordingTo(T a[], int n, int indexes[]) {
for (int i=0; i<n; ++i) {
if (indexes[i] != i) {
const T tempItem = a[i];
int l = i, j;
while ((j = indexes[l]) != i) {
a[l] = a[j];
indexes[l] = l;
l = j;
}
a[l] = tempItem;
indexes[l] = l;
}
}
}
http://en.wikipedia.org/wiki/Radix_sort
http://www.nist.gov/dads/HTML/radixsort.html
Gnome Sort
Well, now that we've reached the
fastest sorting algorithms, let take a look at some of the slowest.
Gnome Sort is extremely simple.
Compare an item with its neighbour, if it is out of order, swap them and move
back (not past the start), otherwise move forward. Stop when you reach the end.
This actually works basically like Insertion Sort, but less efficiently.
This
algorithm is O(n2), but is stable.
[hide source code]
template
<class T >
void
GnomeSort(T a[], int n) {
int i = 0;
while (i < n) {
if (i != 0 && a[i] < a[i-1]) {
Swap(a[i], a[i-1]);
--i;
} else {
++i;
}
}
}
http://en.wikipedia.org/wiki/Gnome_sort
http://www.nist.gov/dads/HTML/gnomeSort.html
Stupid Sort
Can we do worse than Gnome Sort?
Sure, go back to the start after finding items out of order and swapping them.
This algorithm is so bad that it is O(n3), but it is stable.
[hide source code]
template
<class T>
void
StupidSort(T a[], int n) {
int i = 0;
while (i < n-1) {
++i;
if (a[i] < a[i-1]) {
Swap(a[i-1], a[i]);
i = 0;
}
}
}
Stooge Sort
Here's a bazaar idea. Can we
sort with no loop whatsoever? Sure by using the powers of recursion we can
develop Stooge Sort. This algorithm is so bad that it is O(n2.7)
Stooge Sort is NOT stable.
[hide source code]
template
<class T>
void
StoogeSortAux(T a[],
int
l,
int
r) {
if (a[r-1] < a[l]) Swap(a[l], a[r-1]);
if (r - l > 2) {
const
int
third = (r-l)/3;
StoogeSortAux(a, l, r-third);
StoogeSortAux(a, l+third, r);
StoogeSortAux(a, l, r-third);
}
}
template<class T>
void
StoogeSort(T a[], int n) {
if (n > 1) StoogeSortAux(a, 0, n);
}
http://en.wikipedia.org/wiki/Stooge_sort
http://www.nist.gov/dads/HTML/stoogesort.html
Fib Sort
Just as Stooge Sort has no loop,
neither does Fib Sort. The running time of this algorithm with n items, relates
to the nth Fibonacci number, hence the name.
Fib Sort is NOT stable.
[hide source code]
template
<class T>
void FibSort(T a[],
int n) {
if (n <= 1)
return;
if (a[n-1] < a[0])
Swap(a[0], a[n-1]);
FibSort(&a[1], n-2);
if (a[1] < a[0])
Swap(a[0], a[1]);
FibSort(&a[1], n-1);
}
http://www.ics.uci.edu/~eppstein/161/exams/mt1.pdf
Slow Sort
Okay, now things just get really
insane. This algorithm containing 3 recursive calls is actually designed to be
as innocently looking and yet as inefficient as possible. Hey, if you can’t
design the fastest algorithm, why not go for the slowest! This algorithm manages
to be about as bad as O(n(logn)/2) even though on the surface it
appears to contain code similar to Stooge Sort. The authors (Andrei
Broder & Jorge Stolfi)
don't mention this at all, but this sort is NOT stable.
[hide source code]
template
<class T>
void
SlowSort(T a[],
int n) {
SlowSortAux(a, 0, n-1, n-1);
}
template
<class T>
void
SlowSortAux(T a[],
int i,
int
j,
int
n) {
if (i < j) {
int m = (i + j) >> 1;
SlowSortAux(a, i, m, n);
SlowSortAux(a, m+1, n, n);
if (a[j] < a[m])
Swap(a[m], a[j]);
SlowSortAux(a, i, j-1, n);
}
}
http://www.cs.uiuc.edu/class/fa05/cs473ug/resources/pessimal-algorithms.pdf
http://de.wikipedia.org/wiki/Slowsort
Perm Sort
Hmm, can we get any slower than
Slow Sort? You bet! We can try every permutation of the items until we find a
match. The number of permutations gets ridiculously high very quickly, and this
algorithm swaps items like crazy, so you'll probably literally grow old waiting
for it, but what the heck. What's more it uses a lot of stack space
This worst-case algorithm is O(n*n!) and it is NOT
stable either.
[hide source code]
template <class T>
bool PermSortAux(T a[], int n, int i) {
if (Sorted(a, n)) return true;
int j = i+1;
if (j < n) {
const T x1 = a[i];
do {
a[i] = a[j];
a[j] = x1;
if (PermSortAux(a, n, i+1)) return true;
a[j] = a[i];
a[i] = x1;
} while (++j < n);
if (PermSortAux(a, n, i+1)) return true;
}
return false;
}
template <class T>
while PermSort(T a[], int n) {
PermSortAux(a, n, 0);
}
http://cg.scs.carleton.ca/~morin/misc/sortalg/
Bozo Sort
In Bozo Sort, we just swap items
randomly until the whole lot just happen to be in sorted order. As you can
imagine, the chance of it even succeeding aren't that great, and if it does, it
most likely isn't going to be quick.
Bozo Sort is NOT stable.
[hide source code]
#define DEFAULT_SEED 0x9e3779b9
template <class T>
while BozoSort(T a[], int n) {
BozoSortAux(a, n, DEFAULT_SEED);
}
template <class T>
while BozoSortAux(T a[], int n, long seed) {
long holdrand = seed;
while (!Sorted(a, n)) {
unsigned int randNo1 = (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
unsigned int randNo2 = (((holdrand = holdrand * 214013L + 2531011L) >> 16) & 0x7fff);
const int pos1 = randNo1 % n;
const int pos2 = randNo2 % n;
Swap(a[pos1], a[pos2]);
}
}
template <class T>
bool Sorted(const T a[], int n) {
for (int i = n-1; i > 0; --i)
if (a[i] < a[i-1])
return false;
return true;
}
http://en.wikipedia.org/wiki/Bozo_sort
On To List Sorting >
Download Mega Sorting
Demo program (104933 bytes zip file)