🚀 go-pugleaf

"crow" <svenb@freegates.be> writes:

> je neemt het eerste element en vergelijkt het met de rest
> is het uniek -> in de andere tabel
> dan neem je het tweede.  dit hoeft niet meer vergeleken te worden met de
> eerste en de tweede maar wel met degene die in je nieuwe tabel zitten en
> degene die na nr 2 komen
> enz..
> zodanig dat als je bij je laatste element nr 100.000 komt dan hoef je die
> enkel nog te vergelijken met de 10.000 in de nieuwe tabel
> nr 50.000 hoef je enkel te vergelijken met de gegevens in de nieuwe tabel en
> de rest van de 50.000
> 
> het zal zeker al een stuk schelen.
> er zullen wel betere methodes bestaan maar dit is de enige waar ik aan dacht
> :)

O(n^2) insertion sort achtig. 

Als je lijst gesorteerd is, is het gewoon doorlopen in O(n). Zo niet,
sorteer via een van de klassieke methodes in O(nlogn). Dit is het
beste wat je kan bereiken, tenzij je elementen een beperkt bereik
hebben. In dat geval kan je het principe van bucket sort gebruiken.

-- 
Lieven Marchand <mal@bewoner.dma.be>
Lambda calculus - Call us a mad club