If we make a little program to compare your sort to some others, we can see if there is a more efficient algorithm.
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <mmsystem.h>
#include <vector>
#include <list>
#include <algorithm>
using std::vector;
using std::list;
static DWORD gs_nStartTime = 0;
#pragma comment(lib, "winmm.lib") //for mmsystem.h
void StartTimer() {
gs_nStartTime = timeGetTime();
}
void StopTimer(LPSTR szName) {
printf("%s sort took %ums\n", szName, timeGetTime() - gs_nStartTime);
}
struct error_node {
float err;
int ind;
};
typedef list<error_node> edge_head_t;
typedef vector<edge_head_t::iterator> edge_map_t;
typedef vector<error_node> sort_edge_t;
bool StdCompare(error_node first, error_node second) {
if (first.err >= second.err) {
return false;
}
return true;
}
int QSortCompare(const void *pElem1, const void *pElem2) {
if (((error_node *)pElem1)->err < ((error_node *)pElem2)->err) {
return -1;
} else if (((error_node *)pElem1)->err > ((error_node *)pElem2)->err) {
return 1;
}
return 0;
}
void YourSort(float *pEdgesArray, unsigned nEdges, unsigned *pDirtyArray, unsigned nDirtyEdges) {
edge_head_t edge_head;
edge_map_t edge_map;
sort_edge_t sort_edge;
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
error_node enNew;
enNew.ind = nEdge;
enNew.err = pEdgesArray[nEdge];
edge_head.insert(edge_head.end(), enNew);
}
for (edge_head_t::iterator iEdge = edge_head.begin(); iEdge != edge_head.end(); ++iEdge) {
edge_map.push_back(iEdge);
}
for (unsigned nEdge = 0; nEdge < nDirtyEdges; ++nEdge) {
error_node enNew;
enNew.ind = pDirtyArray[nEdge];
enNew.err = pEdgesArray[enNew.ind];
sort_edge.push_back(enNew);
}
StartTimer();
if (!sort_edge.empty()) {
std::sort(sort_edge.begin(), sort_edge.end(), StdCompare);
sort_edge_t::iterator vec;
for (vec = sort_edge.begin(); vec != sort_edge.end(); ++vec){
edge_head.erase(edge_map[(*vec).ind]);
}
vec = sort_edge.begin();
for (edge_head_t::iterator lis = edge_head.begin(); lis != edge_head.end(); ++lis){
if ((*lis).err >= (*vec).err){
lis = edge_head.insert(lis, *vec);
edge_map[(*vec).ind] = lis;
++vec;
}
if (vec == sort_edge.end()) {
break;
}
}
while (vec != sort_edge.end()){
edge_head.push_back(*vec);
edge_map[(*vec).ind] = (--edge_head.end());
++vec;
}
sort_edge.clear();
}
StopTimer("Your");
}
void SimpleStdVectorSort(float *pEdgesArray, unsigned nEdges) {
sort_edge_t sort_edge;
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
error_node enNew;
enNew.ind = nEdge;
enNew.err = pEdgesArray[nEdge];
sort_edge.push_back(enNew);
}
StartTimer();
std::sort(sort_edge.begin(), sort_edge.end(), StdCompare);
StopTimer("std::vector");
}
void QSort(float *pEdgesArray, unsigned nEdges) {
error_node *pNodes = new error_node[nEdges];
for (unsigned nEdge = 0; nEdge < nEdges; ++nEdge) {
pNodes[nEdge].ind = nEdge;
pNodes[nEdge].err = pEdgesArray[nEdge];
}
StartTimer();
qsort(pNodes, nEdges, sizeof(error_node), &QSortCompare);
StopTimer("qsort");
delete []pNodes;
}
int SetupCompare(const void *pElem1, const void *pElem2) {
if (*(float *)pElem1 < *(float *)pElem2) {
return -1;
} else if (*(float *)pElem1 > *(float *)pElem2) {
return 1;
}
return 0;
}
int main() {
printf("Setting up. Please wait.\n");
const int nElements = 15000;
const int nRandomElements = 1000;
float *pSortArray = new float[nElements];
unsigned *pDirtyArray = new unsigned[nRandomElements];
for (int nElement = 0; nElement < nElements; ++nElement) {
pSortArray[nElement] = rand() * 4.0f / RAND_MAX;
}
qsort(pSortArray, nElements, sizeof(float), &SetupCompare);
for (int nElement = 0; nElement < nRandomElements; ++nElement) {
bool bAlreadyExists;
do {
bAlreadyExists = false;
pDirtyArray[nElement] = rand() % nElements;
for (int nTest = 0; nTest < nElement; ++nTest) {
if (pDirtyArray[nElement] == pDirtyArray[nTest]) {
bAlreadyExists = true;
break;
}
}
} while (bAlreadyExists);
pSortArray[pDirtyArray[nElement]] = rand() * 4.0f / RAND_MAX;
}
printf("Starting sorts\n");
YourSort(pSortArray, nElements, pDirtyArray, nRandomElements);
SimpleStdVectorSort(pSortArray, nElements);
QSort(pSortArray, nElements);
delete []pDirtyArray;
delete []pSortArray;
return 0;
}
The output of the above on my computer was:
Setting up. Please wait.
Starting sorts
Your sort took 63ms
std::vector sort took 154ms
qsort sort took 4ms
These results were on an array of 15,000 elements with 1,000 "dirty" elements randomly spread throughout the data. The times were only for sorting only, not setting up or pre-processing the data.
You should test with arrays of different sizes and different numbers of dirty elements that would be around what you expect to be a common case for your algorithm.
Also, I'm not sure on your situation, if you are heavily relying on the standard library, then qsort may not be the best option.
To my amazement, your algorithm was actually much faster than the plain
std::vector
sort, however it was beaten by
qsort
by a factor of 16.
You may consider adding in other comparisons such as a Binary Tree, or the earlier mentioned Red-Black Tree.