5 ms·
[Edit: I took a quick glance at the paper and got carried away; the rest of this comment is about a different algorithm apparently known as "exchange sort", and
by svat 5y ago
[Edit: I took a quick glance at the paper and got carried away; the rest of this comment is about a different algorithm apparently known as "exchange sort", and an interesting property of it. The algorithm in the paper is actually different, and indeed more surprising.]
Hey! That's my sorting algorithm! (Well, I'm sure it has been independently discovered many times, but one of those times was by me before I had learned of O(n log n) sorting; I used it many times including in the INOI 2004 programming contest, about which I asked the following question ten years ago in 2011 on math.SE about this algorithm and Catalan numbers, a truly surprising property that is not mentioned in this paper: https://math.stackexchange.com/questions/36022/how-do-the-catalan-numbers-turn-up-here https://math.stackexchange.com/questions/36022/how-do-the-ca...
> For situations where a quadratic-time sorting algorithm is fast enough, I usually use the following:
//Given array a[1], ... a[n]
for i = 1 to n:
for j = i+1 to n:
if a[i] > a[j]:
swap(a[i],a[j])
> It looks like bubble sort, but is closer to selection sort. It is easy to see why it works: in each iteration of the outer loop, `a[i]` is set to be the smallest element of `a[i…n]`.
----
Also: A few years ago I emailed Prof. Richard Stanley of Enumerative Combinatorics fame asking whether it was related to any of the hundreds of problems in his Catalan Numbers list, and he said he didn't know a direct connection at the time (so maybe it's an addition to his list?):
> > permutations equal to the product of all their inversions (in lexicographic order) [multiplying on the left]
> Example: The permutation 1423 has two inversions (24) and (34), and the product (34)(24) is the same as 1423.
> Non-example: The permutation 3412 has four inversions (13), (14), (23) and (24), and the product (24)(23)(14)(13) is 4321 which is not the same as 3412.
> Among the permutations of {1, 2, 3, 4}, there are 14 examples (and 10 non-examples).
And 14 is C_4, the fourth Catalan number.
- buzzin_ 5y agoWhat do you mean, it looks like bubble sort? It is bubble sort.
- svat 5y agoBubble sort only swaps adjacent elements. The one I used is a lesser-known sort apparently called "exchange sort".
- BoppreH 5y agoNot quite, your algorithm has j going from i+1 to n, and swapping when a[i] > a[j]. OP's algorithm has both indexes going from 1 to n, and swapping when a[i] < a[j]. Yours is more efficient and easy to see why it's correct, but OP's is slightly simpler and more surprising.
- svat 5y agoOh yes, good point: I got carried away; there is a difference! Simplicity is subjective (I think mine is simpler of course :P), but the algorithm in the post is indeed more surprising.
- pricecomstock 5y agoYour algorithm does appear in Section 3.1 of the linked paper by the name "Exchange Sort"
- jeffwass 5y agoI 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.
- otto2 5y agoBack 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.
- goodcanadian 5y agoYour algorithm is in the paper as a comparison, and it is described as a standard exchange sort.
- maxk42 5y agoBecause I have a need to optimize: // Given array a[1], ..., a[n] for i = 1 to n - 1: swapped = false for j = i + 1 to n: if a[i] > a[j]: swapped = true swap(a[i], a[j]) if swapped == false: break This should reduce time complexity to O( (n - 1)^2 ) and stop sorting after the remainder of the array is sorted and tested one time.
- q-big 5y ago> This should reduce time complexity to O( (n - 1)^2 ) O((n-1)^2) = O(n^2).
- labawi 5y agoI see where you're going, but your implementation broke the sort. As for time complexity, it changes from ϴ(n²) to O(n²). Alternatively, you can drop the O-notation and calculate precisely so as to include constant factor speedups, though your algorithm may end up slower in the worst case.
- y4mi 5y agoit doesnt work though def swap(lst, a, b): tmp = lst[a] lst[a] = lst[b] lst[b] = tmp def optimized_sort(numbers): i = 0 while i < len(numbers): swapped = False j = i + 1 while j < len(numbers): if numbers[i] > numbers[j]: swapped = True swap(numbers, i, j) if swapped == False: break j +=1 i+=1 return numbers numbers = [1, 4,7,3,7,12,55,3,11,2,9,88,8] optimized_sort([*numbers]) => [1, 4, 2, 7, 7, 12, 3, 3, 8, 9, 55, 11, 88] removing the break gets you the correct order: [1, 2, 3, 3, 4, 7, 7, 8, 9, 11, 12, 55, 88]
- labawi 5y agoOriginal code would be correct, if not for a few spaces - probably a typo.
- keskadale 5y agoINOI 2004. this guy's OG.
- odonnellryan 5y agoOh gosh. Now you made me remember my own Catalan number problem with regards to weird solutions to generating balanced parentheses ahahaha.