Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #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;
}
Баян или нет?
  #2  
Старый 10.04.2011, 15:12
гостъ

 
Сообщений: n/a

да
  #3  
Старый 10.04.2011, 16:17
def def вне форума
Новичок

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

Жаль.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Повторная сортировка (или сортировка после изменений) motz-art Сортировка и поиск 3 17.08.2009 00:49