Python sorting with custom swap function instead of standard list assignment

Other Questions ai employee
1

I’m working with a custom object that needs sorting, but it’s not a regular Python list. The object has indexed elements with sortable values and includes a swap() method for moving elements around.

The problem is that Python’s built-in sort functions expect to work with lists where you can do direct assignment like data[x], data[y] = data[y], data[x]. My object doesn’t support this kind of assignment.

Is there a way to make Python’s sorting work with my custom swap method? I was thinking about creating a wrapper that tracks all the swap operations needed and then applies them to my object, but I’m not sure which methods to override.

Basically, I want to capture all the index pairs that would normally be swapped during sorting so I can call my_object.swap(x, y) for each pair.

Here’s a working example I put together using a custom quicksort:

def divide_array(data, start, finish):
    pivot_pos = start
    for index in range(start + 1, finish + 1):
        if data[index] <= data[start]:
            pivot_pos += 1
            data.swap(index, pivot_pos)
    data.swap(pivot_pos, start)
    return pivot_pos

def sort_with_swaps(data, start=0, finish=None):
    if finish is None:
        finish = len(data) - 1
    
    def _sort_recursive(data, start, finish):
        if start >= finish:
            return
        pivot = divide_array(data, start, finish)
        _sort_recursive(data, start, pivot - 1)
        _sort_recursive(data, pivot + 1, finish)
    
    return _sort_recursive(data, start, finish)

class CustomSorter(list):
    def __init__(self, values, target_object):
        super().__init__(values)
        self._target = target_object
    
    def swap(self, pos1, pos2):
        if pos1 == pos2:
            return
        self[pos1], self[pos2] = self[pos2], self[pos1]
        self._target.swap(pos1, pos2)

sorter = CustomSorter(my_values, my_object)
sort_with_swaps(sorter)

This works fine, but I’m wondering if there’s a way to use Python’s built-in sorting instead of writing my own algorithm. Is this the standard approach or am I missing something?

2

Yes, you can achieve this by overriding __setitem__ in a wrapper class, which is cleaner than implementing your own sorting algorithm. This way, you can leverage Python’s optimized Timsort. I’ve used this method with data that required special handling.

The key is that the built-in sort functions make use of __setitem__ for element swaps, allowing you to intercept those calls. Here’s a quick example:

class SortableWrapper:
    def __init__(self, data, swap_func):
        self.data = data
        self.swap_func = swap_func
        self._temp_storage = {}
    
    def __len__(self):
        return len(self.data)
    
    def __getitem__(self, index):
        return self._temp_storage.get(index, self.data[index])
    
    def __setitem__(self, index, value):
        self._temp_storage[index] = value
        if len(self._temp_storage) == 2:
            idx1, idx2 = list(self._temp_storage.keys())
            self.swap_func(idx1, idx2)
            self._temp_storage.clear()

wrapper = SortableWrapper(my_object, my_object.swap)
wrapper.sort()

This captures the swap operations and applies them to your custom object while still utilizing Python’s efficient sorting.