How can I write a sort method for python list

Hi,

I can write a bubble sort as a function:

def bubble_sort(x):
    n = len(x)
    for i in range(n-1, 0, -1):
        for j in range(i):
            if x[j] > x[j+1]:
                x[j], x[j+1] = x[j+1], x[j]
    return(x)
x = [9,3,6,1,7,10,0]
print(bubble_sort(x))
[0, 1, 3, 6, 7, 9, 10]

How may I rewrite it as a method so that I can get:

x = [9,3,6,1,7,10,0]
x.bubblesort()
print(x)
[0, 1, 3, 6, 7, 9, 10]

Hi John,

You can’t. Built-in types like list cannot be monkey-patched with new methods.

What you can do is keep bubble_sort as a function.

Or you can subclass list, and extend it with a new method:

class MyList(list):
    def bubble_sort(self):
        ...

L = MyList([9, 3, 6, 1, 7, 10, 0])
L.bubble_sort()

Are you aware that lists already have a sort method?

Thank you very much Steven. I am aware that there is a built-in sort method, and my question is a data structure question. I tried to modified my code accordingly and get the results.

Is it common to have a class without initialization “def init(” ? In this case, you define MyList as a class based on a list.

class MyList(list):
    def bubble_sort3(self):
        n = len(self)
        for i in range(n - 1, 0, -1):
            for j in range(i):
                if self[j] > self[j + 1]:
                    self[j], self[j + 1] = self[j + 1], self[j]

L = MyList([9, 3, 6, 1, 7, 10, 0])
L.bubble_sort3()
print('L\n')
print(L)
L
[0, 1, 3, 6, 7, 9, 10]

Yes. Not providing an __init__ just means it uses the init of the
superclass, list. That’s fine. All you’re doing is making a subclass
with one extra method - everything else comes from the superclass.

Cheers,
Cameron Simpson cs@cskk.id.au

MyList doesn’t need its own __init__ method, since it inherits one from the superclass list.

But if you inherit immutable built-in types and override the __init__,

class A(list):
    def __init__(self, *args, **kwargs):
        list.__init__(self, *args, **kwargs)

class B(tuple):
    def __init__(self, *args, **kwargs):
        tuple.__init__(self, *args, **kwargs)

class C(str):
    def __init__(self, *args, **kwargs):
        str.__init__(self, *args, **kwargs)

you will run into error messages as follows:

>>> A([1,2,3])
[1, 2, 3]
>>> B((1,2,3))
Traceback (most recent call last):...(snip)...
TypeError: object.__init__() takes exactly one argument (the instance to initialize)
>>> C("test")
Traceback (most recent call last):...(snip)...
TypeError: object.__init__() takes exactly one argument (the instance to initialize)

I don’t understand the meaning of the error message… :slight_smile:

1 Like

Thank you very much, Cameron and Steven. I was wondering if it’s possible to write merge sort by class method rather than a function? Is it appropriate to do so? Any comments on the code are welcome.

# merge function for mergesort
def merge_sorted(x, y): # assume that the two sequences are sorted
    res = []
    while x and y:
        if x[0] <= y[0]:
            res += [x[0]]
            x.pop(0)
        else:
            res += [y[0]]
            y.pop(0)
    if x:
        return res + x
    else:
        return res + y

def mergesort(x): # assume that x is an non-empty list 
    n = len(x)
    if n == 1:
        return x  
    elif n == 2:
        return [min(x), max(x)]
    else: # n == 3 or n ==4:
        first_half = x[: n//2]
        second_half = x[n//2:]
        first_half_sorted = mergesort(first_half)
        second_half_sorted = mergesort(second_half)
        return merge_sorted(first_half_sorted, second_half_sorted)

import numpy as np
listx = list(np.random.permutation(10))
print(listx)
print('\n')
print(mergesort(listx)) 

Output:

[5, 8, 6, 9, 3, 7, 2, 1, 0, 4]


[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Well, you can definitely do it with a subclass as in your own previous
example.

The difficulty with a class method (no, not a “@classmethod” class
method, I mean an “instance method” - you mean this also) is getting it
into the class you want it to work on.

The subclass approach means you need to work against instances of the
subclass. Using your MyList as an example, that works fine, but breaks
as soon as regular lists get mixed in, as they lack the method. You end
up needing to have convenient factories to convert ordinary lists into
the subclass in order to use the method. That quite possibly involves
copying the list (which is expensive) and also directly breaks the “sort
in place” aspect of your example. And it also becomes wordy and
cumbersome very quickly.

You can define a “mixin” class (a bare class with just the extra
methods) and include it in any subclasses:

class SortableMixin:
    def mergesort(self):
        ... in place merge sort ...

and easily mix that into any subclasses:

class MyList(list, SortableMixin):
    pass

class SparseList(SortableMixin):
    ... special "sparse" list implementation of a list ...

but you’re still subclassing. I do not know if you can modify a class’s
method resolution order (the __mro__ attribute). [… experiments…]
No you cannot.

Anyway, the advantage of a function is that you can apply it to any
type of object (provided the object is suitable). So your mergesort
function can be applied to a list or the a MyList or any other
collection which looks enough like a list.

So a function can often be a good way to do things, particularly since
it isn’t bound to a specific class.

Cheers,
Cameron Simpson cs@cskk.id.au

1 Like

A solution for how to inherit an immutable class:

>>> class C(str):
...     def __new__(cls, text):
...         return super().__new__(cls, text + ":overwritten")
... 
>>> C("text")
'text:overwritten'

FYI :wink:

1 Like