I’ve recently coded a q-sort template function implementation. It’s part of another project, but it’s sort of stand-alone.
Author: Aaron M. Schinder
Date: 4 May 2013
Purpose: ams_qsort is an implementation of quicksort, the popular O(n*log(n)) sorting algorithm. There are millions of q-sort implementations out there, but this one is mine. This was programmed partially for the ability to sort multiple lists, but mostly for the exercise in converting a recursive program to a procedural loop.
It has some desirable features over most implementations of qsort:
1. It doesn’t use recursion of the function calls. Instead, it implements recursive behavior through the use of a tree data-structure. This means it won’t blow your call-stack when sorting large lists (which is the point of having an O(n*log(n)) sorting algorithm in the first place!).
2. What the actual sorting function returns is not a single sorted list, but a permutation map. The permutation map can be applied not just to this list, but to other related lists as well to sort each according to the first. First you acquire the permutation map that will sort the target list, then you apply it to lists.
Main functions of interest:
bool quicksort(std::vector<T> *V, std::vector<long> *map, bool (*comparator)(T, T));
bool rearrange(std::vector<T> *V, std::vector<long> *map);
void invertmap(std::vector<long > *map, std::vector<long > *inv);
void mapcompose(std::vector<long > *map_in_main, std::vector<long > *map_in_sub, long indstart);
Typical use:
quicksort(&myvector,&map,&comparatorfn);
rearrange(&myvector,&map); //rearranges myvector (sorts it)
rearrange(&myothervector, &map); //rearranges some other vector (sorts it according to myvector)
invertmap(&map,&othermap); //creates a map which, when composed with map, de-permutes it.
rearrange(&myothervector,&othermap); //unsorts the myothervector
bool comparator(T A,T B)
comparator is a pointer to a bool function that returns true if A>B, according to whatever evaluation of A and B you want.
Comments (0)