How to build a sorting algorithm with 2 keys in Python?-CodePudding

I'm aware that Python has a very nice function sorted() for this but I'd like to implement my own function to understand the logic. I have a list of strings and I'd like to sort them first by length, then alphabetically. For example, Input: ['daring','adequate','bold','bait','cold','beautiful'] Output: ['bait','bold','cold','daring','adequate','beautiful'] How do I build a function that does this?

I started with building a simple quicksort function for sorting only alphabetically, but now I can't think of a efficient way of progressing from it to include 2 keys at once. Here is the code: (assumes strings are all in one case)

def quick_sort(sequence):
    length = len(sequence)
    if length <=1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if item >pivot:
            items_greater.append(item)

        else:
            items_lower.append(item)

    return quick_sort(items_lower)   [pivot]   quick_sort(items_greater)
print(quick_sort(['daring','adequate','bold','bait','cold','beautiful']))

TLDR: How to turn this into a Length/Alphebetical sort? Thanks

CodePudding user response：

You can do this by adding a 'key function' that maps an item into a tuple (item_length, item) prior with pivot in your algorithm. For example:

def quick_sort(sequence, key_fn):
    length = len(sequence)
    if length <=1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if key_fn(item) > key_fn(pivot):
            items_greater.append(item)

        else:
            items_lower.append(item)


    return quick_sort(items_lower, key_fn)   [pivot]   quick_sort(items_greater, key_fn)


print(quick_sort(['daring','adequate','bold','bait','cold','beautiful'], lambda e: (len(e),e)))

will return

['bait', 'bold', 'cold', 'daring', 'adequate', 'beautiful']

CodePudding user response：

You can implement a compare function that compares any two values in the way you define it.

def compare(a, b):
    if len(a) != len(b):
        return len(a) > len(b)
    else:
        return a > b


def quick_sort(sequence):
    length = len(sequence)
    if length <= 1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if compare(item, pivot):
            items_greater.append(item)

        else:
            items_lower.append(item)

    return quick_sort(items_lower)   [pivot]   quick_sort(items_greater)


print(quick_sort(['daring', 'adequate', 'bold', 'bait', 'cold', 'beautiful']))

this will print

['bait', 'bold', 'cold', 'daring', 'adequate', 'beautiful']

CodePudding user response：

This is how you can write it into your quicksort function assuming that you only care about the alphabetical order based on the first letter of each word.

def quick_sort(sequence):
    length = len(sequence)
    if length <=1:
        return sequence
    else:
        pivot = sequence.pop()

    items_greater = []
    items_lower = []

    for item in sequence:
        if item[0] > pivot[0]:
            if item[0] == pivot[0]:
                if len(item) > pivot:
                    items_greater.append(item)
                else:
                    items_lower.append(item)
            items_greater.append(item)

        else:
            items_lower.append(item)

    return quick_sort(items_lower)   [pivot]   quick_sort(items_greater)
print(quick_sort(['daring','adequate','bold','bait','cold','beautiful']))

returns

['adequate', 'bold', 'bait', 'beautiful', 'cold', 'daring']