LINUX.ORG.RU
Форум — Development  

Не могу написать компаратор для qsort

 


0

1

Имеется: 

struct KeyValue{
	uint64_t value;
	unsigned int key;
};

int compare(const void* a, const void* b){
	
	return ( ((KeyValue*)a)->value - ((KeyValue*)b)->value );
}
int compare2(const void* a, const void* b){
        uint64_t f = ((KeyValue*)a)->value;
	uint64_t s = ((KeyValue*)b)->value;
	if(f == s)
		return 0;
	if(f < s)
		return -1;
	return 1;
}

1 компаратор, логично, что вычтя из unsigned unsigned - отрицательного не получится никак. Поэтому компаратор не правильно работает, на самом деле он почти сортирует, но сортирует блоками, по несколько 10 тысяч элементов. 2 компаратор, что не так в нем? Получается полная фигня на выходе из qsort.

P.S. надо сортировать именно по value, на key наплевать

★★

Последнее исправление: Chubakur (всего исправлений: 2)
← Вменяемый GUI для git под Linux.
libc хэш таблицы →

На первый взгляд все нормально, давай код вызова qsort.

И да, почему qsort, а не std::sort + перегруженный оператор функции прямо в твоей структуре?

no-such-file ★★★★★
()

Это, случаем, не из курсеровской криптографии? Я в прошлом году писал. То ли дискретный логарифм, то ли еще что-то.

cdshines ★★★★★
()
Ответ на: комментарий от cdshines

Именно он, мне в универе надо сдать по-быстренькому, а голова уже не варит

Chubakur ★★
() автор топика
Ответ на: комментарий от no-such-file

Описал 

struct KeyValue{
	uint64_t value;
	unsigned int key;
	bool operator==(KeyValue& a){
		return a.value == value;
	}
	bool operator<(KeyValue& a){
		return value < a.value;
	}
	bool operator>(KeyValue& a){
		return value > a.value;
	}
};

Вызываю сортировку: 

std::sort(mem, mem+n+1);

Итог - мусор

Chubakur ★★
() автор топика

Если компилятор поддерживает лямбды:

std::sort(mem, mem + n + 1, [](KeyValue const& l, KeyValue const& r) { return l.value < r.value; });

Или просто написать функцию compare с теми же аргументами и телом, и передать вместо лямбды compare.

BlackHawk ★
()
Ответ на: комментарий от Chubakur

А там случайно не большие числа? %u для printf ожидает unsigned int, а ему подсовывают unsigned long long, вот и получается мусор

BlackHawk ★
()
Ответ на: комментарий от adzeitor

Ага курсовая, это лабораторка :-(

mpz_init_set_str(a,"6511709995802996252529428210009069141516455100602512742258547866292839663070281213795462953359084389612327175129512390242393774885156190907043183764572298",10);
		mpz_init_set_str(b,"4016751268155181878780762958485595786864539552267966173503519872828650364102948010668074636189225260885467109630266705699778224615794326630829490560742794",10);
		mpz_init_set_str(m,"9913033868557133667485171584043308894354447793802229576147965224579616862439637051468618269920939124273132778910108308880842351094700094598897767100778663",10);
const unsigned long long  n = 1048576;



KeyValue* mem = (KeyValue*)calloc(n+1, sizeof(KeyValue));
mpz_t tmp; mpz_init_set(tmp,b);
KeyValue* memp = mem;
uint64_t* export_buffer = new uint64_t[8];
for(unsigned int x1=0;x1<=n;++x1){
			mpz_export(export_buffer,NULL,0,sizeof(uint64_t),0,0,tmp);
			memp->key = x1;
			memp->value = export_buffer[0];
			mpz_mul(tmp, tmp, a);
			mpz_mod(tmp,tmp,m);
			memp++;
}
                //qsort(mem,n+1,sizeof(KeyValue),compare);
		//std::sort(mem, mem+n+1);
		std::sort(mem, mem + n + 1, [](KeyValue const& l, KeyValue const& r) { return l.value < r.value; });
Chubakur ★★
() автор топика
Последнее исправление: Chubakur (всего исправлений: 1)
Ответ на: комментарий от Chubakur

Ну это жёстко ;)

Что-то вроде этого сможешь? 


...
...

void
printKeyValue (KeyValue *a, int n) {

  for (int i = 0; i < n; ++i)
    printf ("(%d,%ld) ", a[i].key, a[i].value);
  printf("\n");
}

int main () {
  int n = 5;
  int i;

  KeyValue* mem = (KeyValue*)calloc(n, sizeof(KeyValue));

  for(i = 0; i < n; ++i) {
    mem[i].key = i;
    mem[i].value = n-i;
  }

  printKeyValue (mem, n);
  qsort(mem,n,sizeof(KeyValue),compare2);
  printKeyValue (mem, n);

}

У меня этот код сортирует: 

(0,5) (1,4) (2,3) (3,2) (4,1) 
(4,1) (3,2) (2,3) (1,4) (0,5)

adzeitor ★
()
Ответ на: комментарий от BlackHawk

Действительно, спасибо. Выводилось просто плохо

Chubakur ★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Вменяемый GUI для git под Linux.
Development
libc хэш таблицы →