|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ilya Teterin 2:5020/400 08 Apr 2003 07:47:57
To : Val Krigan
Subject : Re: Сортировка
--------------------------------------------------------------------------------
Tue Apr 08 2003 00:45, Val Krigan wrote to Vladislav Gusev:
Представляю свое кривое творение:
#include <vector>
using namespace std;
const hash_space=102400;
typedef double elementtype;
typedef vector<elementtype> elementtype_node;
typedef vector<elementtype_node> node_vector;
double min,max;
int hash_func(double arg){
return int((arg-min)/(max-min)*hash_space);
}
int __cdecl sortfunc(const void *d1, const void *d2){
elementtype *e1=(elementtype*)d1;
elementtype *e2=(elementtype*)d2;
if(*e1>*e2)
return 1;
else if(*e1==*e2)
return 0;
return -1;
};
void sort_node(elementtype_node & node){
qsort(&node[0],node.size(),sizeof(elementtype),&sortfunc);
};
void addelement(node_vector & vect, elementtype element){
vect[hash_func(element)].push_back(element);
};
int main(){
node_vector nodes(hash_space);
bool firsttime=true;
int i,j;
min=0;max=1000; // hardcoded ;)
#define X 1000000
for(i=0;i<X;i++){
double el=(rand()%10000)/100.0;
addelement(nodes,el);
}
for(i=0;i<nodes.size();i++){
sort_node(nodes[i]);
for(j=0;j<nodes[i].size();j++){
// printf("%f\n",nodes[i][j]);
};
};
return 0;
};
Комментарии: функция hash_func выбирается в зависимости от конкретной задачи,
должна возвращать значение [0..hash_space-1] и удовлетворять условию a1<a2 =>
hash_func(a1)<=hash_func(a2). В зависимости от того, насколько хорошо ее
удастся выбрать и размера hash_space, сложность сортировки изменяется от
qsort-овской (наихудший случай - все элементы попали в один hash_node) до
O(n) (наилучший случай - каждый hash_node содержит не более одного элемента).
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
