Элементы в отсортированном списке меняют относительный порядок в зависимости от того, есть ли в списке другие элементы. Алгоритм сортировки аналогичен сортировке компаний с помощью финансового сканера.
Там таблица компаний со свойствами насколько хорош бренд, насколько он паршивый, рискованный и прибыльный и т. Д.
|symbol|risk|brand|quality|cheapness|profit|
|------|----|-----|-------|---------|------|
|BHP |0 |1 |1 |0.11 |0.1 |
|MAIL |1 |1 |-1 |0.06 |0.18 |
Мы хотим отсортировать таблицу так, чтобы лучшие компании для инвестиций оказались на вершине .
Для этого необходимо сравнить компании, используя некоторую взвешенную комбинацию его параметров. Но есть проблема - параметры имеют очень разные диапазоны, одни находятся в [0.01..0.3], другие - в [1..10].
Для нормализации диапазонов мы будем использовать ранговую сортировку . Отсортируйте каждый столбец отдельно и перечислите его значения из 1 to N. Таким образом, таблица будет преобразована в:
|symbol|risk|brand|quality|cheapness|profit|
|------|----|-----|-------|---------|------|
|BHP |1 |1 |2 |2 |1 |
|MAIL |2 |1 |1 |1 |2 |
Теперь значения находятся в том же диапазоне, и мы можем сравнить их, используя взвешенную комбинацию, ниже в таблице приведен список весов, чтобы умножить его на свойства компании и подсчитать балл - единственное число, для каждой компании:
weights =
|risk|brand|quality|cheapness|profit|
|-1 |1 |1 |1 |1 |
После умножения свойств на их веса и суммирования мы можем рассчитать балл для каждой компании. А затем отсортируйте таблицу по столбцу оценок , чтобы компании с наибольшими баллами оказались наверху (см. Последний столбец):
|symbol|risk|brand|quality|cheapness|profit|score|
|------|----|-----|-------|---------|------|-----|
|BHP |1 |1 |2 |2 |1 |5 |
|MAIL |2 |1 |1 |1 |2 |3 |
Пока это работает отлично, и мы Вы можете видеть, что BHP лучше, чем ПОЧТА .
ПРОБЛЕМА
Давайте добавим больше компаний:
|symbol|risk|brand|quality|cheapness|profit|score|
|------|----|-----|-------|---------|------|-----|
|MAIL |1 |1 |-1 |0.06 |0.18 |9 |
|MAR |0 |1 |1 |0.03 |0.17 |9 |
|BHP |0 |1 |1 |0.11 |0.1 |8 |
|IHG |0 |1 |1 |0 |0.15 |6 |
|TRI |0 |1 |1 |0.02 |0.11 |6 |
Что происходит? Порядок BHP и MAIL был изменен на противоположный ! Это неправильно. Наше инвестиционное решение будет зависеть от того, сколько компаний мы добавим в список, это не кажется надежным способом заработать деньги.
ОБНОВЛЕНИЕ, следуя совету, я рассчитал ранги для второй таблицы. Похоже, что действительно алгоритм нестабилен и очень чувствителен к присутствию других элементов, небольшая разница в исходных значениях может превратиться в очень большую разницу в его рангах. Как мы теперь видим, разница в прибыли 5/1 = 5 против 2/1 = 2, когда в таблице всего 2 элемента.
|symbol|risk|brand|quality|cheapness|profit|score|
|------|----|-----|-------|---------|------|-----|
|MAIL |2 |1 |1 |4 |5 |9 | <= profit = 5
|MAR |1 |1 |2 |3 |4 |9 |
|BHP |1 |1 |2 |5 |1 |8 | <= profit = 1
|IHG |1 |1 |2 |1 |3 |6 |
|TRI |1 |1 |2 |2 |2 |6 |
ВОПРОС:
Похоже, есть алгоритм ранжирования нестабильна и чувствительна к присутствию других элементов в таблице, что может дать очень разные результаты сортировки.
Есть ли способ сделать его стабильным? Таким образом, относительный порядок A и B всегда будет одинаковым, независимо от других элементов в списке.
Что было бы лучшим вариантом для сортировки этого списка? Нормализация столбца и использование взвешенной суммы нормализованных значений для расчета оценки? (Я отказался от него, потому что считал, что нашел святой Грааль - ранжированную сортировку - и теперь могу просто игнорировать нормализацию).
CODE
const companies2 = [
{ symbol: 'MAIL', risk: 1, brand: 1, quality: -1, cheapness: 0.06, profit: 0.18 },
{ symbol: 'BHP', risk: 0, brand: 1, quality: 1, cheapness: 0.11, profit: 0.1 }
]
const companies5 = [
{ symbol: 'MAIL', risk: 1, brand: 1, quality: -1, cheapness: 0.06, profit: 0.18 },
{ symbol: 'MAR', risk: 0, brand: 1, quality: 1, cheapness: 0.03, profit: 0.17 },
{ symbol: 'BHP', risk: 0, brand: 1, quality: 1, cheapness: 0.11, profit: 0.1 },
{ symbol: 'IHG', risk: 0, brand: 1, quality: 1, cheapness: 0, profit: 0.15 },
{ symbol: 'TRI', risk: 0, brand: 1, quality: 1, cheapness: 0.02, profit: 0.11 },
]
const weights = { risk: -1, brand: 1, quality: 1, cheapness: 1, profit: 1 }
console.log("BHP better than MAIL: \n")
console.log(sort_with_rank(companies2, weights).map(({ symbol }) => symbol))
console.log("\n\n")
console.log("MAIL better than BHP:\n")
console.log(sort_with_rank(companies5, weights).map(({ symbol }) => symbol))
// Helper functions ----------------------------------------------------------------------
function sort_with_rank(table, weights) {
// Adding ranks
let containers = table.map((row) => ({ row, ranks: {} }))
let sort_key
for (sort_key in weights) {
containers = map_with_rank(
containers,
({ row }) => row[sort_key],
(item, rank) => {
item.ranks[sort_key] = rank
return item
}
)
}
// Calculating score
const containers_with_score = containers.map(({ row, ranks }) => {
let sort_key, score = 0
for (sort_key in weights) score += weights[sort_key] * ranks[sort_key]
return { row, ranks, score }
})
// Sorting by score
const sorted = sort_by(containers_with_score, ({ score }) => -score)
// Mapping to original
return sorted.map(({ row, score }) => ({ ...row, score }))
}
function map_with_rank(list, order_by, map) {
// Sorting accourding to rank
const list_with_index = list.map((v, i) => ({ v, original_i: i, order_by: order_by(v) }))
const sorted = sort_by(list_with_index, ({ order_by }) => order_by)
// Adding rank, if values returned by `order_by` are the same, the rank also the same
const sorted_with_rank = []
let rank = 1
for (let i = 0; i < sorted.length; i++) {
const current = sorted[i]
if (i > 0 && current.order_by != sorted[i - 1].order_by) rank++
sorted_with_rank.push({ ...current, rank })
}
// Restoring original order and mapping
const original_with_rank = sort_by(sorted_with_rank, ({ original_i }) => original_i)
return original_with_rank.map(({ v, rank }) => map(v, rank))
}
function sort_by(list, by) {
list = [...list]
list.sort(function(a, b) { return by(a) - by(b) })
return list
}