0

Реализовываю на js алгоритм сортировки подсчетом. Если кратко алгоритм: У нас есть массив чисел(int/float), и мы подсчитываем кол-во одинаковых элементов, а потом просто выводим их в нужном порядке. Пример: Массив - 5, 2, 4, 1, 7, 3, 2, 3, 5, 9, -2, 0, 5, 2 Подсчитали:

-2: 1
 0: 1
 1: 1
 2: 3
 3: 2
 4: 1
 5: 3
 7: 1
 9: 1

и выводим: -2, 0, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 7, 9

Проблема в том, что в js нету такого как массив с ключами. Но есть объекты.

Как названия параметров я использую значения которые надо отсортировать. Но столкнулся с проблемой что js очень странно сохраняет порядок параметров объекта: сначала положительные числа от меньших к большим, а после них - отрицательные, но уже от больших к меньшим. Вот пример:

0: 1
1: 1
2: 2
3: 1
4: 1
5: 1
-2: 1
-3: 3
-4: 1
-5: 3

Подозреваю что js просто сортирует их как символьные строки.

Я знаю что можно сделать из объекта массив массивов с элементами значение-ключ, который можно упорядочить, но это дополнительная сортировка которая значительно повлияет на результат. Скажите пожалуйста, можно ли как-то по дефолту указать чтобы параметры были нормально отсортированы, или возможно как-то по другому их выводить. Спасибо


Обновлено: Положительные числа выводятся в нужном порядке, а отрицательные - в таком, в каком они создавались. Я навел пример из консоли браузера, в ней они сортировались, но не отображался реальный порядок.

8
  • не понял, а зачем подсчитывать вообще кол-во элементов?
    – Zhihar
    7 ноя 2020 в 16:06
  • алгоритм таков, написано же
    – teran
    7 ноя 2020 в 16:07
  • @Zhihar Это метод сортировки подсчетом. Считаем сколько есть одинаковых элементов и выводим в нужном порядке 7 ноя 2020 в 16:08
  • сортировки в объекте поменять не получится 7 ноя 2020 в 16:11
  • @ЕвгенийПлатов вы если с алгоритмом не знакомы, и с тем, для каких задач он применяется, то прочитайте прежде чем комментировать. В задача подразумевается что мы знаем множество возможных значений элементов, и знаем порядок их вывода.
    – teran
    7 ноя 2020 в 16:14

3 ответа 3

1

А такой алгоритм устроит (если я правильно понял)?

arr = [5, 2, 4, 1, 7, 3, 2, 3, 5, 9, -2, 0, 5, 2,];

// найти минимальное значение в массиве
min = arr[0];

for (let value of arr) {
    min = value < min ? value : min
}

// подсчитать кол-во уникальных элементов в массиве
counts = [];

for (let value of arr) {
    counts[value - min] = counts[value - min] ? counts[value - min] + 1 : 1 
}

// отсортировать значения
res = [];

for (let index in counts) {
    const value = parseInt(index) + min;

    for (let i = 0; i < counts[index]; i ++)
        res.push(value);
}

console.log(res);
10
  • реализовать одну сортировку используя другую? не кажется ли вам это бредом?
    – teran
    7 ноя 2020 в 16:18
  • кажется, потому что в описании явно используется множество которое и так сортирует ключи или я совершенно не понял приведенного в примере описания
    – Zhihar
    7 ноя 2020 в 16:21
  • В оригинале алгоритма мы не должны сортировать ключи, они должны быть уже в нужном порядке. Ну или вывести сразу правильно 7 ноя 2020 в 16:25
  • все, разобрался - изменил код, смотрите
    – Zhihar
    7 ноя 2020 в 16:31
  • В этом есть логика и код рабочий. Но c float работать не будет, т.к. Объект сохраняет в нужном порядке только положительные целочисленные значения 7 ноя 2020 в 16:40
1
const arr = [- 5, 2, 4, 1, 7, 3, 2, 3, 4.1, 5, 9, -2, 0,Math.PI, 5, 2];
const donor = [...arr];
const result = [];
let n = Math.min(...donor);
while(n<Infinity){
  result.push(n);
  donor.splice(donor.indexOf(n),1);
  n = Math.min(...donor);
}
console.log(result);
0

// Генератор случайных значений
const random = ()=>Math.trunc(10*Math.random()-5)/4;

// Массив со значениями
const array = new Array(100).fill(0).map(random);

// Вывод массива значений
console.log('array', JSON.stringify(array).replace(/.{57,62},/g,'$&\n'));

// Счетчик значений
const counter = v => [v, array.filter(n=>n==v).length];
     
// Формируем объект
const obj = Object.fromEntries([...(new Set(array))].map(counter));

// Вывод объекта до сортировки
console.log('obj', JSON.stringify(obj,null,2)
    .replace(/\"([0-9.-]+)\"/g,(...[,m])=>`[${m}]`.padEnd(7)));

// Сортируем элементы объекта по ключам
const result = Object.entries(obj).sort(([a],[b])=>Math.sign(a-b))

// В результате бyдет массив из пар ключ-значение:

// Можем выводить их построчно
for(const [key,val] of result){
    console.log(`result[${(''+key+']').padEnd(6)} = ${val};`);
}

Заметьте, результаты легко сортируются с ключами с плавающей точкой.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.