Выбор сортировки с обоих концов с минимальным и максимальным Python - PullRequest
Новая
       47

Выбор сортировки с обоих концов с минимальным и максимальным Python

0 голосов
/ 15 апреля 2019

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

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

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]

1 Ответ

0 голосов
/ 15 апреля 2019

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

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)
...