Sorting algorithms

Some time ago I suddenly got an idea for a new sorting algorithm. What if you walked through an unsorted list of numbers, doing so until the next number was no longer greater than its predecessor, moved that number to the front and started again? I soon realized that this was a very brute and therefore somewhat inefficient approach. Performance could drastically improve if you don’t move the smaller number to the fron but keep it in memory during your next walk-through and insert it into the right spot when you pass it.

I wanted to test this so I made a Java program to implement my new sorting algorithm, which I dubbed ‘H sort’. Of course I needed a benchmark to test against, and I recalled the famous Q sort algorithm from my freshman year. I dusted off my old Pascal book (never thought I’d ever do that again!) and used it to implement Q sort in Java. Strangely enough Q sort does not seem to be in any standard Java library.

As I’d thought, brute H sort performed tragically badly. Its speed also seems highly dependent on the degree of ‘unsortedness’ of the sort list. Sorting an array of 10 integers ranging from 1 through 100 takes approximately 45 microsecs for Q sort, while brute H sort needs 80 up to 600 micros! Improved H sort takes around 50 micros, so that’s indeed quite acceptable.

Further comparing Q and (improved) H sort:

  • Array size 50: 125 vs. 520 micros
  • Array size 100: 260 vs. 1800 micros
  • Array size 1000: 4,000 vs. 18,000 micros

OK, so it’s quite good but not nearly as good as the old Q sort! Of course I need to test this further, running tests automatically for many times and averaging the results. I also want to vary the degree of ‘sortedness’ of the arrays, using partly-sorted ones for testing. I hope to work on this in my spare time the coming days and I’ll keep you posted! I’ll also look into whether this ‘H sort’ algorithm of mine is indeed new or if someone already came up with this (which seems very likely).

Verkiezingen: democratie als legitimatie van de staat?

Gisteren mochten we stemmen. Een democratisch recht dat ons een héél klein beetje invloed geeft op waar het in dit land naartoe gaat. We stemmen met om en nabij de 10 miljoen mensen om 150 Tweede Kamer-zetels te verdelen over enkele politieke partijen. Na een moeizaam formatieproces gaan een paar van deze partijen die al dan niet een meerderheid van zetels hebben en het enigszins met elkaar kunnen vinden, een regering vormen. Deze regering gaat vervolgens beleid maken en uitvoeren, en de door ons gekozen Tweede Kamer legt zich toe op zijn eigenlijke taak: het controleren van de regering. Beleid ligt overigens al voor minstens zo’n 80 procent vast; op de rest kan de regering enige invloed uitoefenen.

Je invloed in dit spel is natuurlijk miniem. Jouw ene stem maakt feitelijk niet uit. Maar als niemand zou gaan stemmen, werkt het systeem ook weer niet.

Het gaat met name om trends, om wat grote groepen mensen vinden, onder invloed van groepsprocessen en natuurlijk de media. Als er op een gegeven moment het groepsgevoel ontstaat dat Samsom het best goed doet, dan heeft dat enorme invloed omdat heel veel mensen daar hun stemgedrag op aanpassen. En dan is Roemer ineens zijn extra zetels kwijt.

Democratie gaat dus om groepsdynamiek en niet om individuele stemmen. Is het daarmee een slecht systeem? Ik weet het eerlijk waar niet; ik kan me momenteel nog geen beter systeem indenken. Misschien is het wel waar wat ze zeggen, dat democratie de minst slechte staatsvorm is.

Het waarom van de staat

Feit is dat we een staat nodig hebben. Voor mij als klassiek liberaal het liefst voor zo min mogelijk taken, maar in ieder geval politie, justitie en defensie. De eigendomsrechten van de burgers op hun eigen lichaam, persoon en de vruchten van hun arbeid moeten bewaakt worden. Niemand mag zich daaraan onttrekken, anders dreigt wetteloosheid en wanorde. We moeten dus iets van een staat boven (naast?) ons dulden om ons tegen de rotte appels onder ons te beschermen. En deze staat moet op enige wijze gelegitimeerd worden, zodat de mensen deze situatie accepteren. Vroeger deed een door God zelf aangewezen koning of keizer het erg goed. Daar geloven we nu toch niet meer zo in. Het ritueel van de democratie is nu feitelijk de legitimatie van de staat geworden. Je hebt invloed op het beleid van de staat, zij het minimaal, en daarmee is de staat ook een beetje van jou.

Ik vind persoonlijk dat dit mechanisme niet volledig voldoet. De staat groeit maar door en trekt steeds meer taken naar zich toe. En de meeste burgers vinden dit nog prima ook! Het verdelen van belastinggeld over bepaalde groepen helpt hier natuurlijk bij. Maar goed, nu wijk ik wat te ver af van het thema van deze post, democratie als legitimatie van de staat. Thema’s als belastingen kunnen later mooi nog eens aan bod komen.

Feit is dat ik op dit moment nog geen goed alternatief voor democratie zie, waarbij burgers meer invloed hebben op de staat en deze beter in toom kunnen houden. Daar kan ik de komende tijd dus nog eens flink over lezen en nadenken, terwijl ondertussen in Den Haag de heren Samsom en Rutte hun formatiedans dansen!