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.

Could you give an example of what the output should be for the example list you provided? I am having a hard time following along with your description. — Patch Rick Walsh
– Patch Rick Walsh, Commented Jul 27, 2013 at 0:59
Is this supposed to be a Shellsort? Because if it is, I don't think you quite understand the idea. You're supposed to do the subsorts with an insertion sort, and you're supposed to perform the subsorts for every subsequence of a given gap length, not just the sequences starting at the first element. — user2357112
– user2357112, Commented Jul 27, 2013 at 1:08
It seems like it might be a combsort. That's the only other sorting algorithm I can think of using the concept of "gaps". — greatwolf
– greatwolf, Commented Jul 27, 2013 at 1:21
Step 1: Write insertion sort. Step 2: Modify your insertion sort to take start and stride parameters, so you can use it on sublists of a list. Step 3: Write a routine that runs your insertion sort with the starts and strides dictated by this algorithm. — user2357112
– user2357112, Commented Jul 27, 2013 at 1:37

greatwolf · Accepted Answer · 2013-07-27 02:02:43Z

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:

Implement the bubblesort algorithm first. The logic is simpler and makes it much easier to reason about as you write it.
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.
After each iteration of the loop you decrease the gap length(in effect making the comb shorter) by some scaling amount.
The last step would be to experiment with different gap lengths and formulas to see how it affects algorithm efficiency.

Collectives™ on Stack Overflow

Sorting Technique Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related