Сортировка списка кортежей с использованием сортировки слиянием? - PullRequest
Новая
       6

Сортировка списка кортежей с использованием сортировки слиянием?

0 голосов
/ 03 марта 2020

Я пытаюсь отсортировать этот список кортежей после числа во втором индексе, используя алгоритм сортировки слиянием, но я очень не уверен, как это сделать.

Это список кортежей, которые я пытаясь отсортировать: 

list_of_tuples = [('Birds of Prey', 97.1),
                  ('Dolittle', 175.0),
                  ('The Gentlemen', 7.0),
                  ('Falling', 22.0)]

И я могу реализовать общий алгоритм сортировки слиянием, но я не могу сделать это так, чтобы сортировать после числа в кортеже по второму индексу.

Это моя реализация общей сортировки слиянием: 

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

    return arr

Как бы я справился с этой задачей?

Предпочтительный ответ состоит в том, что он возвращает кортеж с наибольшим числом в конец, поэтому результат будет ('Dolittle', 175.0).

1 Ответ

0 голосов
/ 03 марта 2020

Вы можете следить за реализацией сортировки Python и добавить аргумент key: 

def merge_sort(arr, key=lambda x: x):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    merge_sort(left)
    merge_sort(right)

    i = j = k = 0
    while i < len(left) and j < len(right):
        if key(left[i]) < key(right[j]):
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1

    return arr

, тогда все, что вам нужно сделать, это: res = merge_sort(list_of_tuples, key=lambda x: x[1])

Или с реализацией сортировки python: res = sorted(list_of_tuples, key=lambda x: x[1])

...