Recent

Author Topic: Sorting an array?  (Read 17587 times)

ArtLogi

  • Full Member
  • ***
  • Posts: 172
Re: Sorting an array?
« Reply #15 on: December 19, 2016, 08:38:15 pm »
Isn't these also depending a) memory b) time per cycle c) overall speed and the best for the task is the one with the best average features.

I don't know except that basic sort can be done with ladder logic and people started to yel that my implementation were unefficient since no bubbles nor snorts.  :D
While Record is a drawer and method is a clerk, when both are combined to same space it forms an concept of office, which is alias for a great suffering.

jollytall

  • Full Member
  • ***
  • Posts: 122
Re: Sorting an array?
« Reply #16 on: December 28, 2019, 01:40:45 pm »
@skalogryz
I am afraid, the posted algorithm (Same at: https://wiki.freepascal.org/Array_sort) is wrong.

The original QuickSort uses an arbitrary number (some places call it "Pivot"), to swap every item that is larger to higher indexes and every item that is smaller to lower indexes until the two ranges reach each other, and then one sort is finished and the two sub-parts are sorted again iteratively.

In the posted method not the middle VALUE, but the middle INDEX is fixed (mi, ms). Every time when the two "while" loops are called with CompareFunc, the parameter is NOT the original value, but the original index.
If the array "behaves" well the difference cannot be noticed (typically with low number of data points).
But, if not, when the middle element is swapped with another element, the reference is changing.

Try as an example {7,6,1,2,3,4,5}.
In the original quicksort the check is against VALUE 2. The first swap is 7-2, giving {2,6,1,7,3,4,5} and the check continues from 6 and 1 again, against the original value of 2. In gives a second swap immediately, giving {2,1,6,7,3,4,5}. The process stops here and continues with the split sets of {2,1} and {6,7,3,4,5}. OK, no overlap.
In the posted version the first swap is the same: {2,6,1,7,3,4,5} and the check continues from 6 and 1, but against a value of 7 (new value in the middle position!). So, the first "while" goes up to 7 and the second "while" stops immediately at 1, but as the index of 7 (3) is higher than the index of 1 (2), no swap is done, and the iteration continues with {2,6,1} and {7,3,4,5}, clearly showing that both 6 and 3,4,5 are in the wrong group. From hereon the sorting is correct (in this example, for larger sets it could have the same problem again), giving a final "sorted" set of {1,2,6,3,4,5,7}.

Fixing it is relatively easy, need to add a check that if the swap involved the middle index, than ms need to be updated too. It can occur only once (later the indexes have already crossed it), so mi do not need to be updated.
Code: [Select]
      Move(SwapBuf, pb[hs], Stride);
      // begin fix: update ms if the reference point is moved
      if li=mi then ms:=hs;
      if hi=mi then ms:=ls;
      // end fix
      inc(ls, Stride); inc(li);

valdir.marcos

  • Hero Member
  • *****
  • Posts: 1060
Re: Sorting an array?
« Reply #17 on: December 28, 2019, 10:51:37 pm »
Very interesting discussion.

I know it's easy enough to write your own from scratch
huh? computer scientists (1980-90) had great times over years and years, starting from scratch :D to get fast and safe sort algorithms. So I definitively disagree with "easy" LOL

Yeah, I posted this old-school approach before.
Well, let me do it again! :)

hey guys, since 1969 Pascal is a "strong typed" language, ask wikipomidia or whatever, i dont think you are going to make the team change the compiler for a weak soup like basic or sumthing... looolooooloooOOOL
https://en.wikipedia.org/wiki/Strong_and_weak_typing
I suggest you either to learn FreeBasic compiler, either to use variants LOL
Let's quote this:
> Java itself may be considered more strongly typed than Pascal
Yet in Java, arrays of the same type are the same type no matter, which file they are declared in.
java is NOT a language its a mix soup subdialect of c++ with one and only one paradigm = object.. plus it is even NOT a compiler producing machine native code but PCode wich java claimed to be new concept but HAHAH new since Fortran 77 (1977 SO! new my ass)
I've use a little and for a very short time Fortran 77 in 1990 and I neither knew nor realized that it used a virtual machine on that time.

my opinion is simple = bad workers always complain they have bad tools .. they are never guilty but the tools are ;)

avk

  • Hero Member
  • *****
  • Posts: 504
    • my self-education project
Re: Sorting an array?
« Reply #18 on: December 29, 2019, 10:55:39 am »
@jollytall, you seem to be right. Would you be kind enough to update the wiki?
But IMO, those who use this sorting, definitely should not complain that the compiler generates not quite optimal code.

jollytall

  • Full Member
  • ***
  • Posts: 122
Re: Sorting an array?
« Reply #19 on: December 30, 2019, 09:38:38 am »
@jollytall, you seem to be right. Would you be kind enough to update the wiki?

I would be happy, but three issues:
1. I hope the community can validate that my patch is really fixing the issue in all cases
2. I hope skalogryz will also read it, and build it in his own code, maybe more elegantly
3. I do not know, how to update the wiki (but probably can find it somewhere).

jollytall

  • Full Member
  • ***
  • Posts: 122
Re: Sorting an array?
« Reply #20 on: October 15, 2021, 10:00:10 am »
It took me some time, but finally I went to the wiki page and in the Discussion section commented the bug. I did not want to touch the main page, but probably it also should be done.
I also uploaded the source with some more descriptive name changes (and in my own style) to Github: https://github.com/zsoltszakaly/quicksortforpascal

jollytall

  • Full Member
  • ***
  • Posts: 122
Re: Sorting an array?
« Reply #21 on: November 11, 2021, 08:13:02 am »
JFYI: I also updated the source code on the Wiki main page: https://wiki.freepascal.org/Array_sort

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 9688
  • FPC developer.
Re: Sorting an array?
« Reply #22 on: November 11, 2021, 10:16:00 am »
Thank you!

 

TinyPortal © 2005-2018