Path: csiph.com!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c++ Subject: Re: C++ threshold for "stupid" sorting algorithms (O(n^2)) Date: Tue, 21 Jan 2020 03:11:54 -0800 Organization: A noiseless patient Spider Lines: 112 Message-ID: <86iml5jc79.fsf@linuxsc.com> References: <86k15z3rm7.fsf@linuxsc.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="d01dc2e4789bccc98e4eaed72337c14b"; logging-data="21548"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19wFRQxTDjAp/faWDr3vBadHGsk8EKzT3Y=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:dx1w3PiqagMp+QA6v+SB5a+9iOQ= sha1:9jVWv7EP8oZkVKStFzaPqhslXVA= Xref: csiph.com comp.lang.c++:71482 Robert Wessel writes: > On Fri, 10 Jan 2020 13:53:52 -0800, Tim Rentsch > wrote: > >> Robert Wessel writes: >> >>> Generally the O(n**2) sorts are considered usable up a few tens of >>> items. And use insertion sort, not bubble sort (simpler algorithm, >>> twice as fast on average). >> >> The simplest bubble sort is simpler than the simplest insertion >> sort. >> >> The most complete bubble sort is simpler than the most complete >> insertion sort. >> >> It is only if we compare a somewhat less complete rendition of >> insertion sort to a somewhat more complete rendition of bubble >> sort that "insertion sort" may be called simpler. >> >> I agree that insertion sort is a better choice than bubble sort >> in almost all cases, but saying insertion sort is simpler than >> bubble sort is an apples-and-oranges comparison. > > For common definitions of what bubble and insertion sorts are, > insertion sorts are simpler. > > Standard versions in C: > > void InsertionSort(int a[], int length) > { > int i, j, temp; > > for(i = 1; i < length; i++) > { > temp = a[i]; > for (j = i - 1; j >= 0 && a[j] > temp; j--) > a[j + 1] = a[j]; > a[j] = temp; > } > } > > void BubbleSort(int a[], int length) > { > int i, j, temp; > > for (i = 0; i < length; i++) > { > for (j = 0; j < length - i - 1; j++) > { > if (a[j + 1] < a[j]) > { > temp = a[j]; > a[j] = a[j + 1]; > a[j + 1] = temp; > } > } > } > } > > There's not a lot of difference there (basically all the same > lines of code, except that the "if" in the bubble sort has been > folded into insertion sort's inner loop termination test). The first function body is shorter but that doesn't mean it is simpler. The loop invariants in the first function are more complicated than those in the second function. Also I think you're being unfair in how the two function bodies are written. In most cases bubble sort is presented using a "swap()" function to exchange two elements. There are a few other deficiencies, relative to how the InsertionSort function is written, for the coding in the BubbleSort function. It's easy, and I think more usual, to present bubble sort something like this: void BubbleSort(int a[], int length) { int n, i; for (n = length; n > 1; n--) for (i = 1; i < n; i++) if (a[i-1] < a[i]) swap( a, i-1, i ); } Writing bubble sort this way also illustrates a key difference between the two: swap() is a simple and easy-to-understand abstraction. There is no analogous abstraction for the key operation in insertion sort. That lack isn't just accidental. > But there's little to add to the insertion sort, while the bubble > sort is usually enhanced by adding a check to stop if no swapping > has been done in a pass, adding more code (and if you don't, the > usual claim that bubble sort works well on already sorted files is > false). [...] More apples-and-oranges. Of course bubble sort can be enhanced in that way, but the main point of doing so is to show that the enhancement doesn't buy much. In contrast, the common follow-on to insertion sort -- using binary search to find the insertion point -- offers a significant theoretical (and often practical) advantage, in that there is now an O( n log n ) bound on the number of comparisons done. No one is arguing that bubble sort is a better practical choice for actual coding; insertion sort is clearly better, on several different axes. But supporting that argument by claiming insertion sort is simpler than bubble sort is overreaching. It's better, in the sense of making a more convincing argument, to admit that bubble sort is simpler, and then go on to explain that despite the relative simplicity of bubble sort, insertion sort (or sometimes others, depending on circumstances) is a better practical choice, for several reasons that are compelling and also clearly defensible.