-1

I was playing around with sorting algorithms and manage to work out bubble sort and select sort but I also Created this other method on accident and have no idea why it works. I tested the weirdsort method with large randomly generated lists and it worked every time.

def weirdsort(x):
    for i in range(len(x)):
        for j in range(len(x)):
            if (x[i] < x[j]):
                x[i], x[j] = x[j], x[i]

def bubblesort(x):
    for i in range(len(x)):
        for j in range(0, len(x) - i - 1):
            if (x[j] > x[j+1]):
                x[j], x[j+1] = x[j+1], x[j]


def selectsort(x):
    for i in range(len(x)):
        minindex = i
        for j in range(i+1, len(x)):
            if (x[minindex] > x[j]):
                minindex = j
        x[i], x[minindex] = x[minindex], x[i]
newatcodn
  • 11
  • 1
  • 4
    it's just an even less efficient bubble sort. If you want to see why it works, just feed it a relative short shuffled list and make it print what it does in your inner loop – Mike 'Pomax' Kamermans Mar 28 '23 at 05:36
  • 1
    Your `weirdsort` is a variation of `selectsort` with a higher number of swaps which makes it less efficient. – Ake Mar 28 '23 at 05:37
  • @Mike'Pomax'Kamermans It's no bubble sort. Bubble sort never swaps pairs that are already in the correct order. – Kelly Bundy Mar 28 '23 at 21:29
  • @Ake No it isn't. – Kelly Bundy Mar 28 '23 at 21:35
  • @KellyBundy no, "normal" bubble sort doesn't, but this one does, hence the "even less efficient" descriptor. It's a bubble sort that actively unsorts some elements each pass, but unsorts fewer elements than it sorts. There is (for good reason) no established name for that =) – Mike 'Pomax' Kamermans Mar 29 '23 at 00:46
  • @Mike'Pomax'Kamermans Bubble sort also only swaps adjacent elements. This is really nothing like bubble sort. The closest normal algorithm is really insertion sort. – Kelly Bundy Mar 29 '23 at 00:51

1 Answers1

1

I would regard this as an (inefficient) implementation of insertion sort, except for the first iteration of the outer loop: this iteration will put the greatest value at index 0. But from then onwards, it operates as insertion sort, always moving the next value into the sorted left-partition of the list.

Details

In the first iteration of the outer loop the greatest value will be swapped to index 0. This should be clear: the value at index 0 is swapped when a greater value is encountered, and so all values are compared with it, guaranteeing the greatest value will end up there. If you wish you could interpret this as one iteration of selection sort in descending order.

From the second iteration onwards this really is insertion sort:

As in the first iteration, the greatest value will be swapped into the current index i. But this time we know that the greatest value was sitting at the previous index, so when j==i-1 that swap will occur. That also means that when j > i no swaps will happen anymore, and so the values at the right of index i will not change -- they remain as they were right after the first iteration of the outer loop.

Secondly, the values at the left of index i will remain sorted -- this is an invariant of the outer loop. We can prove this by induction. We know it is true after the first iteration, and as the inductive step we can reason as follows:

The value originally at index i will be swapped backwards as soon as arr[j] is a greater value, so that all up until arr[j] is sorted correctly, and the new value at arr[i] is greater than that. Such swaps will keep occurring as j increases, and ultimately, at j==i-1, a last swap will occur. At every swap, the sort order up to (and including) index j is guaranteed until this last swap occurs and j becomes equal to i. At that moment the values up to index i (including it) are in sorted order.

This practically means that from the second iteration onward, the value at index i is "rotated" into the sorted partition of the list (at the left of index i). At the end, the sorted partition is the whole list.

trincot
  • 317,000
  • 35
  • 244
  • 286