4

I have been racking my head trying to wrap my mind around this thing, but I cannot figure out the proper loop invariant and expected behavior of the following code. Any help would be much appreciated.

def modSwapSort(L): 
    """ L is a list on integers """
    print "Original L: ", L
    for i in range(len(L)):
        for j in range(len(L)):
            if L[j] < L[i]:
                # the next line is a short 
                # form for swap L[i] and L[j]
                L[j], L[i] = L[i], L[j] 
                print L
    print "Final L: ", L
KGS
  • 277
  • 2
  • 4
  • 11
  • Deleted my answer after realising that I completely misunderstood the algorithm. Sorry if I confused anyone. – wookie919 Aug 13 '14 at 02:16
  • No problem. Not sure why the -1... – KGS Aug 13 '14 at 02:28
  • This looks like an [insertion sort](http://en.wikipedia.org/wiki/Insertion_sort). What's the problem? – kylieCatt Aug 13 '14 at 02:34
  • Hmm, I haven't seen insertion sort before, checking it out. – KGS Aug 13 '14 at 02:42
  • 1
    @IanAuld Don't be fooled by the simplicity of this sorting algorithm. It's not insertion sort or bubble sort or selection sort or any other common O(n^2) sorting algorithm that people are mostly aware of. I had some time free so I actually ran the algorithm and I was very intrigued by the way it sorted. I now fully appreciate the difficulty in proving the correctness of this algorithm. – wookie919 Aug 13 '14 at 03:07
  • From a brief reading, it looks like this will just repeatedly ensure that the element at `i` is smaller than all elements to it's right. Inefficient though. – Hamish Aug 13 '14 at 03:40
  • Won't it ensure that it is the smallest element in the list? – KGS Aug 13 '14 at 03:49
  • 2
    @KGS If you're still interested : https://stackoverflow.com/questions/69437526/what-is-this-odd-sorting-algorithm – Dost Arora Oct 05 '21 at 21:26
  • Link to discussion: https://news.ycombinator.com/item?id=28758106 – Eran Medan Jul 04 '22 at 15:00

1 Answers1

2

It is a some form of selection sort. It's complexity is O(n^2). It could be helped with some simple optimisation in a for-ranges. Because now on every i-loop step it founds the least element in j-loop and puts it in the i-th position, the second least element will be in postion (i-1) and so on. So on every step your list will look like (i=3):

[ A1, A2, A3, B1, B2] where Ak < Ak-1 and Bs are unordered.

So shorty: on every ith step you look for the least element with index greater than i, that will be greater than the first element in a list.

With some tunning of for-ranges you could minimize the comparisons and swaps count. But anyway, this algorithm will have ~ O(n^2) complexity.

English is not my native language, sorry for the typos.

simakazi
  • 53
  • 1
  • 7