I'm looking for a Pascal / Delphi implementation of InsertionSort that works indirectly on the data by calling two methods:
I'm looking for a Pascal / Delphi implementation of InsertionSort that works indirectly on the data by calling two methods:
1. function Compare(_idx1, _Idx2:integer): integer
2. procedure Swap(_Idx1, _Idx2: integer);
The first is not the problem, but so far all implementations I have found either work directly on arrays or would require a MoveByOne(StartIdx, EndIdx) operation and the possibility to temporarily store one element.
Why do I want this? My implementation of QuickSort in dzlib works with the two methods mentioned above. I would like to implement a cut off where it switches to InsertionSort as mentioned in all articles about QuickSort optimization. So far I am using CombSort, which works but is not quite as efficient as InsertionSort would be.
1. function Compare(_idx1, _Idx2:integer): integer
2. procedure Swap(_Idx1, _Idx2: integer);
The first is not the problem, but so far all implementations I have found either work directly on arrays or would require a MoveByOne(StartIdx, EndIdx) operation and the possibility to temporarily store one element.
Why do I want this? My implementation of QuickSort in dzlib works with the two methods mentioned above. I would like to implement a cut off where it switches to InsertionSort as mentioned in all articles about QuickSort optimization. So far I am using CombSort, which works but is not quite as efficient as InsertionSort would be.
Warum die Daten bewegen, währe es nicht besser nur pointer zu drehen?
ReplyDeleteWebsearch solves this easily
ReplyDeleteJust want to save writing two small methods or am I missing the real question?
ReplyDeleteDavid Heffernan so you found something? Would you care to enlighten me?
ReplyDeleteThomas Mueller google.com
ReplyDeleteDavid Heffernan thanks, that was really helpful. Never heard of this search engine before.
ReplyDeleteI feel like I'm missing something. The two methods you outline are like a couple of lines each.
ReplyDeleteUse a search engine. Then you'll get plenty of hits giving pseudo code for the insertion sort algo. Translating to Pascal is trivial for an experienced programmer. Try harder.
ReplyDeleteDavid Heffernan If that is you at your best, you should fight the urge to comment.
ReplyDeleteI'm not looking for an insertion sort algorithm, I have plenty of pseudo code and real implementations. I'm looking for an implementation that does not access the data directly but instead calls only a compare and a swap method. I'm not sure if this is possible, as the usual implementations work differently.
ReplyDeleteInsertion sort algorithm is precisely what you are asking for actually. Once you've abstracted away compare, swap and count, all that is left is the algorithm.
ReplyDeleteThe algorithm is given here: https://en.m.wikipedia.org/wiki/Insertion_sort
It's really quite trivial for any programmer to convert that into code. It's even written with swap as an operation. The only thing you need to do is recognise the compare operation, and that is obvious I am sure.
Assuming zero based arrays and the availability of the count the code is
i := 1;
while i < Count do begin
j := i;
while (j > 0) and (compare(j-1, j) > 0) do begin
swap(j-1, j);
dec(j);
end;
inc(i);
end;
That's a trivial direct translation from the top hit on a websearch.
David Heffernan thanks. I hereby apologize for being too stupid to closely examine the pseudo code after I found so many implementations that work differently.
ReplyDeleteLars Fosdal you really think so?
ReplyDeleteI just looked again and found that the pseudo code in the German Wikipedia article on InsertionSort does not use a swap call. So, yes, I am still stupid, but it wasn't as obvious as it seems.
ReplyDeleteAll of these sorting algorithms can be written in terms of these two abstracted functions. It's a very neat way to go because it makes it easy to separate the algorithm from the data and thereby reuse algorithms.
ReplyDeleteBut yeah, that German wiki article's code is confusing I agree. I know that you aren't stupid, so the whole thread didn't hang together. I was sure that if you'd seen that pseudocode in the English wiki article it would be obvious, so the only explanation I could come up with was that you hadn't looked. Of course, that wasn't the case.
Thomas Mueller Most, if not all, in-place sorting algorithms can be written using your compare and swap methods.
ReplyDeleteThat's partially why I didn't pick up that it was the algorithm itself you were after.
David Heffernan - Yes, I do. We can and should do better than merely pointing out that a question is best solved by a web search.
ReplyDeleteLars Fosdal I guess I disagree with you there. And in this instance it turned out that some more websearch was exactly what was needed.
ReplyDeleteDavid Heffernan - We do disagree there. Your approach is the SO approach. Mine is less stringent.
ReplyDeleteYes, I expect that people have googled before posting - and I know that most do - but sometimes, we all can get stuck even if the question may appear trivial.
Perhaps we are having a bad day, or we are stressed out, or we simply are erroneously looking for a different answer than the ones we find.
At that time, it is good to have friends that will bear over with our inconsistencies and imperfections, and have the patience to help us out. Those friends will not belittle our efforts or ridicule our inability to find what we are looking for.
Lars Fosdal, David Heffernan That "SO" approach drives many people away. SO itself is regarded as often toxic and unfriendly by many. I know the Delphi tag suffers from this -- and this worries me, because since SO is a key tech site we want the Delphi tag to be welcoming, not the opposite. It doesn't help the language.
ReplyDeleteOn the other hand I wanted to help but didn't get the question, so asked for clarification and got none...
ReplyDeleteAttila Kovacs No, I just wanted to make my existing QuickSort procedure a bit faster by applying the optimizations described here: https://en.wikipedia.org/wiki/Quicksort#Optimizations
ReplyDelete+Asbjørn Heid Sorry, I must have overlooked it. I guess trying to understand those various sorting algorithms and their implementation variants takes quite a lot of toll.
ReplyDeleteThomas Mueller Yeah I finally got what you were after. It just didn't occur to me that it was the algorithm itself you were struggling with, I thought you were after a smarter Swap or something due to your wish to avoid a temporary value.
ReplyDeleteThis is what I ended up with:
ReplyDeleteprocedure InsertionSort(_Left, _Right: Integer; _CompareMeth: TCompareItemsMeth; _SwapMeth: TSwapItemsMeth);
var
i: Integer;
j: Integer;
begin
i := _Left + 1;
while i <= _Right do begin
j := i;
while (j > 0) and (_CompareMeth(j - 1, j) > 0) do begin
_SwapMeth(j, j - 1);
Dec(j);
end;
Inc(i);
end;
end;
sourceforge.net - dzlib + buildtools / SvnCode / [r739] /dzlib/trunk/src/u_dzInsertionSort.pas
And this is where it is being used:
https://sourceforge.net/p/dzlib/code/HEAD/tree/dzlib/trunk/src/u_dzQuicksortPlus.pas
David Millington Delphi tag isn't any different from others. A few years ago when there were still questions to be asked, there was a much better hit rate of good to bad questions.
ReplyDeleteWhat you and so many others don't realise is that SO isn't about being nice to askers. It's about helping people. Over 99% of the help that SO provides to people doesn't come by way of answering a new question. It comes from people finding existing content. And the key to making that work is to make the good content identifiable.
The paradox of the SO naysayers is that everybody uses it on a near daily basis, and finds it indispensable. And yet complains about it.
David Heffernan There are still questions to be asked, but the feedback I see is no-one feels welcome enough in the tag to ask them.
ReplyDeleteI am aware SO is great as a reference tool. But I myself have stopped asking questions there. I disagree with your last paragraph: in my experience, there are many people - Delphi tag, and in general - who no longer use it.
David Heffernan This community is by design, not SO. Please stop trying to SO'ize it.
ReplyDeleteThere is no conflict in having a strict SO and communities like this one which has a much more relaxed attitude to those asking for help and how they raise their questions. The two are different, and hence should be treated differently.
The only hard rule her is that we focus on solving development issues, and mostly do our best to avoid business and policy topics, which are not centric to writing code.
Yes, we find answers on SO too. So what? That doesn't mean that we want this place to be SO as well.
I'd like to second the remarks on SO. I know it's off topic but these days I tend to avoid asking questions on SO if possible because you just don't know what kind of response you're going to get. Some of the worst responses I've had were from electrical engineering SO, unbelievably rude, never went back again. The Delphi tag has its fair share of unpolite individuals and I've had some tongue lashing for a number of them. To prevent SO going the way of Wikipedia, such individuals should be banded for a set period.
ReplyDeleteDavid Heffernan I don’t ask on stack overflow because of what has been said here, but it seems according to SO help that being nice is also a requirement to asking/posting questions/answers
ReplyDelete“Be nice.
Whether you've come to ask questions, or to generously share what you know, remember that we’re all here to learn, together. Be welcoming and patient, especially with those who may not know everything you do. Oh, and bring your sense of humor. Just in case.
For specific guidelines, see: Be nice - principles and practice.”
Everybody who says they don't use SO is telling a little fib. What happens is as follows:
ReplyDelete1. You don't know something.
2. You type search keywords into a search engine.
3. The search engine finds numerous hits.
4. Some of these are from SO.
5. You read a few of these, and learn what you didn't know before.
All you SO naysayers are telling me that you won't follow a search engine hit if it is an SO link? I don't believe you.
In fact I think the opposite. I think when you see an SO link and an EE link you will be more likely to follow the SO link because there is a better chance of you getting useful content. And why is that? Because SO tries to filter out the noise.
In fact, I would say that the biggest problem with SO these days is that it accepts too many dire questions that can only ever help the asker. SO is the wrong site for such questions. Those questions should be asked elsewhere. Fine. Go ahead and ask those questions elsewhere, SO is meant to be a reference.
The bottom line here is that if you don't like asking on SO it is because you are trying to ask the wrong sort of question. When you ask good questions that fit, you get good responses. Don't try to force questions that don't fit into SO. Ask them elsewhere. Here. The Emba forum. But not on SO. It's a free world. Nobody forces anybody to use SO to ask their questions.
Lars Fosdal I'm not trying to do anything of the sort. In this thread I'm just defending SO as being a different place from here, with different goals.
ReplyDeleteMocte Sandoval If you ask a question that fits, you can expect a good response. If your question doesn't fit, expect downvotes and pressure to revise it to fit.
ReplyDeleteThomas Mueller At least one mistake that I see. The condition
ReplyDeletej > 0
should be
j > _left
David Millington "it doesn't help the language". Sounds like you are blaming SO for problems of Emba's own making.
ReplyDeleteProbably that's a bit hyperbolic from me, but that's how your comment comes across.
Personally I would say that Emba's poor record on quality was rather more harmful.
David Heffernan That is not how you started out in this thread.
ReplyDeleteLars Fosdal nope, I have never said I want this community to become SO.
ReplyDeleteDavid Heffernan It is not what you say, it's how you act.
ReplyDeleteLars Fosdal I don't think you can tell me what I believe. You can't put words into my mouth. Well, you can, but I'll take them right back out.
ReplyDeleteDavid Heffernan - I don't tell you what you believe. I don't put words into your mouth. I tell you what I observe, what I perceive, i.e. how you come across to me.
ReplyDeleteLars Fosdal No. You told me I was trying to turn this place into SO. Which I'm not.
ReplyDeleteWell, it certainly looks that way, David, when you tell people off like you do.
ReplyDeleteLars Fosdal SO is one thing. This community is something else. Both have their place, and serve quite different purposes.
ReplyDeleteBut if somebody asks a question here, that might fit on SO, you can expect me to recommend doing good research and asking clearly.
I don't find asking someone to "websearch, google, and try harder" to be helpful at all. They are not asking the question at SO. They are asking it here. BTW - what happened to the SO rule "be welcoming and patient"? Has it been fully replaced with RTFM?
ReplyDeleteLars Fosdal well, it was what was needed here. Sometimes what is needed is not to tell somebody the answer, but to tell them how to find the answer.
ReplyDeleteDavid Heffernan As mentioned previously in this thread - that is not always enough nor even appropriate, IMO.
ReplyDeleteThomas Mueller I would warn that using Swap instead of MoveByOne paradigm make InsertionSort to loose its effectiveness - by 1.4 times according to my quick test. You intend to use Ins/S as fast sort method for short slices, but deteriorate its advantage over other simple methods for the sake of compatibility.
ReplyDeleteBoris Novgorodov thanks, I'm aware of that.
ReplyDeleteThomas Mueller Perhaps you didn't spot my recent comment in this thread, but in that comment I point out the bug in the code you committed to your repo. I can't see a subsequent commit fixing it.
ReplyDeleteDavid Heffernan no, I hadn't seen it. Thanks.
ReplyDeleteFixed. Unfortunately I forgot to write a unit test for that case.
ReplyDelete