[Макс]

Описание: Данная функция поможет отсортировать значения из массива.

Вариант by RyDeR [Показать]

Функция:

stock quickSort(array[], left, right)
{
	new tempLeft = left,
		tempRight = right,
		pivot = array[(left + right) / 2],
		tempVar;
	while(tempLeft <= tempRight)
	{
		while(array[tempLeft] < pivot) tempLeft++;
		while(array[tempRight] > pivot) tempRight--;
		if(tempLeft <= tempRight)
		{
			tempVar = array[tempLeft], array[tempLeft] = array[tempRight], array[tempRight] = tempVar;
			tempLeft++, tempRight--;
		}
	}
	if(left < tempRight) quickSort(array, left, tempRight);
	if(tempLeft < right) quickSort(array, tempLeft, right);
}

Пример:

new array[] = { -541, 54, 689, 12, 3, 0, 3, 55, 66, -541, 5468484, -564, 1554, 1656 };
quickSort(array, 0, sizeof(array) - 1);
for(new i; i != sizeof(array); ++i)
{
	printf("%d", array[i]);
}

Вариант by ZiGGi [Показать]

Функция:

stock insert_sort(array[], const size = sizeof(array))
{
	for(new i = 1, j, key; i < size; i++)
	{
		key = array[i];
		for(j = i - 1; j >= 0 && array[j] > key; j--)
		{
			array[j + 1] = array[j];
		}
		array[j + 1] = key;
	}
}

Пример:

new array[] = { -541, 54, 689, 12, 3, 0, 3, 55, 66, -541, 5468484, -564, 1554, 1656 };
insert_sort(array);
for(new i; i != sizeof(array); ++i)
{
	printf("%d", array[i]);
}

Результат:

-564
-541
-541
0
3
3
12
54
55
66
689
1554
1656
5468484

Сообщение отредактировал Макс: 16 сентября 2017 - 12:33

[SooBad]

Во-первых - функция рекурсивная, во-вторых - совершенно ненужные циклы в цикле, в третих - очень медленная, в четвертых - где она может быть полезна?

Сообщение отредактировал SooBad: 15 сентября 2017 - 21:39

[makap]

 SooBad (15 сентября 2017 - 21:37) писал:

Во-первых - функция рекурсивная, во-вторых - совершенно ненужные циклы в цикле, в третих - очень медленная, в четвертых - где она может быть полезна?

Начнем с того, что эта быстрая сортировка. Большинство реализаций - рекурсивные, если ты не знал

Какие еще ненужные циклы в цикле? Обмены совершаются гораздо дольше, чем сравнения
Можешь погуглить алгоритм быстрой сортировки для ознакомления

Как эта сортировка может быть медленная, если она быстрее пузырьковой, вставками и т.п. (возможно, за исключением очень-очень малых последовательностей)

[SooBad]

 makap (16 сентября 2017 - 04:15) писал:

Большинство реализаций - рекурсивные, если ты не знал

LOL

 makap (16 сентября 2017 - 04:15) писал:

Какие еще ненужные циклы в цикле? Обмены совершаются гораздо дольше, чем сравнения

Обмены могут быть только в пищевой цепочке.

 makap (16 сентября 2017 - 04:15) писал:

Можешь погуглить алгоритм быстрой сортировки для ознакомления

Обязательно погуглю, как только начну сомневаться в собственных постах.

 makap (16 сентября 2017 - 04:15) писал:

Как эта сортировка может быть медленная, если она быстрее пузырьковой, вставками и т.п. (возможно, за исключением очень-очень малых последовательностей)

Ты бы ещё с методом слияния сравнил.

 makap (16 сентября 2017 - 04:15) писал:

Начнем с того, что эта быстрая сортировка.

Окау. Пруфы?

[makap]

Не надо писать то, что не понимаешь. Ты только создаешь иллюзию понимающего скриптера. Да, синтаксис языка ты знаешь. А как речь заходит об алгоритмах сортировки, то начинаешь писать конкретную херню.

Или я не правду написал? (о сортировке)

Или это такой троллинг, чтобы съехать с некорректной мысли?

Сообщение отредактировал makap: 16 сентября 2017 - 12:12

[Макс]

Добавил еще один вариант в шапку темы.

 SooBad (15 сентября 2017 - 21:37) писал:

где она может быть полезна?

Например, что бы сделать ТОП игроков. Да и вообще, применений можно найти много.

[SooBad]

 makap (16 сентября 2017 - 12:11) писал:

Не надо писать то, что не понимаешь. Ты только создаешь иллюзию понимающего скриптера. Да, синтаксис языка ты знаешь. А как речь заходит об алгоритмах сортировки, то начинаешь писать конкретную херню.

Или я не правду написал? (о сортировке)

Или это такой троллинг, чтобы съехать с некорректной мысли?

Интересно, где же ты подтверждаешь свои слова?
Ты прав - докажи, или, иначе получается, что "херню" пишешь ты)
И в чём проявляется троллинг?

[makap]

 SooBad (16 сентября 2017 - 12:35) писал:

Интересно, где же ты подтверждаешь свои слова?
Ты прав - докажи, или, иначе получается, что "херню" пишешь ты)
И в чём проявляется троллинг?

Ты не смог дать аргументированный ответ (что плохого в рекурсивной сортировке, почему эти циклы ненужные, почему сортировка медленная) на мое первое сообщение. О чем это говорит (???). И ты с меня требуешь какие-то доказательства?

Также можно сделать вывод, что если ты требуешь пруф, что это быстрая сортировка, то ты не знаешь, что такое быстрая сортировка. В вики можешь найти алгоритм.

И еще приплетаешь сюда зачем то метод слияния. Метод слияния можно реализовать так, что он будет быстрее быстрой сортировке и наоборот.

P.S. Ты ведь раньше думал, что memcpy - парсер массивов.

[SooBad]

 makap (16 сентября 2017 - 12:50) писал:

Ты не смог дать аргументированный ответ (что плохого в рекурсивной сортировке, почему эти циклы ненужные, почему сортировка медленная) на мое первое сообщение.

Аргумент с более хорошим альтернативным вариантом приложил автор темы.

 makap (16 сентября 2017 - 12:50) писал:

И ты с меня требуешь какие-то доказательства?

Да, требую, ведь пока все твои посты и упрёки звучат как балабольство.
Я могу сделать тесты, и доказать, что вариант Ziggi быстрее. Ты сомневаешься?

 makap (16 сентября 2017 - 12:50) писал:

Также можно сделать вывод, что если ты требуешь пруф, что это быстрая сортировка, то ты не знаешь, что такое быстрая сортировка. В вики можешь найти алгоритм.

Это уже ответ на твой антонимичный пост выше. Чтобы казаться умнее, ты отсылаешь на вики меня. LOL.

 makap (16 сентября 2017 - 12:50) писал:

И еще приплетаешь сюда зачем то метод слияния. Метод слияния можно реализовать так, что он будет быстрее быстрой сортировке и наоборот.

Приплёл потому, что ты смешал два сорта говнеца) Нашёл, блин, с чем сравнить быструю сортировку

 makap (16 сентября 2017 - 12:50) писал:

P.S. Ты ведь раньше думал, что memcpy - парсер массивов.

Ты ещё приплети то, что года 3-4 назад я говорил, что return true быстрее return 1.
Окау. Если ты хочешь знать, почему я так думал, объясню: функция мной никогда не задействовалась, в корне, я лишь знал про её существование, следовательно, по описанию на "вики" - я сделал вывод, что она скрещивает память двух массивов в один => что это парсер. Объективно?

Сообщение отредактировал SooBad: 16 сентября 2017 - 13:44

[makap]

 SooBad (16 сентября 2017 - 13:30) писал:

Аргумент с более хорошим альтернативным вариантом приложил автор темы.

Это не более хороший вариант. Это другая сортировка
А можно добавить сюда интроспективную сортировку (там содержится быстрая, пирамидальная и вставки)
Видимо ты не можешь аргументировать

 SooBad (16 сентября 2017 - 13:30) писал:

Да, требую, ведь пока все твои посты и упрёки звучат как балабольство.
Я могу сделать тесты, и доказать, что вариант Ziggi быстрее. Ты сомневаешься?

Найдешь такую последовательность, которая окажется наихудшим вариантом для быстрой, но лучший для вставок?
У быстрой сортировки лучшая сложность O(nlogn), а у вставок O(n) (как раз таки доказательство о скорости)
Худший случай для быстрой - тот случай, когда при каждом рекурсивном вызове разбиение будет максимально несбалансированно (опорный элемент всегда правый/левый)
А лучший случай для вставок - возрастающая последовательность, на ней у вставок не будет обменов

 SooBad (16 сентября 2017 - 13:30) писал:

Это уже ответ на твой антагоничный пост выше. Чтобы казаться умнее, ты отсылаешь на вики меня. LOL.

Уговорил, вот алгоритм с вики

algorithm quicksort(A, lo, hi) is
    if lo < hi then
        p := partition(A, lo, hi)
        quicksort(A, lo, p – 1)
        quicksort(A, p, hi)

 algorithm partition(A, lo, hi) is
    pivot := get_pivot(A, lo, hi)
    i := lo
    j := hi    
    while i < j do
        while A[i] < pivot do
          i := i + 1 
        while A[j] > pivot do
          j := j - 1 
        if i <= j then
            swap A[i] with A[j]
            i := i + 1
            j := j - 1
    return i

Похоже на реализацию автора?

 SooBad (16 сентября 2017 - 13:30) писал:

Приплёл потому, что ты также смешал два сорта говнеца) Нашёл, блин, с чем сравнить быструю сортировку

Многие не понимают быструю сортировку и им легче написать реализацию пузырьковой. Тем не менее на больших размерностях, пузырек может уснуть

___

Итеративная быстрая сортировка реализуется через стек и реализация итеративной сортировки значительно сложнее, чем рекурсивной
Поэтому принято везде использовать рекурсивную версию.