BlueDiamond's blog

What is the complexity of this sorting algorithm?
By BlueDiamond, history, 5 years ago, In English

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!

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Please don't do this:

bool changes = 1;
→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Well from my testing your version is really slow even for $$$n = 10^6$$$, however, this modification seems to make it reasonably fast:

vector<int> solve(vector<int> 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;
}
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    "Please don't do this: bool changes = 1" Can you explain why ?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      Not readable code.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +92 Vote: I do not like it

      Keywords true and false are there for a reason

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks, it makes a lot of sense why it works better when we start from a larger number and devide it by 2.

    → Reply
»
5 years ago, # |
  Vote: I like it +33 Vote: I do not like it

I think it's something similar to Shellsort.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks for pointing this out. Indeed, it is quite similar to Shellsort.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you intend to make a youtube video about it?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    These days I am very busy, I have a lot of work to do...( ͡° ͜ʖ ͡°)

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

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

→ Reply