Блог пользователя BlueDiamond

What is the complexity of this sorting algorithm?
Автор BlueDiamond, история, 5 лет назад, По-английски

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
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

Please don't do this:

bool changes = 1;
→ Ответить
»
5 лет назад, # |
← 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<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;
}
→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

I think it's something similar to Shellsort.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do you intend to make a youtube video about it?

→ Ответить
»
5 лет назад, # |
← 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. :)

→ Ответить