141 lines
3.8 KiB
C++
141 lines
3.8 KiB
C++
#ifndef _COMMON_QUICKSORT_TPP_
|
|
#define _COMMON_QUICKSORT_TPP_
|
|
|
|
template <class T>
|
|
QuickSort<T>::QuickSort(void)
|
|
: mlpItemList(0), mlpBlockItems(0)
|
|
{
|
|
}
|
|
|
|
template <class T>
|
|
QuickSort<T>::~QuickSort()
|
|
{
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::sortItems(Array<T> &arrayItems,SortOptions::SortOrder sortOrder)
|
|
{
|
|
if(!arrayItems.size())return;
|
|
mlpItemList=&arrayItems[0];
|
|
if(SortOptions::Ascending==sortOrder)quickSort(0,arrayItems.size()-1);
|
|
else quickSortDescending(0,arrayItems.size()-1);
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::sortItems(Block<T> &someBlock,SortOptions::SortOrder sortOrder)
|
|
{
|
|
if(!someBlock.size())return;
|
|
mlpBlockItems=&someBlock;
|
|
if(SortOptions::Ascending==sortOrder)sortBlockAscending(0,someBlock.size()-1L);
|
|
else sortBlockDescending(0,someBlock.size()-1L);
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::quickSort(long left,long right)
|
|
{
|
|
long tempLeft(left);
|
|
long tempRight(right);
|
|
T tempItem;
|
|
T swapItem;
|
|
|
|
tempItem=*((T FAR*)(mlpItemList+((left+right)/2L)));
|
|
do{
|
|
while(*((T FAR*)(mlpItemList+tempLeft))<tempItem&&tempLeft<=right)tempLeft++;
|
|
while(tempItem<*((T FAR*)(mlpItemList+tempRight))&&tempRight>=left)tempRight--;
|
|
if(tempLeft>right)tempLeft--;
|
|
if(tempRight<left)tempRight++;
|
|
if(tempLeft<=tempRight)
|
|
{
|
|
swapItem=*((T FAR*)(mlpItemList+tempLeft));
|
|
*((T FAR*)(mlpItemList+tempLeft))=*((T FAR*)(mlpItemList+tempRight));
|
|
*((T FAR*)(mlpItemList+tempRight))=swapItem;
|
|
tempLeft++;
|
|
tempRight--;
|
|
}
|
|
}while(tempLeft<=tempRight);
|
|
if(left<tempRight)quickSort(left,tempRight);
|
|
if(tempLeft<right)quickSort(tempLeft,right);
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::quickSortDescending(long left,long right)
|
|
{
|
|
long tempLeft(left);
|
|
long tempRight(right);
|
|
T tempItem;
|
|
T swapItem;
|
|
|
|
tempItem=*((T FAR*)(mlpItemList+((left+right)/2L)));
|
|
do{
|
|
while(*((T FAR*)(mlpItemList+tempLeft))>tempItem&&tempLeft<=right)tempLeft++;
|
|
while(tempItem>*((T FAR*)(mlpItemList+tempRight))&&tempRight>=left)tempRight--;
|
|
if(tempLeft>right)tempLeft--;
|
|
if(tempRight<left)tempRight++;
|
|
if(tempLeft<=tempRight)
|
|
{
|
|
swapItem=*((T FAR*)(mlpItemList+tempLeft));
|
|
*((T FAR*)(mlpItemList+tempLeft))=*((T FAR*)(mlpItemList+tempRight));
|
|
*((T FAR*)(mlpItemList+tempRight))=swapItem;
|
|
tempLeft++;
|
|
tempRight--;
|
|
}
|
|
}while(tempLeft<=tempRight);
|
|
if(left<tempRight)quickSortDescending(left,tempRight);
|
|
if(tempLeft<right)quickSortDescending(tempLeft,right);
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::sortBlockAscending(long left,long right)
|
|
{
|
|
long tempLeft(left);
|
|
long tempRight(right);
|
|
T tempItem;
|
|
T swapItem;
|
|
|
|
tempItem=(*mlpBlockItems)[(left+right)/2L];
|
|
do{
|
|
while((*mlpBlockItems)[tempLeft]<tempItem&&tempLeft<=right)tempLeft++;
|
|
while(tempItem<(*mlpBlockItems)[tempRight]&&tempRight>=left)tempRight--;
|
|
if(tempLeft>right)tempLeft--;
|
|
if(tempRight<left)tempRight++;
|
|
if(tempLeft<=tempRight)
|
|
{
|
|
swapItem=(*mlpBlockItems)[tempLeft];
|
|
(*mlpBlockItems)[tempLeft]=(*mlpBlockItems)[tempRight];
|
|
(*mlpBlockItems)[tempRight]=swapItem;
|
|
tempLeft++;
|
|
tempRight--;
|
|
}
|
|
}while(tempLeft<=tempRight);
|
|
if(left<tempRight)sortBlockAscending(left,tempRight);
|
|
if(tempLeft<right)sortBlockAscending(tempLeft,right);
|
|
}
|
|
|
|
template <class T>
|
|
void QuickSort<T>::sortBlockDescending(long left,long right)
|
|
{
|
|
long tempLeft(left);
|
|
long tempRight(right);
|
|
T tempItem;
|
|
T swapItem;
|
|
|
|
tempItem=(*mlpBlockItems)[(left+right)/2L];
|
|
do{
|
|
while((*mlpBlockItems)[tempLeft]>tempItem&&tempLeft<=right)tempLeft++;
|
|
while(tempItem>(*mlpBlockItems)[tempRight]&&tempRight>=left)tempRight--;
|
|
if(tempLeft>right)tempLeft--;
|
|
if(tempRight<left)tempRight++;
|
|
if(tempLeft<=tempRight)
|
|
{
|
|
swapItem=(*mlpBlockItems)[tempLeft];
|
|
(*mlpBlockItems)[tempLeft]=(*mlpBlockItems)[tempRight];
|
|
(*mlpBlockItems)[tempRight]=swapItem;
|
|
tempLeft++;
|
|
tempRight--;
|
|
}
|
|
}while(tempLeft<=tempRight);
|
|
if(left<tempRight)sortBlockDescending(left,tempRight);
|
|
if(tempLeft<right)sortBlockDescending(tempLeft,right);
|
|
}
|
|
#endif
|