Блог

Главная - Вопросы по программированию - Быстрая сортировка по разным значениям

Быстрая сортировка по разным значениям

#python-3.x #algorithm #sorting #quicksort

Вопрос:

Привет! У меня есть список списков, подобных этому:

 list_ = [["a", 1],
    ["b", 3],
    ["c", 2],
    ["d", 2]]

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

 def partition(a, low, high):
    i = low - 1
    pivot = a[high][1]
        
    for j in range(low, high):
        
        if a[j][1] >= pivot:
            i  = 1
            a[i], a[j] = a[j], a[i]

def quicksort_inplace(a, low=0, high=None):
    if high is None:
        high = len(a) - 1
    if low < high:
        p_idx = partition(a, low, high)
        quicksort_inplace(a, low, p_idx - 1)
        quicksort_inplace(a, p_idx   1, high)
    
    return a

Проблема. Я понимаю, как сортировать по одному элементу за раз, но я не понимаю, как сортировать свой список так, чтобы при наличии одинаковых элементов сортировка происходила в алфавитном порядке (по первому элементу).

в:

 [
    ["a", 1],
    ["b", 3],
    ["c", 2],
    ["d", 2]
]

из:

 [
    ["b", 3],
    ["d", 2]
    ["c", 2],
    ["a", 1],
]

Комментарии:

1. Когда a[j][1] == pivot вы не хотите помещать все элементы в одну и ту же часть раздела. Вместо этого разделите их на первый элемент списка.

2. В вашем примере также показан обратный порядок сортировки по алфавиту для первого элемента. Это ваш желаемый результат или неверный вывод, который выдает ваш текущий алгоритм?

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

Ответ №1:

Вы можете просто адаптировать свое сводное значение и функцию сравнения для выполнения любой логики, которую вы хотите, но, как это чаще всего бывает, вы хотите выполнить «лексиографический» порядок. К счастью, python уже реализует эту логику для вас со списками и кортежами, сравнивая первые элементы и, если они равны, переходите к следующему, прежде чем определить, какой из них больше.

Просто используя

 pivot = a[high]
...
if a[j] < pivot:

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

Проще всего просто создать такой key , по которому можно будет сортировать.

 pivot = (-a[high][1], a[high][0]) # reversed number first, then ordinary letter.
...
if (-a[j][1], a[j][0]) < pivot:

Конечно, мы можем использовать их и key в обычных процедурах сортировки

 sorted(list_, key=lambda x: (-x[1], x[0]))
list_.sort(key=lambda x: (-x[1], x[0]))
Метки: