Сортировка экстремумами

Придумал вот такой устойчивый алгоритм сортировки, сложность 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;}

Баян или нет?

10.04.2011, 14:12