* * *

Author Topic: Radixsort loses array elements  (Read 615 times)

Lupp

  • New member
  • *
  • Posts: 30
Radixsort loses array elements
« on: February 07, 2017, 11:05:20 am »
I posted this topic in the 'Beginners' subforum first: http://forum.lazarus.freepascal.org/index.php/topic,35729.0.html. Probably this was not the best choice.
But: There you find the code of my test program and the wrong results it returened for a given example.

My impression is that the Radixsort won't wortk at all. In specific I cannot see in what way it would handle negative numbers.
However, I did not yet study the dependencies starting with GQueue thoroughly.
« Last Edit: February 07, 2017, 11:08:41 am by Lupp »

Thaddy

  • Hero Member
  • *****
  • Posts: 3400
Re: Radixsort loses array elements
« Reply #1 on: February 07, 2017, 11:55:24 am »
where is that unit uRadixSort?

Lupp

  • New member
  • *
  • Posts: 30
Re: Radixsort loses array elements
« Reply #2 on: February 07, 2017, 03:56:18 pm »
Sorry. I should have mentioned that already. Igot it it from this wiki page: http://wiki.freepascal.org/Radix_sort.
It's not an "official part" of freepascal.

Nitorami

  • Full Member
  • ***
  • Posts: 189
Re: Radixsort loses array elements
« Reply #3 on: February 07, 2017, 06:04:24 pm »
1. I wonder how you get this compiled in the first place, as RadixSort expects an open array (array of integer) while you pass it a fixed arr: array [0..7] of integer.

2. When I change arr to a dynamic array and compile it with the IDE fpc 3.0.0 in compiler mode "normal", the IDE crashes with a signal 291. That may be a bug in the IDE but it may also be a deeper issue in gqueue, uradixsort or the specialization.
For some unfathomable reason, it compiles ok in mode "debug", and, yes, the output is garbage.

3. Do you really need specialisation ? Seems a bit oversophisticated to me. Why don't you use a simple straightforward 20-lines-of-code-quicksort algorithm to sort just a few integers ?

Lupp

  • New member
  • *
  • Posts: 30
Re: Radixsort loses array elements
« Reply #4 on: February 07, 2017, 09:02:47 pm »
Thank you for your interest!
Sorry again. 
I missed to state that I had slightly modified the unit URadixSort from the wiki: I had introduced to the procedure a second parametrer by value: high: Integer and I had replaced the calls to the high function, only available for ordinary (fix) arrays by the parameter high.   

1. Why? An array declared with fix index ranges is as well as strip of values of the declared type in memory as a dynamic array is - or a strip of the respective bytes or words if you prefer. And even if it might not be contiguous in every case the access by index must be organised completely transparent anyway. For the 1D-arrays  we have in the dynamic case this is rather simple as no additional memory-mapping is needed. 

2. I tried it again to compare the results for a dynamic array and an ordinary array with identical content. No difference! (See attached example: lpi, lps and pas.)

3. It's not about urgent needs. I got back to thinking about sorting for principal reasons as I did every few decades for a long time now. 30+ years ago I "invented" the non-comparing sorts (Yes, I kow I was not the first one to do so. Otherwise the algorithm would be known now as LexiSort instead of what we have.) and was since fascinated by the high efficiency. Since about 1990 I used LexiSorting as a kind of benchmark on my PCs. A few years ago when I last ran it on my supermarket computer, it did the queuing for 10 000 000 words of up to 10 letters in German Telefonbuchordung in just 1 (0ne!) second.

In 1993 when my procedure got its present shape (only slightly adapted later for FreePascal), I did not include sorting for numbers. I now started an attempt to complete the job - and was mildly surprised to find the mentioned unit which did not pay any attention to the problems concerning the numeric types that I saw. I was not so much surprised that it didn't work. However, most of the underlying unit GQueue is no Pascal source  but just relies on "inline" code. I cannot learn anything interesting about it without spending a lot of time. I will omit it and return to my "flat" style of programming for the purpose. Due to my age it may also be necessary to abandon the subject.

Thanks again.
« Last Edit: February 07, 2017, 09:10:26 pm by Lupp »

 

Recent

Get Lazarus at SourceForge.net. Fast, secure and Free Open Source software downloads Open Hub project report for Lazarus