Как сортировать по неполным критериям?

Question

Сначала я попытался передать свою функцию в Array.sort, но она не сортируется правильно. Обратите внимание, как 'c' стоит перед 'a' в результате, даже если регистр if (b == 'a' && a == 'c') обрабатывается правильно.

Эти данные только для примера. Мои фактические данные не должны сортироваться по алфавиту. Он должен использовать logi c, показанный в функциях a_before_b и b_before_a.

Поскольку у меня есть только условия для определения относительного упорядочения НЕКОТОРЫХ (НЕ всех) пар элементов, может быть несколько действительный порядок элементов. Мне просто нужно произвести ЛЮБОЙ действительный заказ, где допустимые средства не противоречат ни одному из моих условий (которые определены в функциях a_before_b и b_before_a).

const sorted = ['a', 'b', 'c', 'd']; // I do NOT have access to this
const unsorted = ['c', 'd', 'a', 'b'];

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

const mySortingFunction = (a, b) => {
  if (a_before_b(a, b)) return -1;
  if (b_before_a(a, b)) return 1;
  return 0;
}

// doesn't produce correct sorting 
console.log(unsorted.sort(mySortingFunction)); // [ 'c', 'a', 'd', 'b' ]

Затем я попробовал написать свой собственный с нуля. Но он входит в бесконечное l oop, и я не знаю почему.

const sorted = ['a', 'b', 'c', 'd'];
const unsorted = ['c', 'd', 'a', 'b'];

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

const findAnUnsortedElement = array => {
  for (let [i, element] of Object.entries(array)) {
    i = +i;
    const a = element;
    const b = array[i + 1];
    if (b === undefined) return 'SORTING_COMPLETE';
    if (!a_before_b(a, b)) console.log(a, 'should not be before', b);
    if (b_before_a(a, b)) console.log(b, 'should be before', a);
    if (!a_before_b(a, b) || b_before_a(a, b)) return a;
  }
}

// from w3schools
function move(arr, old_index, new_index) {
  while (old_index < 0) {
    old_index += arr.length;
  }
  while (new_index < 0) {
    new_index += arr.length;
  }
  if (new_index >= arr.length) {
    var k = new_index - arr.length;
    while ((k--) + 1) {
      arr.push(undefined);
    }
  }
  arr.splice(new_index, 0, arr.splice(old_index, 1)[0]);
  return arr;
}

// enters infinite loop, never returns
const myCustomSort = array => {
  while (findAnUnsortedElement(array) != 'SORTING_COMPLETE') {
    const element = findAnUnsortedElement(array);
    const index = array.findIndex(el => el == element);
    console.log('moving', element);
    array = move(array, index, index + 1);
    console.log(array);
  }
  return array;
}

console.log(myCustomSort(unsorted));

Answer 1

const unsorted = ['c', 'd', 'a', 'b'];
const sorted = unsorted.sort();

Должно сработать Я не уверен, в чем ваша проблема.

Answer 2

Алгоритм в ответе, который я дал ранее и который вы (первым) приняли, действительно основан на эвристике c.

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

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

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

Вот реализация:

class Node {
    constructor(value) {
        this.value = value;
        this.prev = new Set;
        this.order = 0; // No order yet
    }
    orderWith(other) {
        if (other === this) return;
        if (a_before_b(this.value, other.value) || b_before_a(other.value, this.value)) {
            other.prev.add(this);
        } else if (a_before_b(other.value, this.value) || b_before_a(this.value, other.value)) {
            this.prev.add(other);
        }
    }
    setOrder(path = new Set) {
        // Use recursion to find length of longest path to "least" node.
        if (this.order) return; // already done
        if (path.has(this)) throw "cycle detected";
        let order = 1;
        for (let prev of this.prev) {
            prev.setOrder(path.add(this));
            order = Math.max(order, prev.order + 1);
        }
        this.order = order; // If order is 1, it is a "least" node
    }
}

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

function mySort(arr) {
    // Create a graph: first the nodes
    let nodes = {}; // keyed by values in arr
    for (let value of arr) nodes[value] = nodes[value] || new Node(value);

    // Then the edges...
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            nodes[arr[i]].orderWith(nodes[arr[j]]);
        }
    }
    
    // Set absolute order, using the longest path from a node to a "least" node.
    for (let node of Object.values(nodes)) node.setOrder();
    
    // Sort array by order:
    return arr.sort((a, b) => nodes[a].order - nodes[b].order);
}

const sorted = ['a', 'b', 'c', 'd'];
const unsorted = ['c', 'd', 'a', 'b'];
console.log(mySort(unsorted));

Answer 3

Может что-то вроде этого

const sorted = ['a', 'b', 'c', 'd']; // I do NOT have access to this
const unsorted = ['c', 'd', 'a', 'b'];

const a_before_b = (a, b) => {
  if (a == 'a' && b == 'd') return true;
  if (a == 'b' && b == 'c') return true;
  if (a == 'a' && b == 'c') return true;

}

const b_before_a = (a, b) => {
  if (b == 'a' && a == 'c') return true;
  if (b == 'b' && a == 'c') return true;
}

const mySortingFunction = (a, b) => {
  if (a_before_b(a, b)) return -1;
  if (b_before_a(a, b)) return 1;
  return 0;
}

// doesn't produce correct sorting 
console.log(unsorted.sort(mySortingFunction));