Sort array by low, medium and high

Question

I'm working on a problem to sort array by low, medium and high -- in-place tweak original array. I'm looking for advice, especially any algorithm implementation efficiency. My current bottleneck of implementation is that I have to do partition twice, by low+medium and high, then do low and medium partition on low+medium part. I'd like to do partition only once.

'''
You have an unsorted array of integers and a
function........string getCategory(integer)........
which deterministically returns 1 of three possible strings:
"low", "medium", or "high", depending on the input integer.
You need to output an array with all the "low" numbers at the bottom,
all the "medium" numbers in the middle, and all the "high" numbers at the top.
This is basically a partial sort. Within each category, the order of the numbers does not matter...
For example, you might be give the array [5,7,2,9,1,14,12,10,5,3].
For input integers 1 - 3, getCategory(integer) returns "low",
for 4 - 10 it returns "medium," and for 11 - 15 it returns "high".
You could output an array (or modify the given array) that looks like this: [3,1,2,5,5,9,7,10,14,12]
'''

def getCategory(value):
    if 1<=value<=3:
        return 'low'
    elif 4<=value<=10:
        return 'medium'
    else:
        return 'high'
def partial_sort(numbers):
    low_and_medium_index = 0
    high_index = len(numbers)-1
    while low_and_medium_index <= high_index:
        while low_and_medium_index <= high_index and \
                        getCategory(numbers[low_and_medium_index]) != 'high':
            low_and_medium_index+=1
        while low_and_medium_index <= high_index and \
                        getCategory(numbers[high_index]) == 'high':
            high_index -= 1
        if low_and_medium_index < high_index:
            numbers[low_and_medium_index], numbers[high_index] = numbers[high_index], numbers[low_and_medium_index]
        else:
            break
    low_index = 0
    medium_index = low_and_medium_index - 1
    while low_index <= medium_index:
        while low_index <= medium_index and \
                        getCategory(numbers[low_index]) == 'low':
            low_index+=1
        while low_index <= medium_index and \
                        getCategory(numbers[medium_index]) == 'medium':
            medium_index -= 1
        if low_index < medium_index:
            numbers[low_index], numbers[medium_index] = numbers[medium_index], numbers[low_index]
        else:
            break

    return numbers

if __name__ == "__main__":
    print partial_sort([5,7,2,9,1,14,12,10,5,3])

Answer 1

Unless you're very sure you can outperform CPython's list.sort() here I would recommend using it instead of custom algorithm whose implementation is hard to read.

And most likely CPython based implementation is going to be fast because we are removing pure Python loops. I can't say the same thing about other implementations, for example PyPy, you may have to time and compare them yourself.

---

Now to do this using list.sort() we will have to use its key argument, key argument is used for specifying custom comparison values.

In this we can map 'low', 'medium' and 'high' to some numbers and use those numbers for comparison. If possible you can also numbers such numbers from get_category itself to reduce one step.

def get_category(value):
    if 1 <= value <= 3:
        return 'low'
    elif 4 <= value <= 10:
        return 'medium'
    else:
        return 'high'


def partial_sort(numbers):
    category_weight = {'low': 1, 'medium': 2, 'high': 3}
    numbers.sort(key=lambda x: category_weight[get_category(x)])
    return None  # Can be omitted, but let's be explicit.

As you can see the resulting code is much short and easier to read.

---

Timing comparisons

>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**5
>>> %timeit partial_sort(data)
1 loops, best of 3: 347 ms per loop
>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**5
>>> %timeit partial_sort_op(data)
1 loops, best of 3: 435 ms per loop

>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6
>>> %timeit partial_sort(data)
1 loops, best of 3: 3.58 s per loop
>>> data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6
>>> %timeit partial_sort_op(data)
1 loops, best of 3: 4.42 s per loop

---

Notes

• Don't use camel-casing for function and variable names, in Python underscores are preferred.
• Your code should be PEP-8 compliant to make it much more readable.
• Read more about sorting in Python: Sorting Mini-HOW TO
• If you're modifying the array in-place then it is recommended to return None instead of the array. It makes it consistent with other in-place operations we have in Python like list.append(), list.extend(), dict.update() etc. Else use sorted() with same key to get a new list and return it from your function, but creating a new list is expensive.

Answer 2

Your input values are defined. In this case You can make a weight map list:

def partial_sort_3(numbers):
    category_weights = [-1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3]
    numbers.sort(key=lambda x: category_weights[x])

Instead of creating weight for every for every numbers, You have predefined list with all weight.

Why -1 is a first value in category_weights? Because Your values are 1-15 and You must create a value for 0.

Why not category_weights = [1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3] and check category_weights[x - 1]? Because it's a little bit slower.

And finally comparison to @AshwiniChaudhary solution:

>>> timeit.timeit('partial_sort(data)', 'data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6', globals={'partial_sort': partial_sort}, number=1)
>>> 4.691216389997862

>>> timeit.timeit('partial_sort(data)', 'data = [5, 7, 2, 9, 1, 14, 12, 10, 5, 3] * 10**6', globals={'partial_sort': partial_sort_3}, number=1)
>>> 2.725900844001444