2
\$\begingroup\$

I had to relax a bit, so I wrote this sorting algorithm. By any means it isn't fast, but I really started to get interested in it, since I haven't seen similar approach yet.

Disclaimer

I do not intend to make something revolutionary, but rather find another possible way to sort numbers, this algorithm was made due to my heavy insomnia when I had to relax my brain and I don't want people to comment to use Python native sorting algorithms. Of course these are much more elegant and efficient, I'm just curious about things, see the Questions section for that.

How it works:

The algorithm works as following:

  1. Finding pairs of numbers in incorrect order - any two numbers that are next to each other, are not a member of other pair and are not in correct order are grouped together and the pair gets computed value of an average of the two numbers. If numbers are in correct order, they are treated as a single number into the next step.
  2. Checking the order of the newly simplified array - If such an array has all numbers in correct order and it consists only of the original numbers, the array is sorted, otherwise it gets to step 3
  3. Unpacking pairs - any pair in the array is unpacked in correct order, so if a pair was previously packed as [63, 48], it gets automatically unpacked back into the array as [..., 48, 63, ...] Then the algorithm gets back to step 2

The code [Python]

import random 


class ValueNode: #ValueNode object storing single number or a pair of values
def __init__(self, numL=None, numR=None, num=None):
    if num is None: #Initializing a pair of values
        self.numL = numL
        self.numR = numR
        self.valL = numL.value if isinstance(numL, ValueNode) else numL
        self.valR = numR.value if isinstance(numR, ValueNode) else numR
        self.value = (self.valL + self.valR) / 2
        self.isPair = True
    else: #Initializing a single value
        self.num = num
        self.value = num.value if isinstance(num, ValueNode) else num
        self.isPair = False

def __str__(self):
    if self.isPair:
        return f"({str(self.numL)}|{str(self.numR)})->{self.value}"
    else:
        return f"{(str(self.num) + '->') if isinstance(self.num, ValueNode) else ''}{self.value}"

def __gt__(self, otherValue): #gt implementation for comparison of the value of ValueNode
    return self.value > otherValue.value

def unpack(self): #Unpack logic, either returning the pair of numbers in correct order or a single number
    if self.isPair:
        return [self.numL, self.numR] if self.numR > self.numL else [self.numR, self.numL]
    else:
        return [self.num]


def solve(arr): #Algorithm implementation using array as stack
stack = [arr]
sizes = []

while stack:
    current_arr = stack.pop()
    sizes.append(len(current_arr))

    if isSorted(current_arr):
        if isComplete(current_arr):

            return current_arr
        else:
            unpackedArray = []
            for i in current_arr:
                unpackedArray += i.unpack()
            stack.append(unpackedArray)
    else:
        newArray = []
        counter = 0
        while counter <= (len(current_arr) - 1):
            if counter < (len(current_arr) - 1) and current_arr[counter] > current_arr[counter + 1]:
                newArray.append(ValueNode(numL=current_arr[counter], numR=current_arr[counter + 1]))
                counter += 1
            else:
                newArray.append(ValueNode(num=current_arr[counter]))
            counter += 1
        stack.append(newArray)


def isSorted(arr): #Function to check whether the array is sorted
for i in range(len(arr) - 1):
    if arr[i] > arr[i + 1]:
        return False
return True


def isComplete(arr): #Function to check whether the array contains all the original numbers 
for i in arr:
    if i.isPair:
        return False
return True

#Generating random array of numbers, converting each of them to ValueNode and sorting them using Pair Average Sorting algorithm
unsorted_numbers = [ValueNode(num=i) for i in [random.randint(0, 10000000) for _ in range(100)]]
for i in solve(unsorted_numbers):
     print(i)

Size of arrays through the run

Here is an interesting chart of the size of the arrays, it starts with the initial array of size 1000 in this case and then it starts to merge and average the numbers. You can notice a repetitive pattern that is probably also recursive. Chart of arrays sizes

My questions:

  1. Does this sorting algorithm make any sense from the perspective of sorting algorithms in general?

  2. Could the algorithm possibly be optimized for better performance? I'm really interested if the optimization would lead to a better solution, although I mostly bet on it becoming one of the standard algorithm.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

naming convention

        self.numL = numL
        self.numR = numR
        self.valL = ...

PEP-8 asks that you spell these num_l, val_l, new_array, and so on.

(Also, somehow your defs wound up exdented and in the left margin, but that must be a stackexchange copy-n-paste issue.)

duck defaulting

        ... = numL.value if isinstance(numL, ValueNode) else numL

This reads vaguely like java code, rather than duck-typed python code. Consider using getattr() to simplify it:

        ... = getattr(numL, 'value', numL)

Also, if you're going to mess around with same variable having different types, it would be a kindness to the Gentle Reader to throw in some type annotations, including | Union types, so we know what to expect. The machine doesn't care, but we do.

ctor defines all attributes

A class invariant is a pretty important aspect of a defined class, and "the set of object attributes" typically will be a stable invariant of constant size, always the same attributes.

Your constructor always defines

        self.value: float = ...
        self.isPair: bool = ...

In the False case we also define self.num.

OTOH in the True case we instead define

        self.numL = ...
        self.numR = ...
        self.valL = ...
        self.valR = ...

One can certainly do this. The machine doesn't care. But a maintenance engineer will. You should minimally write some comments that motivate this design decision.

More likely, you want to group those four attributes into a namedtuple, @dataclass, or other data structure, setting it to None in the False case. By convention a pythonista will typically list all possible attributes in the constructor, assigning None if not yet known, as a handy list of "things to juggle in your mind" as you read the code. Not following the convention is possible, but it can lead to surprises.

total order

You define a partial order over value nodes.

    def __gt__( ...

Now, I understand that this code happens to never ask if one is less than another. But still, it's odd that you didn't throw in a @total_ordering decorator. It feels like a giant hole in the sidewalk, just waiting for some hapless maintenance engineer to fall into.

And at this point, I'm hesitant to even broach the topic of equality.

tuples for things that aren't lists

   def unpack(self):
        ...
        return [self.numL, self.numR] if ...

Prefer to return a 2-tuple here, please. This is a situation where a C coder would use a struct.

A somewhat subtle aspect of writing pythonic code is we use tuple for fixed number of items where position dictates meaning. For example, in an (x, y) point we wouldn't want to mix up the two coordinates, as they mean different things. Similarly a (name, height, weight) record should be a tuple.

In contrast, we use a list for arbitrary number of "same" thing, such as a list of student names.

When unpacking a pair, we're returning (smaller, larger) numbers, and we should not confuse the one with the other, they're not interchangeable. Different meanings are associated with each one.

re-testing same thing repeatedly

    def solve( ...
        while stack:
            ...
            if isSorted(current_arr):

Wow, that looks pretty expensive, given that it's a O(N) linear predicate.

Some sort algorithms would do a bit of bookkeeping with an index or two, keeping track of "sorted up to here", invalidating it when needed, in order to avoid the expense of repeated linear scans.

The body of solve is straightforward enough, no complaints. But it would really benefit from a few comments or asserts that explain relevant loop variants ("are we closer to finished?") and invariants ("everything in this range is definitely sorted!").

numeric conversions

unsorted_numbers = ...

This use case suggests that it would be handy to have a utility function that converts an Iterable of floats into a bunch of value nodes.

questions

  1. make sense?

Yes, sure, given that it eventually puts the inputs into proper order. I assume you have an automated test suite that compares results with what sorted() says. Given the ready availability of such an oracle, consider letting the hypothesis package torture test this algorithm for correctness.

  1. optimized?

Well, caching an index or two so we do fewer full linear scans is one idea that leapt off the page.

I didn't hear you mention whether stability is a requirement. It can make a difference to implementations, given that it's a constraint on what your algorithm is permitted to do.

You didn't mention any particular use case, so I'm going to assume you're shooting for "general sort". In which case there are some obvious edge cases to verify:

  • given the best case, already sorted input, return "quickly"
  • given mostly sorted input, return somewhat quickly
  • does perfectly reverse sorted input take "too long"?
  • does large number of duplicate values impact the sorting time? (likely not, but test it!)

All of which leads us to ask

  • Is expected running time O(N × log N) ?
  • What is a worst case input?
  • Given the averaging behavior, are some input distributions harder to sort than others?

As a separate matter, I have seen the standard library array (or equivalently, np.array) make code run 3x faster than a naïve list of numbers. How does that work? Part of it is due to being cache-friendly. For N numbers we don't need to do random reads via N 64-bit pointers.

In your case, you really do need two kinds of object. And you do lots of allocates and deallocates. Maybe two arrays, one for each of the is_pair() cases?

type stability

If I pass in a bunch of floats, I won't be disappointed, I will get ordered floats back.

If I pass in a bunch of ints, is there the risk of any being converted to the corresponding float by unpack ? Should we document such behavior? Should we just unconditionally map(float, arr) to properly set expectations?

Notice that an int can be as big as 2 ** 53, and still be properly represented by a double float. Increment by just + 1 and we will see that float(n) == n turns False.

numeric precision

Don't worry about this, but I will note in passing that there's a bigger literature on the topic of "computing a midpoint" than one might expect.

        ... = (self.valL + self.valR) / 2

You don't specify bounds on the input values, for example "less than 2 ** 52". Even if both values are int, this returns a float average, with opportunity for overflow.

Standard bit of paranoia for code that cares about such details is to compute

        assert self.valL <= self.valR
        ... = self.valL + (self.valR - self.valL) / 2

If you wrote this in C++20 you could rely on std::midpoint to avoid overflow.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.