Есть ли у кого нибудь рабочий алгоритм Плавной Сортировки на ЯП?

Question

[Proger5913]

Здравствуйте, нужен код плавной сортировки на каком нибудь ЯП, чтобы он работал. Я хз, как во всем инете так мало кода с этим алгоритмом. Желательно на C#

Comments

[xorknown]

Странно, первая же ссылка на источник в википедии содержит вполне внятный код.

[Homemade]

Плавная сортировка? Впервые слышу.

[Proger5913]

xorknown, что-то кода я не нашел

[Proger5913]

Homemade, я тоже)

[xorknown]

Proger5913, не уверен можно ли сюда кидать ссылки на данный ресурс, но код если просто пролистать вниз. Тык. После слов Этап 2

Вторая ссылка в гугле ведет на реализацию на питоне

[Евгений Шатунов]

Proger5913, так если ты сам впервые о таком алгоритме слышишь, то зачем ты его ищешь?

[Proger5913]

Евгений Шатунов, на фрилансе заказ, лол))

[Евгений Самсонов]

Может все-таки "платная" сортировка? Сколько платите? xD

[Proger5913]

Евгений Самсонов, чел ваще бомжом оказался, пришлось ему бесплатно отдать, потому что через сейф не смог он закинуть 100грн, а 200грн минимум))

Answer 1

[Yuriy Vorobyov]

Код:

кодище

private static bool IsAscending(string A, string B)
{
	return (StringType.StrCmp(A, B, false) <= 0);
}

private static void UP(ref int IA, ref int IB, ref int temp)
{
	temp = IA;
	IA += IB + 1;
	IB = temp;
}

private static void DOWN(ref int IA, ref int IB, ref int temp)
{
	temp = IB;
	IB = IA - IB - 1;
	IA = temp;
}

private static int q, r, p, b, c, r1, b1, c1;
private static string[] A;

private static void Sift()
{
	int r0, r2, temp = 0;
	string t;
	r0 = r1;
	t = A[r0];

	while (b1 >= 3)
	{
		r2 = r1 - b1 + c1;

		if (!IsAscending(A[r1 - 1], A[r2]))
		{
			r2 = r1 - 1;
			DOWN(ref b1, ref c1, ref temp);
		}

		if (IsAscending(A[r2], t))
		{
			b1 = 1;
		}
		else
		{
			A[r1] = A[r2];
			r1 = r2;
			DOWN(ref b1, ref c1, ref temp);
		}
	}

	if (Convert.ToBoolean(r1 - r0))
		A[r1] = t;
}

private static void Trinkle()
{
	int p1, r2, r3, r0, temp = 0;
	string t;
	p1 = p;
	b1 = b;
	c1 = c;
	r0 = r1;
	t = A[r0];

	while (p1 > 0)
	{
		while ((p1 & 1) == 0)
		{
			p1 >>= 1;
			UP(ref b1, ref c1, ref temp);
		}

		r3 = r1 - b1;

		if ((p1 == 1) || IsAscending(A[r3], t))
		{
			p1 = 0;
		}
		else
		{
			--p1;

			if (b1 == 1)
			{
				A[r1] = A[r3];
				r1 = r3;
			}
			else
			{
				if (b1 >= 3)
				{
					r2 = r1 - b1 + c1;

					if (!IsAscending(A[r1 - 1], A[r2]))
					{
						r2 = r1 - 1;
						DOWN(ref b1, ref c1, ref temp);
						p1 <<= 1;
					}
					if (IsAscending(A[r2], A[r3]))
					{
						A[r1] = A[r3]; r1 = r3;
					}
					else
					{
						A[r1] = A[r2];
						r1 = r2;
						DOWN(ref b1, ref c1, ref temp);
						p1 = 0;
					}
				}
			}
		}
	}

	if (Convert.ToBoolean(r0 - r1))
		A[r1] = t;

	Sift();
}

private static void SemiTrinkle()
{
	string T;
	r1 = r - c;

	if (!IsAscending(A[r1], A[r]))
	{
		T = A[r];
		A[r] = A[r1];
		A[r1] = T;
		Trinkle();
	}
}

public static void SmoothSort(string[] Aarg, int N)
{
	int temp = 0;
	A = Aarg;
	q = 1;
	r = 0;
	p = 1;
	b = 1;
	c = 1;

	while (q < N)
	{
		r1 = r;
		if ((p & 7) == 3)
		{
			b1 = b;
			c1 = c;
			Sift();
			p = (p + 1) >> 2;
			UP(ref b, ref c, ref temp);
			UP(ref b, ref c, ref temp);
		}
		else if ((p & 3) == 1)
		{
			if (q + c < N)
			{
				b1 = b;
				c1 = c;
				Sift();
			}
			else
			{
				Trinkle();
			}

			DOWN(ref b, ref c, ref temp);
			p <<= 1;

			while (b > 1)
			{
				DOWN(ref b, ref c, ref temp);
				p <<= 1;
			}

			++p;
		}

		++q;
		++r;
	}

	r1 = r;
	Trinkle();

	while (q > 1)
	{
		--q;

		if (b == 1)
		{
			--r;
			--p;

			while ((p & 1) == 0)
			{
				p >>= 1;
				UP(ref b, ref c, ref temp);
			}
		}
		else
		{
			if (b >= 3)
			{
				--p;
				r = r - b + c;
				if (p > 0)
					SemiTrinkle();

				DOWN(ref b, ref c, ref temp);
				p = (p << 1) + 1;
				r = r + c;
				SemiTrinkle();
				DOWN(ref b, ref c, ref temp);
				p = (p << 1) + 1;
			}
		}
	}
}

Вызов:

string[] data = { "Hello", "World", "Computer", "VB.Net", "PHP" };
SmoothSort(data, 5);

Результат:

Computer
Hello
PHP
VB.Net
World

Вот тут можете больше посмотреть, а еще тут, тут и тут

Comments

[Василий Банников]

можно плз простыню из кода хотябы в спойлер спрятать?
А вообще код ужасен. Сразу виден олимпиадный стиль )

[Yuriy Vorobyov]

Василий Банников, не спорю, сам ужаснулся

[Евгений Самсонов]

Код похоже писали студенты

Answer 2

[Василий Банников]

Вот вариант на питоне, например: https://habr.com/ru/company/edison/blog/496852/
Вот на C++: cppalgo.blogspot.com/2010/10/smoothsort.html
Вот на C: https://github.com/skycook/Smoothsort-C
Вот на C#: https://github.com/usmnzain/smoothsort

Вот ещё куча вариантов: https://github.com/search?q=smoothsort&type=Reposi...