Loading...
Searching...
No Matches
Sort.cpp
/*
* Copyright (C) 2010 Regents of the University of Michigan
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#include "Sort.h"
#include "Error.h"
#include <stddef.h>
#include <string.h>
#define Item(b) (base_char+(b)*width)
#define IsBefore(x,y) ((cmp(Item(x),Item(y)))<0)
#define Exchange(x,y) {\
memcpy(tmp,Item(x),width);\
memcpy(Item(x),Item(y),width);\
memcpy(Item(y),tmp,width);\
}
#define TRUE 1
void QuickSort(void *base, size_t nelem, size_t width,
int (*cmp)(const void *, const void *))
{
struct __QuickSortStack
{
size_t left, right;
};
if (nelem <= 1)
return;
// Create a pseudo-stack to avoid recursion
char * base_char = (char *) base;
const size_t stackSize = 128;
__QuickSortStack * stack = new __QuickSortStack[stackSize];
char * tmp = new char [width];
if ((stack == NULL) || (tmp == NULL))
error("Out of memory in QuickSort routine");
size_t stackIdx = 0;
// Size of minimum partition to median of three
const size_t Threshold = 7;
// current partitions
size_t lsize, rsize;
size_t l, mid, r;
size_t scanl, scanr, pivot;
l = 0;
r = nelem - 1;
while (TRUE)
{
while (r > l)
{
if (r - l > Threshold)
// QuickSort : median of three partitioning
{
mid = (r + l) / 2;
// sort l, mid, and r
if (IsBefore(mid, l))
Exchange(mid, l);
if (IsBefore(r, l))
Exchange(r, l);
if (IsBefore(r, mid))
Exchange(r, mid);
// set up for partitioning...
pivot = r - 1;
Exchange(mid, pivot);
scanl = l + 1;
scanr = r - 2;
}
else
{
// set up random partition -- faster
pivot = r;
scanl = l;
scanr = r - 1;
}
while (TRUE)
{
// scan from left for element >= pivot
while ((scanl < r) && IsBefore(scanl, pivot))
++scanl;
while ((scanr > l) && IsBefore(pivot, scanr))
--scanr;
// if scans have met, we are done
if (scanl >= scanr)
break;
Exchange(scanl, scanr);
if (scanl < r)
++scanl;
if (scanr > l)
--scanr;
}
// Exchange final element
Exchange(pivot, scanl);
// Place largest partition on stack
lsize = scanl - l;
rsize = r - scanl;
if (lsize > rsize)
{
// if size is one we are done
++ stackIdx;
if (stackIdx == stackSize)
error("Out of Stack in QuickSort routine");
stack[stackIdx].left = l;
stack[stackIdx].right = scanl - 1;
if (rsize != 0)
l = scanl + 1;
else
break;
}
else
{
// if size is one we are done
++ stackIdx;
if (stackIdx == stackSize)
error("Out of Stack in QuickSort routine");
stack[stackIdx].left = scanl + 1;
stack[stackIdx].right = r;
if (lsize != 0)
r = scanl - 1;
else
break;
}
}
// iterate with values from stack
if (stackIdx)
{
l = stack[stackIdx].left;
r = stack[stackIdx].right;
--stackIdx;
}
else
break;
}
delete [] stack;
delete [] tmp;
}
#define Item2(b) (base_char2+(b)*width)
#define Exchange2(x,y) {\
memcpy(tmp,Item(x),width);\
memcpy(Item(x),Item(y),width);\
memcpy(Item(y),tmp,width);\
memcpy(tmp,Item2(x),width);\
memcpy(Item2(x),Item2(y),width);\
memcpy(Item2(y),tmp,width);\
}
void QuickSort2(void *base, void *base2, size_t nelem, size_t width,
int (*cmp)(const void *, const void *))
{
struct __QuickSortStack
{
size_t left, right;
};
if (nelem <= 1)
return;
// Create a pseudo-stack to avoid recursion
char * base_char = (char *) base;
char * base_char2 = (char *) base2;
const size_t stackSize = 128;
__QuickSortStack * stack = new __QuickSortStack[stackSize];
char * tmp = new char [width];
if ((stack == NULL) || (tmp == NULL))
error("Out of memory in QuickSort routine");
size_t stackIdx = 0;
// Size of minimum partition to median of three
const size_t Threshold = 7;
// current partitions
size_t lsize, rsize;
size_t l, mid, r;
size_t scanl, scanr, pivot;
l = 0;
r = nelem - 1;
while (TRUE)
{
while (r > l)
{
if (r - l > Threshold)
// QuickSort : median of three partitioning
{
mid = (r + l) / 2;
// sort l, mid, and r
if (IsBefore(mid, l))
Exchange2(mid, l);
if (IsBefore(r, l))
Exchange2(r, l);
if (IsBefore(r, mid))
Exchange2(r, mid);
// set up for partitioning...
pivot = r - 1;
Exchange2(mid, pivot);
scanl = l + 1;
scanr = r - 2;
}
else
{
// set up random partition -- faster
pivot = r;
scanl = l;
scanr = r - 1;
}
while (TRUE)
{
// scan from left for element >= pivot
while ((scanl < r) && IsBefore(scanl, pivot))
++scanl;
while ((scanr > l) && IsBefore(pivot, scanr))
--scanr;
// if scans have met, we are done
if (scanl >= scanr)
break;
Exchange2(scanl, scanr);
if (scanl < r)
++scanl;
if (scanr > l)
--scanr;
}
// Exchange final element
Exchange2(pivot, scanl);
// Place largest partition on stack
lsize = scanl - l;
rsize = r - scanl;
if (lsize > rsize)
{
// if size is one we are done
++ stackIdx;
if (stackIdx == stackSize)
error("Out of Stack in QuickSort routine");
stack[stackIdx].left = l;
stack[stackIdx].right = scanl - 1;
if (rsize != 0)
l = scanl + 1;
else
break;
}
else
{
// if size is one we are done
++ stackIdx;
if (stackIdx == stackSize)
error("Out of Stack in QuickSort routine");
stack[stackIdx].left = scanl + 1;
stack[stackIdx].right = r;
if (lsize != 0)
r = scanl - 1;
else
break;
}
}
// iterate with values from stack
if (stackIdx)
{
l = stack[stackIdx].left;
r = stack[stackIdx].right;
--stackIdx;
}
else
break;
}
delete [] stack;
delete [] tmp;
}
void * BinarySearch(const void *key, const void *base,
size_t nelem, size_t width,
int (*cmp)(const void *, const void *))
{
if (nelem == 0)
return NULL;
char * base_char = (char *) base;
int left = 0;
int right = nelem - 1;
while (right >= left)
{
int probe = (left + right) / 2;
int test = cmp(key, Item(probe));
if (test == 0)
return (void *) Item(probe);
if (test < 0)
right = probe - 1;
else
left = probe + 1;
}
return NULL;
}