Sorting Technique Python

Question

I'm trying to create a sorting technique that sorts a list of numbers. But what it does is that it compares two numbers, the first being the first number in the list, and the other number would be the index of 2^k - 1.

2^k - 1 = [1,3,7, 15, 31, 63...]

For example, if I had a list [1, 4, 3, 6, 2, 10, 8, 19]

The length of this list is 8. So the program should find a number in the 2^k - 1 list that is less than 8, in this case it will be 7.

So now it will compare the first number in the random list (1) with the 7th number in the same list (19). if it is greater than the second number, it will swap positions.

After this step, it will continue on to 4 and the 7th number after that, but that doesn't exist, so now it should compare with the 3rd number after 4 because 3 is the next number in 2^k - 1.

So it should compare 4 with 2 and swap if they are not in the right place. So this should go on and on until I reach 1 in 2^k - 1 in which the list will finally be sorted.

I need help getting started on this code.

So far, I've written a small code that makes the 2^k - 1 list but thats as far as I've gotten.

a = []

for i in range(10):
    a.append(2**(i+1) -1)

print(a)

EXAMPLE:

Consider sorting the sequence V = 17,4,8,2,11,5,14,9,18,12,7,1. The skipping sequence 1, 3, 7, 15, … yields r=7 as the biggest value which fits, so looking at V, the first sparse subsequence = 17,9, so as we pass along V we produce 9,4,8,2,11,5,14,17,18,12,7,1 after the first swap, and 9,4,8,2,1,5,14,17,18,12,7,11 after using r=7 completely. Using a=3 (the next smaller term in the skipping sequence), the first sparse subsequence = 9,2,14,12, which when applied to V gives 2,4,8,9,1,5,12,17,18,14,7,11, and the remaining a = 3 sorts give 2,1,8,9,4,5,12,7,18,14,17,11, and then 2,1,5,9,4,8,12,7,11,14,17,18. Finally, with a = 1, we get 1,2,4,5,7,8,9,11,12,14,17,18.

You might wonder, given that at the end we do a sort with no skips, why this might be any faster than simply doing that final step as the only step at the beginning. Think of it as a comb going through the sequence -- notice that in the earlier steps we’re using course combs to get distant things in the right order, using progressively finer combs until at the end our fine-tuning is dealing with a nearly-sorted sequence needing little adjustment.

p = 0
x = len(V) #finding out the length of V to find indexer in a
for j in a: #for every element in a (1,3,7....)
    if x >= j: #if the length is greater than or equal to current checking value
        p = j #sets j as p 

So that finds what distance it should compare the first number in the list with but now i need to write something that keeps doing that until the distance is out of range so it switches from 3 to 1 and then just checks the smaller distances until the list is sorted.

Answer 1

The sorting algorithm you're describing actually is called Combsort. In fact, the simpler bubblesort is a special case of combsort where the gap is always 1 and doesn't change.

Since you're stuck on how to start this, here's what I recommend:

1. Implement the bubblesort algorithm first. The logic is simpler and makes it much easier to reason about as you write it.
2. Once you've done that you have the important algorithmic structure in place and from there it's just a matter of adding gap length calculation into the mix. This means, computing the gap length with your particular formula. You'll then modifying the loop control index and the inner comparison index to use the calculated gap length.
3. After each iteration of the loop you decrease the gap length(in effect making the comb shorter) by some scaling amount.
4. The last step would be to experiment with different gap lengths and formulas to see how it affects algorithm efficiency.