Показать сообщение отдельно
  #1  
Старый 10.04.2011, 11:44
def def вне форума
Новичок

Отправить личное сообщение для def Посмотреть профиль Найти все сообщения от def
 
Регистрация: 10.04.2011
Сообщений: 2

Сортировка экстремумами
Придумал вот такой устойчивый алгоритм сортировки, сложность O(n^2).

Идея вот в чём: допустим, нам нужно отсортировать массив по возрастанию. Для этого мы находим его минимальный элемент, добавляем его в массив-результат, а самому минимальному элементу из исходного массива присваиваем плюс бесконечность либо удаляем его. Если необходимо сортировать по возрастанию, находим максимальный элемент и присваиваем минус бесконечность.

Псевдокод:

Код:
sort(arr) {
	result = [];
	цикл по arr по итератору i:
		j = индексМинЭлемента;
		result[i] = arr[j];
		arr[j] = Infinity;
	возврат result;
}
Пример реализации на javascript:

Код:
function sort(array) {
	var result = [];
	for (var i = 0; i < array.length; i++) {
		var min = array[0], n = 0;
		for (var j = 0; j < array.length; j++)
			if (array[j] < min)
				min = array[j], n = j;
		result.push(min);
		array[n] = Infinity;
	}
	return result;
}
Баян или нет?