Linear Sorting of Lists with 2 Elements

Question

This is my first question here so I accept any/all tips in case my question is not properly worded.

First off, the problem:

Say we have the following array A = [(1,'cat'), (1,'dog'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]

I need to use an algorithm that will sort this list based on the first element of each component (meaning the number). It is specifically mentioned that it does not have to be a stable algorithm (I guess meaning that we do not need to consider the sorting of the words after the number, just the 0s being before all the 1s)

I should also mention that I do not wish to employ the strategies of creating side-arrays that I will populate with the results as the algorithm sorts them. The requirement is for the algorithm to sort the array within the same array.

The code I have devised is the following:

def SwapAround(A, start, end):
start_pos = start

for i in range(start,end):
    if A[i] < A[end]:
        A[i], A[start_pos] = A[start_pos], A[i]
        start_pos = start_pos + 1
A[start_pos], A[end] = A[end], A[start_pos]

return start_pos


A=[(1,'cat'),(0,'dog'),(1,'kangaroo'),(0,'mule'),(1,'giraffe'),(1,'dog'), 
(0,'bat')]
SwapAround(A,0,len(A) - 1)
print(A)

I am having rather peculiar issues with it, although I am pretty confident that it should be working (at least walking down the code line by line it made good sense to me).

The code sorts the list, but not completely... for example, my most recent output was:

[(0, 'bat'), (0, 'dog'), (1, 'kangaroo'), (0, 'mule'), (1, 'giraffe'), (1, 'dog'), (1, 'cat')]

With a smaller list, it has actually worked, and I was dumbfounded to wake up this morning to add a couple more components to my list and it not working.

Could you possibly tell me if you can see something readily "wrong" that I should consider, and the rationale behind that so that I may fully comprehend it.

Second Question: If I wanted to add components to my list that had the number 2 as well (meaning my algorithm would have to sort between 0,1,2 instead of just 0 and 1) would you use a completely different algorithm or should swapping still work? My initial thought was that Swapping would not work properly (and it hasn't with this algorithm) and maybe a CountingSort or RadixSort would work better, so your input would be very much appreciated.

Answer 1

Your algorithm is conceptually wrong, though it's already close to the solution.

The important problem with your algorithm is that only the first element to swap will ever change. Instead you need to move both the index of the last and first element.

def sort_binary_key(arr):
    l, u = 0, len(arr) - 1

    while l < u:
        if arr[l] == 1 and arr[u] == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif arr[l] == 1:
            u -= 1
        elif arr[u] == 0:
            l += 1
        else:
            u -= 1
            l += 1

For the second part of the question:
Yes, it's possible. Run the above algorithm twice. In the first run, move all elements with 0 to the lower part of the array, all other elements to the upper. Afterwards run the same algorithm over the second part of the array, sorting between elements with 1 and 2 as first tuple-member.

def sort_binary_key(arr, l, u, key_mapper):
    while l < u:
        al, au = key_mapper(arr[l]), key_mapper(arr[u])

        if al == 1 and au == 0:
            arr[l], arr[u] = arr[u], arr[l]
        elif al == 1:
            u -= 1
        elif au == 0:
            l += 1
        else:
            u -= 1
            l += 1

    return l

def sort_ternary(arr):
    tmp = sort_binary_key(arr, 0, len(arr) - 1, lambda t: 0 if t == 0 else 1)
    sort_binary_key(arr, tmp, len(arr) - 1, lambda t: 0 if t == 1 else 1)

Note that the above code is only intended as a demonstration. This code works with lists of integers instead of the input provided by OP.

Answer 2

Your algorithm could not work from a much deeper level. You running an O(n) complexity general sorting algorithm. There is no algorithm for general sorting with that average complexity (if you find one, let me know!). Check this table of complexities of different sorting algorithms.

If your scenario is only with 0 and 1, and you want all the 0 at the start and 1 at the end (unstable), then it could be done with O(n) (Check Paul's Answer to see how) and your algorithm is utterly different.

---

You can use python list sort and just pass the key:

A = [(1,'cat'), (1,'dog'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(A, key=lambda x: x[0])
>>> [(0, 'giraffe'), (0, 'cheetah'), (1, 'cat'), (1, 'dog'), (1, 'elephant')]

You can also make it consider secondary key (first name and secondly a number):

B = [(1,'cat'), (0,'cat'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(B, key=lambda x: (x[1], x[0]))
>>> [(0, 'cat'), (1, 'cat'), (0, 'cheetah'), (1, 'elephant'), (0, 'giraffe')]

Python has a default sorting and in your case, you could simply write:

C = [(1,'cat'), (0,'cat'), (0,'giraffe'), (0,'cheetah'),(1,'elephant')]
sorted(C)
>>> [(0, 'cat'), (1, 'cat'), (0, 'cheetah'), (1, 'elephant'), (0, 'giraffe')]