Слияние сортировки 2d массив

Question

Я снова застрял при попытке заставить работать сортировку слиянием.В настоящее время у меня есть 2d массив с тайм-кодом Unix (рис. 1) и сортировка слиянием с использованием (рис. 2). Я пытаюсь проверить первое значение в каждом массиве, т.е. массив [x] [0], а затем переместить весь массив в зависимости отзначение array [x] [0], однако сортировка слиянием создает дубликаты данных и удаляет другие данные (рис. 3). Мой вопрос: что я делаю неправильно?Я знаю, что это сортировка слиянием, но не вижу исправления.

рис 1

[[1422403200        100]
 [1462834800        150]
 [1458000000         25]
 [1540681200        150]
 [1498863600        300]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]]

рис 2

import numpy as np


def sort(data):
    if len(data) > 1:
        Mid = len(data) // 2
        l = data[:Mid]
        r = data[Mid:]
        sort(l)
        sort(r)

        z = 0
        x = 0
        c = 0

        while z < len(l) and x < len(r):
            if l[z][0] < r[x][0]:
                data[c] = l[z]
                z += 1
            else:
                data[c] = r[x]
                x += 1
            c += 1

        while z < len(l):
            data[c] = l[z]
            z += 1
            c += 1

        while x < len(r):
            data[c] = r[x]
            x += 1
            c += 1
        print(data, 'done')
unixdate = [1422403200, 1462834800, 1458000000, 1540681200, 1498863600, 1540771200, 1540771200,1540771200, 1540771200, 1540771200]
price=[100, 150, 25, 150, 300, 100, 100, 100, 100, 100]
array = np.column_stack((unixdate, price))
sort(array)
print(array, 'sorted')

рис 3

[[1422403200        100]
 [1458000000         25]
 [1458000000         25]
 [1498863600        300]
 [1498863600        300]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]
 [1540771200        100]] 

Answer 1

Я не смог обнаружить ни одной ошибки в вашем коде.

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

data = [
 [1422403200, 100],
 [1462834800, 150],
 [1458000000,  25],
 [1540681200, 150],
 [1498863600, 300],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100],
]

sort(data)

from pprint import pprint
pprint(data)

Вывод:

[[1422403200, 100],
 [1458000000, 25],
 [1462834800, 150],
 [1498863600, 300],
 [1540681200, 150],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100],
 [1540771200, 100]]

---

Редактировать с учетом контекста numpyи использование np.column_stack.

- я ожидаю, что случится так, что np.column_stack фактически создаст представление , отображающее два массива.Чтобы получить реальный массив, а не ссылку на существующие массивы, вы должны скопировать этот массив: -

array = np.column_stack((unixdate, price)).copy()

---

Edit 2 , с учетом контекста NumPy

Это поведение на самом деле не имеет ничего общего с np.column_stack;np.column_stack уже выполняет копирование.

Причина, по которой ваш код не работает, заключается в том, что нарезка ведет себя по-разному с NumPy, чем с Python.Разрезание создает представление массива, который отображает индексы.

Ошибочные строки:

l = data[:Mid]
r = data[Mid:]

Поскольку l и r просто отображаются на две частипамяти, удерживаемой data, они изменяются, когда data.Вот почему строки data[c] = l[z] и data[c] = r[x] перезаписывают значения и создают копии при перемещении значений.

Если data является массивом с пустым фрагментом, мы хотим, чтобы l и r были копиями данных., а не только взгляды.Это может быть достигнуто с помощью метода copy.

l = data[:Mid]
r = data[Mid:]
if isinstance(data, np.ndarray):
    l = l.copy()
    r = r.copy()

Таким образом, я протестировал, копия работает.

---

Примечание

Если вы хотите отсортировать данные, используя списки Python, а не массивы, эквивалентный np.column_stack в vanilla python zip:

z = zip([10, 20, 30, 40], [100, 200, 300, 400], [1000, 2000, 3000, 4000])
z
# <zip at 0x7f6ef80ce8c8>
# `zip` creates an iterator, which is ready to give us our entries.
# Iterators can only be walked once, which is not the case of lists.

list(z)
# [(10, 100, 1000), (20, 200, 2000), (30, 300, 3000), (40, 400, 4000)]

Записи являются (неизменяемыми) кортежами.Если вам нужно, чтобы записи были редактируемыми, составьте на них список карт:

z = zip([10, 20, 30, 40], [100, 200, 300, 400], [1000, 2000, 3000, 4000])
li = list(map(list, z))
# [[10, 100, 1000], [20, 200, 2000], [30, 300, 3000], [40, 400, 4000]]

Чтобы транспонировать матрицу, используйте zip(*matrix):

def transpose(matrix):
    return list(map(list, zip(*matrix)))

transpose(l)
# [[10, 20, 30, 40], [100, 200, 300, 400], [1000, 2000, 3000, 4000]]

Вы также можете отсортировать список питонов li используя li.sort(), или сортируйте любой итератор (списки являются итераторами), используя sorted(li).

Здесь я бы использовал (проверено):

sorted(zip(unixdate, price))