Is this the simplest (and most surprising) sorting algorithm?

Re:Is this the simplest (and most surprising) sorting algori... by jeffwass on Tuesday October 05, 2021 @12:14PM (#28761449)

I actually did the opposite! I was taught this sort in high school (I think the teacher called it shuttle interchange?), and I independently came up with the bubble sort on my own as a more-efficient in-place implementation on disk.

Back in the 90’s for my high-school computer class, we were saving records on disk using TurboPascal and I was trying to sort my file in-place.

The sort was super slow, which I assumed was the disk head having to jump back and forth over larger distances of the array of records when comparing and swapping.

I reasoned if I could keep the compares and swaps between I and I+1, and then sweep those I’s forward, it’s the same number of overall compares but less head jumping with each compare/swap being adjacent records.

My implementation did speed things up quite a bit. I have no idea if my reasoning was right, or if I had some other inadvertent bottleneck. But I was proud of the speedier result.

I never explicitly pointed it out to the teacher, though, and didn’t get full marks on that homework because he said my overall program wasn’t user friendly enough.

[ Parent | on HN ]

Re:Is this the simplest (and most surprising) sorting algori... by otto2 on Tuesday October 05, 2021 @02:27PM (#28763516)

Back in time I was sorting records on disk using Atari ST and (probably) Omikron BASIC. I applied RADIX sort (or a variant) that I saw in one magazine. It worked as a charm on RAM disk, but once when I tried it on a floppy disk, it just took forever.

[ Parent | on HN ]