Как сортировать, используя метод подкачки во встроенной Python вместо ai, aj = aj, ai

Question

У меня есть объект, который нужно отсортировать, но хотя у него есть индексы с сортируемыми свойствами, это не list. Вместо этого у него есть метод swap. Есть ли способ отсортировать его?

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

То есть большинство (все?) алгоритмов сортировки имеют в себе строку подкачки, которая выглядит следующим образом:

my_list[i], my_list[j] = my_list[j], my_list[i]

, и я хотел бы получить набор всех (i,j) пар.

Я бы предпочел не реализовывать сортировку самостоятельно.

ОБНОВЛЕНИЕ: используя реализацию быстрой сортировки, которую я нашел , я получил кое-что, что работает:

def partition(array, begin, end):
    pivot = begin
    for i in range(begin+1, end+1):
        if array[i] <= array[begin]:
            pivot += 1
            #array[i], array[pivot] = array[pivot], array[i]
            array.swap(i, pivot)
    #array[pivot], array[begin] = array[begin], array[pivot]
    array.swap(pivot, begin)
    return pivot

def quicksort(array, begin=0, end=None):
    if end is None:
        end = len(array) - 1
    def _quicksort(array, begin, end):
        if begin >= end:
            return
        pivot = partition(array, begin, end)
        _quicksort(array, begin, pivot-1)
        _quicksort(array, pivot+1, end)
    return _quicksort(array, begin, end)


class SwapSorter(list):
    def __init__(self, array, obj):
        super().__init__(array)
        self._obj = obj

    def swap(self, i, j):
        if i == j: return
        print("swapping:",i,j)
        self[i], self[j] = self[j], self[i]
        self._obj.swap(i,j)


ss = SwapSorter(array, obj)
quicksort(ss)

print("sorted:")
print(ss)
print(ss._obj)

но (я думаю) я хотел бы просто использовать встроенную сортировку вместо своей собственной ... или это просто обычная практика для прокрутки собственной сортировки?

Answer 1

Фактический ответ

Звучит так, будто вы делаете хорошо, но мне стало любопытно, и я пришел к ответу в духе того, о чем вы спрашиваете. В следующих разделах вы найдете информацию о мотивации и о том, как она работает, но сразу перейдете к поиску:

def sort_with_swap(mylist):
    # Source locations of items (satifies: source_index = source_indices[dest_index])
    source_indices = sorted(range(len(mylist)), key=lambda i: mylist[i])

    # Destination locations of items (satisfies: dest_index = destination_indices[source_index])
    destination_indices = [None] * len(source_indices)
    for dest_index, source_index in enumerate(source_indices):
        destination_indices[source_index] = dest_index

    # Perform the swaps
    for dest_index, source_index in enumerate(source_indices):
        # Nothing to do if src==dest (although code below actually works if you remove this)
        if source_index == dest_index:
            continue

        # Swap the source item into the correct destination
        mylist.swap(source_index, dest_index)

        # Update the index lists for the new location of the item that had been in the destination
        old_dest_at_dest_index = destination_indices[dest_index]
        source_indices[old_dest_at_dest_index] = source_index
        destination_indices[source_index] = old_dest_at_dest_index

        # These two updates are not necessary but leave index lists in correct state at the end
        # source_indices[dest_index] = dest_index
        # destination_indices[dest_index] = dest_index

Тестирование

Вы можете попробовать эту функцию следующим образом:

class SwappableList(list):
    def swap(self, i, j):
        self[i], self[j] = self[j], self[i]

s = SwappableList("bcdefahg")
print(f"before: {''.join(s)}") # prints "before: bcdefahg"
sort_with_swap(s)
print(f"after:  {''.join(s)}") # prints "after:  abcdefgh"

Мотивация

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

1. Это менее хакерски, потому что для отслеживания того, что происходит, когда происходит, вам нужно подождать два задания, проверить, действительно ли они поменялись, и затем прошить их обратно. вместе.
2. Это не сломается, если реализация сортировки делает что-то отличное от перестановок, например, перестановка трех элементов или удержание элемента сводки в отдельном месте.
3. Уменьшает число перестановок в вашей структуре, подобной списку, которая, судя по звукам, может быть дорогой.

Как это работает

Вот первая наивная попытка моей идеи:

# Warning: doesn't work
def sort_with_swap_naive(mylist):
    source_indices = sorted(range(len(mylist)), key=lambda i: mylist[i])
    for dest_index, source_index in enumerate(source_indices):
        mylist.swap(source_index, dest_index)

Все довольно просто:

1. Мы сортируем список индексов вместо исходного списка. Например, для list('bcdefahg') вы получаете [5, 0, 1, 2, 3, 4, 7, 6].
2. Мы go просматриваем этот список индексов и меняем каждый из пунктов на свои места.

К сожалению, эта простая версия не работает. Для начала, если вы проследите за перестановками последних двух элементов ('g' и 'h'), вы обнаружите, что мы поменяем их в правильных местах и ​​сразу же поменяем их обратно! Проблема более сложна для переставленной части списка, но основная проблема та же…

Проблема заключается в следующем: мы используем off source_indices, чтобы определить, какие элементы нужно поменять местами, но так как мы go через список выходит из-под контроля c. Чтобы решить эту проблему, нам также необходимо обновить это, как мы делаем свопы. Оказывается, чтобы сделать это эффективно, нам нужен список, содержащий противоположное отображение, то есть список индексов назначения. Чтобы увидеть, что нужно обновить, вот оригинальный список до и после замены элементов 0 и 5:

mylist = ['b', 'c', 'd', 'e', 'f', 'a', 'h', 'g']
sources = [5, 0, 1, 2, 3, 4, 7, 6]
destinations = [1, 2, 3, 4, 5, 0, 7, 6]

# Swap item at 0 with item at 5
mylist = ['a', 'c', 'd', 'e', 'f', 'b', 'h', 'g']
# updates:      ^                   ^
sources = [0, 5, 1, 2, 3, 4, 7, 6]
# updates: ^  ^
destinations = [0, 2, 3, 4, 5, 1, 7, 6]
# updates:      ^              ^

Как видите (возможно!), Ключевым моментом для обновления является элемент, который был в индексе назначения (то есть 'b', который был в 0) непосредственно перед свопом.