Быстрый алгоритм сортировки.

[alexcon314]

Да, я исправил пост.
Первоначальный вариант был некорректным, хотя то, что на сортированном массиве merge проигрывает native, тоже примечательно, точнее merge очень незначительно прибавляет на отсортированных данных, а native "убыстряется" значительно.
Я не знаю, как меряет память scout, в диспетчере задач ситуация не такая безоблачная. Причем, нативная сортировка не потребляет памяти, ну т.е. от тика к тику память не растет. А merge с каждым тиком кушает и кушает.

Вот еще один алгоритм (http://jacksondunstan.com/articles/270)

private function shellSort(data:Array, companator:Function): void
		{
			var n:int = data.length;
			var inc:int = int(n/2);
			while (inc)
			{
				for (var i:int = inc; i < n; i++)
				{
					var temp:Sprite= data[i] as Sprite, j:int = i;
					while (j >= inc && companator(data[int(j - inc)], temp) == 1)
 
					{
						data[j] = data[int(j - inc)];
						j = int(j - inc);
					}
					data[j] = temp
				}
				inc = int(inc / 2.2);
			}
		}

По моим тестам, в скорости он не уступил merge, но память не течет.

[Akopalipsis]

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

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

private final function shellSort(array:Array, comparator:Function):void
{
 
	var data:*, i:int, j:int, gap:int, gapIndex:int, gapSequence:Array = new Array(), length:int = array.length;
	gapSequence[0] = 1;
 
	while (++i < 11)
	{
		gapSequence[i] = Math.pow(4, i + 1) + 3 * Math.pow(2, i) + 1;
 
		if (gapSequence[i] < length)
				gapIndex = i;
		else
				break;
	}
 
	gapIndex++;
 
	while(--gapIndex >= 0)
	{
		gap = gapSequence[gapIndex];
 
		i = gap - 1;
 
		while (++i < length)
		{
			j = i;
			data = array[i];
 
			while (j >= gap && comparator(data,array[j - gap]) == -1)
			{
				array[j] = array[j - gap];
				j -= gap;
			}
 
			array[j] = data;
		}
	}
}

[MikroAcse]

Так вот же она: 74 688 КБ.

[Akopalipsis]

Так вот же она: 74 688 КБ.

Спасибо! Теперь я точно уверен, где смотреть память и вдвое больше запутан, так-как у меня показывает на merge с 70 000 до 75 000, а на нативной от 70 000 до 72 000. И ноут у меня в два, а то и в три раза слабже чему у alexcon314, но почему тогда так разнятся показатели... Вот это только добавляет головной боли, остановится не разобравшись нельзя, а отвечают, как-то неохотно

[ZackMercury]

Сообщение от Akopalipsis

Спасибо! Теперь я точно уверен, где смотреть память и вдвое больше запутан, так-как у меня показывает на merge с 70 000 до 75 000, а на нативной от 70 000 до 72 000. И ноут у меня в два, а то и в три раза слабже чему у alexcon314, но почему тогда так разнятся показатели... Вот это только добавляет головной боли, остановится не разобравшись нельзя, а отвечают, как-то неохотно

В диспетчере задач память для всей среды выполнения.
Память, выделенная приложению, должна возвращаться System.totalMemory.
Хотя может я и ошибаюсь, и цифры будут одинаковы.

[alexcon314]

А еще есть мобильные платформы и линукс...работы не початый край.
Akopalipsis, я обратил внимание на один существенный факт: в merge потребляемая память растет (у меня, по крайней мере).
Динамика нехорошая, понимаете? Сколько памяти занято, как таковой - это может разниться для разных окружений (ОС+железо+мгновенные условия). Но вот если есть утечки (тенденция к увеличению потребляемой памяти без явных причин) - вот это не хорошо. Обращать внимание нужно на это.
Ну, и напомню, автор с хабра говорил что-то про пеппер, типа там ваще все круто.

[Akopalipsis]

Но вот если есть утечки

я много раз слышал слова о утечки, но в голове складывалась картинка,
что это в памяти накапливаются объекты, которые из-за неправильного кода не удаляются.
А в merge, если что-то и создается, то локально, с чем может быть связанна утечка?
Мне это очень интересно, хочется знать куда самому обращать внимание?

[alexcon314]

http://www.adobe.com/devnet/actionsc...ollection.html
профайлер http://www.monsterdebugger.com/tour
У меня он так же уверенно показывает рост памяти для merge от тика к тику. В native и shell память не растет.
Почему? Видимо, это как-то связано с созданием буферных массивов в merge-сортировке. Или с каким-то косяком в самом тесте.

[Akopalipsis]

alexcon314 Спасибо! Сейчас почитаю.

Добавлено через 4 часа 34 минуты
Что я подробно начал изучать предложенный Вами алгоритм Шелла, а он даже на сайте неправильно работает. Вот пример кода скопированного с сайта -

package 
{
	import flash.display.Sprite;
	import flash.geom.Point;
 
	public class Main extends Sprite 
	{
		private var _array:Vector.<Point>;
 
		public function Main() 
		{
			_array = new <Point>[];
 
			for (var i:int = 0; i < 10; i++) 
			{
				_array[i] = new Point(random(),0)
			}
 
			shellSort(_array);
		}
		private function shellSort(data:Vector.<Point>): void
		{
			var n:int = data.length;
			var inc:int = int(n/2);
			while (inc)
			{
				for (var i:int = inc; i < n; i++)
				{
					var temp:Point= data[i], j:int = i;
					while (j >= inc && data[int(j - inc)].x > temp.x)
					{
						data[j] = data[int(j - inc)];
						j = int(j - inc);
					}
					data[j] = temp
				}
				inc = int(inc / 2.2);
			}
 
			for (var k:int = 0; k < data.length; k++) 
			{
				trace((data[k] as Point).x); // 2,3,4,5,5,5,5,6,9,7
			}
		}
 
		private function random():int
		{
			return Math.random() * 10;
		}
	}
}

[ZackMercury]

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

Может, кто подскажет?)