Сегодня возникла необходимость быстрой сортировки массива в программе на ActionScript. Естественно, руки потянулись использовать стандартный Array.sort(), особенно, учитывая то, что по результатам сортировки массива мне необходимо сделать соответствующие перестановки MovieClip’ов по уровням z-индексирования, т.к. Array.sort() поддерживает пользовательскую функцию сравнения элементов.

Из-за природного недоверия решил сделать небольшой тест для встроенной функции сортировки класса Array. Результаты удивили. Оказалось, что стандартный метод использует пузырьковую сортировку. Печально. Ну да ладно. Пришлось сделать быструю сортировку (quick sort).

При сортировке массива из 10 элементов в обратном порядке встроенный метод Aaray.sort() с указанием пользовательской функции сделал 49 сравнений элементов.
Да, это худший вариант для алгоритма bubble sort (когда исходный массив имеет обратную сортировку относительно конечного), но это не реабилитирует разработчиков Flash - могли бы встроить и Quick Sort, благо - алгоритм несложный.

function quickSort(a, left, right) {

	if (left == undefined) left = 0;
	if (right == undefined) right = a.length-1;

	var i = left;
	var j = right;
	var step = -1;
	var condition = 1;

	if (left >= right) {
		return;
	}

	do {
		if (condition == (a[i] > a[j])) {

			// here
			var foo = a[j];
			a[j] = a[i];
			a[i] = foo;
			_root.shiftNum++;

			foo = j;
			j = i;
			i = foo;

			step *= -1;
			condition = !condition;
		}

		j += step;

	} while (j != i);

	quickSort(a, left, i-1);
	quickSort(a, i+1, right);
}

Там, где комментарием “here” отмечено место в коде, я просто вставил обработчик перестановок MovieClip’ов с помощью MovieClip.SwapDepths() вот и все :)

К слову… основные алгоритмы сортировки.

Спасибо flasher.ru за то, что избавил меня от написания алгоритма быстрой сортировки на AS :)

Дополнение от 26 мая:

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

Дополнение от 30 июня:
Случайно попалось на глаза - визуализация работы алгоритмов сортировки.