### BlueDiamond's blog

By BlueDiamond, history, 2 months ago, , Hi!

I was playing around with sorting algorithms and came up with this ideea

Code

I am wondering how many times this code goes through the while loop

Also if you think that variations of this code (like changing the order in which we go through the powers of 2) could work better please let me know.

Thanks!  Comments (13)
 » Please don't do this: bool changes = 1; 
 » 2 months ago, # | ← Rev. 2 →   Well from my testing your version is really slow even for $n = 10^6$, however, this modification seems to make it reasonably fast: vector solve(vector a) { shuffle(a.begin(), a.end(), rng); int n = (int) a.size(); bool changes = true; int cnt = 0; while (changes) { cnt++; changes = false; for (int x = n - 1; x > 0; x /= 2) { for (int i = 0; i + x < n; i++) { if (a[i + x] < a[i]) { swap(a[i], a[i + x]); changes = true; } } } } assert(is_sorted(a.begin(), a.end())); cout << cnt << "\n"; return a; } 
•  » » "Please don't do this: bool changes = 1" Can you explain why ?
•  » » » Not readable code.
•  » » » Keywords true and false are there for a reason
•  » » Thanks, it makes a lot of sense why it works better when we start from a larger number and devide it by 2.
 » I think it's something similar to Shellsort.
•  » » Thanks for pointing this out. Indeed, it is quite similar to Shellsort.
•  » » These days I am very busy, I have a lot of work to do...( ͡° ͜ʖ ͡°)
»
2 months ago, # |
Rev. 2

Hello BlueDiamond.

I tried finding out the time complexity of the sorting algorithm in a rather experimental way. Here's what I found.

### Assumptions

• since it is a comparison-based sort, I'll count the number of comparisons

• tested for strictly decreasing sequences only

• rng equals

rng

### What I did next

• generated $10,000$ strictly decreasing sequences of the form
sequences
• I counted the total number of comparisons done by solve for each array

• printed the number of comparisons for each sequence along with the length of the sequences into a csv

• wrote a Python3 script to plot the csv

### Findings

This is what the plot looks like.

It seems that $O(N \log{N})$ is a reasonable asymptote.

#### Codes

solver.cpp
script.py
Makefile

Hope this helps. :)

•  » » You need to count number of comparisons, not number of swaps.
•  » » » Thanks _overrated_! It was very stupid of me. I edited the answer accordingly. :)