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

Question

[andrei selderei]

Есть такой массив (50 элементов):

$data = [
  ['id' => 123, 'price' => 665],
  ['id' => 143, 'price' => 95],
  ['id' => 113, 'price' => 765],
 ...
];

Задача: написать функцию которая полностью отсортирует данные максимум за 6 вызовов, с условием что за 1 вызов ни один элемент не сместиться больше чем на 5 позиций.
Буду очень благодарен за помощь.
Подозреваю что при каждом вызове функции надо как-то частично упорядочить элементы но как это сделать не могу придумать...

Comments

[andrei selderei]

Hellayas, Мне бы хоть намек в какую сторону копать...

[Шохрух Шаймардонов]

andrei selderei, сортировка слиянием? Работает рекурсивно.

Answer 1

[jcmvbkbc]

Есть такой массив (50 элементов):
Задача: написать функцию которая полностью отсортирует данные максимум за 6 вызовов, с условием что за 1 вызов ни один элемент не сместиться больше чем на 5 позиций.

Очевидно, что задача в такой постановке в общем случае неразрешима, т.к. максимальный элемент стоящий первым должен сместиться в процессе сортировки в самый конец, т.е. на 49 позиций, а 49 > 6 * 5.

Comments

[andrei selderei]

Все правильно, но в конкретном случае есть точный набор данных в котором можно упорядочить элементы смещая каждый меньше чем за 6*5 позиций.

Answer 2

[andrei selderei]

Решил вопрос с применением Insertion Sorting с ограничением смещении элементов.
Код ниже если кому-то пригодится.

$data = [
    ['id' => '3823361_11_0', 'ctr' => 8.092, 'turnover' => 12322.08],
    ['id' => '481231_11_0', 'ctr' => 7.661, 'turnover' => 9421.45],
    ['id' => '5286291_11_0', 'ctr' => 9.722, 'turnover' => 417.10],
    ['id' => '382581_11_0', 'ctr' => 6.217, 'turnover' => 5725.30],
    ['id' => '393571_11_0', 'ctr' => 8.997, 'turnover' => 1617.05],
    ['id' => '4763481_11_0', 'ctr' => 8.424, 'turnover' => 712.10],
    ['id' => '602021_11_0', 'ctr' => 4.867, 'turnover' => 3456.90],
    ['id' => '39101_11_0', 'ctr' => 7.622, 'turnover' => 982.60],
    ['id' => '413791_11_0', 'ctr' => 3.953, 'turnover' => 2578.90],
    ['id' => '34131_11_0', 'ctr' => 9.226, 'turnover' => 624.65],
    ['id' => '43351_11_0', 'ctr' => 9.169, 'turnover' => 1574.05],
    ['id' => '475331_11_0', 'ctr' => 9.208, 'turnover' => 2104.55],
    ['id' => '475481_11_0', 'ctr' => 3.650, 'turnover' => 3783.62],
    ['id' => '38181_11_0', 'ctr' => 11.047, 'turnover' => 637.75],
    ['id' => '599461_11_0', 'ctr' => 10.419, 'turnover' => 292.05],
    ['id' => '41811_11_0', 'ctr' => 2.505, 'turnover' => 3382.70],
    ['id' => '517561_11_0', 'ctr' => 2.848, 'turnover' => 1886.30],
    ['id' => '548751_11_0', 'ctr' => 3.672, 'turnover' => 918.42],
    ['id' => '549171_11_0', 'ctr' => 11.253, 'turnover' => 2042.65],
    ['id' => '5931_411_0', 'ctr' => 11.397, 'turnover' => 1443.00],
    ['id' => '44341_11_0', 'ctr' => 1.587, 'turnover' => 2247.80],
    ['id' => '3930561_11_0', 'ctr' => 2.652, 'turnover' => 253.80],
    ['id' => '380r91_11_0', 'ctr' => 4.995, 'turnover' => 1160.60],
    ['id' => '340311_11_0', 'ctr' => 2.383, 'turnover' => 5283.92],
    ['id' => '483021_11_0', 'ctr' => 12.717, 'turnover' => 2547.90],
    ['id' => '643701_11_0', 'ctr' => 12.673, 'turnover' => 1244.50],
    ['id' => '6434601_11_0', 'ctr' => 1.327, 'turnover' => 0.00],
    ['id' => '649661_11_0', 'ctr' => 1.583, 'turnover' => 55.50],
    ['id' => '649541_11_0', 'ctr' => 1.000, 'turnover' => 303.05],
    ['id' => '643561_11_0', 'ctr' => 2.412, 'turnover' => 417.54],
    ['id' => '646511_11_0', 'ctr' => 1.000, 'turnover' => 575.00],
    ['id' => '6454381_11_0', 'ctr' => 1.172, 'turnover' => 0.00],
    ['id' => '6393711_11_0', 'ctr' => 1.823, 'turnover' => 10246.95],
    ['id' => '6454171_11_0', 'ctr' => 2.521, 'turnover' => 0.00],
    ['id' => '393731_11_0', 'ctr' => 3.421, 'turnover' => 113.00],
    ['id' => '645791_11_0', 'ctr' => 0.571, 'turnover' => 620.15],
    ['id' => '476591_11_0', 'ctr' => 5.172, 'turnover' => 3059.00],
    ['id' => '6466651_11_0', 'ctr' => 1.262, 'turnover' => 816.80],
    ['id' => '346361_11_0', 'ctr' => 2.313, 'turnover' => 1875.70],
    ['id' => '382531_11_0', 'ctr' => 4.918, 'turnover' => 202.75],
    ['id' => '6564471_11_0', 'ctr' => 1.392, 'turnover' => 319.60],
    ['id' => '5471_11_0', 'ctr' => 2.643, 'turnover' => 180.55],
    ['id' => '6466551_11_0', 'ctr' => 1.563, 'turnover' => 71.40],
    ['id' => '6355951_11_0', 'ctr' => 2.878, 'turnover' => 375.85],
    ['id' => '6445971_11_0', 'ctr' => 1.081, 'turnover' => 0.00],
    ['id' => '344301_11_0', 'ctr' => 3.542, 'turnover' => 126.00],
    ['id' => '642831_11_0', 'ctr' => 0.699, 'turnover' => 169.20],
    ['id' => '631891_11_0', 'ctr' => 1.852, 'turnover' => 4040.90],
    ['id' => '645341_11_0', 'ctr' => 0.952, 'turnover' => 197.50],
    ['id' => '123', 'ctr' => 3.494, 'turnover' => 0.00],
];

$data = array_map(function ($element, $index) {
    $element['initial_position'] = $index;
    $element['moved_positions'] = 0; 
    return $element;
}, $data, array_keys($data));

function mySort($data, $maxPositionsToMove = 5)
{
    for ($index = 0; $index < count($data); $index++) {
        $element = $data[$index];
        $j = $index - 1;

        $totalSwaps = 0; 
        while ($j >= 0
            && $totalSwaps < $maxPositionsToMove
            && (
                $data[$j]['ctr'] < $element['ctr'] 
                || ($data[$j]['ctr'] == $element['ctr'] && $data[$j]['turnover'] < $element['turnover']) 
            ) && abs($data[$j]['moved_positions']) < $maxPositionsToMove
            && abs($element['moved_positions']) < $maxPositionsToMove
        ) {
            $data[$j + 1]['moved_positions']--;
            $data[$j]['moved_positions']++;

            $data[$j + 1] = $data[$j]; 
            $totalSwaps++;
            $j--; 
        }
        $data[$j + 1] = $element; 
    }

    $data = array_map(function ($element) {
        $element['moved_positions'] = 0;
        return $element;
    }, $data);

    return $data;
}

// dataset after one sorting
var_dump(mySort($data));

// at this point all items should be sorted properly (after 6 sorting iterations)
var_dump(mySort(mySort(mySort(mySort(mySort(mySort($data)))))));

Answer 3

[Сергей П]

А как считать на сколько сместился элемент? По абсолютному индексу?
Ну и да, нужно сделать массив "полностью" или "немножко" отсортированным?
Из постановки задачи не ясны критерии. Полностью отсортировать любой массив нельзя за указанное число шагов с указанными ограничениями.
Нам остаётся лишь увеличивать степень упорядоченности.
Снова возвращаемся к критериям степени упорядоченности.
Их можно придумать несколько:
- количество "выбивающихся" элементов
- минимизация суммы расстояний элементов от их оптимальной позиции.
- среднее расстояние элемента от оптимальной позиции.
- суммарное расстояние элементов от оптимальной позиции.