Сортировка выбора с обоих концов с помощью Min и Max Python

Мне нужно реализовать способ сделать сортировку выбором более эффективной, работая с обоих концов, используя минимальные и максимальные значения.

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

def selectionsort(alist):

    for i in range(len(alist)): 

        min_idx = i 
        for j in range(i+1, len(alist)): 
            if alist[min_idx] > alist[j]: 
                min_idx = j 

        temp = alist[i]
        alist[i] = alist[min_idx]
        alist[min_idx] = temp

alist = [54,26,93,17,77,31,44,55,20]
selectionsort(alist)
print(alist)

Функция должна вернуть упорядоченный список: [17, 20, 26, 31, 44, 54, 55, 77, 93]


python selection-sort
person DS_Sloth    schedule 15.04.2019    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

def selection_sort(l):
    i = 0
    j = len(l) - 1
    while i < j:
        min_idx = i
        max_idx = i
        max_val = l[i]
        for k in range(i, j+1):
            if l[min_idx] > l[k]:
                min_idx = k
            if l[max_idx] < l[k]:
                max_idx = k
                max_val = l[k]

        l[i], l[min_idx] = l[min_idx], l[i]

        # Edge-case: if we shifted the value to the maximum in the last swap
        if l[min_idx] == max_val:
            l[j], l[min_idx] = l[min_idx], l[j]
        else:
            l[j], l[max_idx] = l[max_idx], l[j]

        i += 1
        j -= 1

    return l


my_list = [54, 26, 93, 17, 77, 31, 44, 55, 20]
my_list = selection_sort(my_list)
print(my_list)
person rdas    schedule 15.04.2019
comment
Можете ли вы подробнее объяснить Edge-Case? В каком случае это будет использоваться? - person DS_Sloth; 15.04.2019