### 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!

• +16

 » 2 months ago, # |   -9 Please don't do this: bool changes = 1;
 » 2 months ago, # | ← Rev. 2 →   +21 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; }
•  » » 2 months ago, # ^ |   +34 "Please don't do this: bool changes = 1" Can you explain why ?
•  » » » 2 months ago, # ^ |   -16 Not readable code.
•  » » » 2 months ago, # ^ |   +92 Keywords true and false are there for a reason
•  » » 2 months ago, # ^ |   +3 Thanks, it makes a lot of sense why it works better when we start from a larger number and devide it by 2.
 » 2 months ago, # |   +33 I think it's something similar to Shellsort.
•  » » 2 months ago, # ^ |   +8 Thanks for pointing this out. Indeed, it is quite similar to Shellsort.
 » 2 months ago, # |   0 Do you intend to make a youtube video about it?
•  » » 2 months ago, # ^ |   +12 These days I am very busy, I have a lot of work to do...( ͡° ͜ʖ ͡°)
»
2 months ago, # |
Rev. 2   -11

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. :)

•  » » 2 months ago, # ^ |   +27 You need to count number of comparisons, not number of swaps.
•  » » » 2 months ago, # ^ |   +8 Thanks _overrated_! It was very stupid of me. I edited the answer accordingly. :)