|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Val Krigan 2:5020/400 08 Apr 2003 08:33:10
To : Ilya Teterin
Subject : Re: Сортировка
--------------------------------------------------------------------------------
"Ilya Teterin" wrote
> Представляю свое кривое творение:
>
> #include <vector>
............
> void sort_node(elementtype_node & node){
> qsort(&node[0],node.size(),sizeof(elementtype),&sortfunc);
> };
> 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 содержит не более одного
элемента).
комментарий: =8-0 УЖАС!!!
Почему бы не проще
// счетчик, инициализируемый нулем
struct intZ{
int n;
intZ() : n(0) {}
void operator ++() {n++;}
};
// получаем указатель и размер
void sort_it(float *p, int N){
hash<float,intZ> cont;
// заносим, сложность O(N)
for(i=0; i<N; i++)
cont[p[i]].second++;
// к этому моменту в контейнере содержатся все элементы и кол-во каждого в
исходном массиве
// осталось их отсортировать и распечатать, используем тот же массив
my_copy(p,cont.begin(),cont.end()); // копируем туда все float, ключи
sort(p,p+cont.size()); // сортируем, размер алфавита, ОДИH РАЗ
// печатаем
for(i=0; i<cont.size; i++)
for(j=0;j<cont[p[i]].second; j++)
cout << p[i];
// УСЕ
ЗЫ: Это не компилируемый код, просто для демонстрации ключевых моментов.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
