Не работает алгоритм сортировки выбором

Question

def selectionSort(sequence):
    print(sequence)
    min_number = sequence[0]
    index_of_min_num = 0 
    p = 0
    mistakes = 1
    while p != len(sequence)-1 :
        mistakes = 0
        min_number = sequence[p]
        index_of_min_num = p
        for i in sequence[p:]:
            if i < min_number:
                min_number = i
                index_of_min_num = sequence.index(i)
                mistakes += 1

        sequence[index_of_min_num] = sequence[p]
        sequence[p] = min_number
        p += 1

    return sequence

print(selectionSort([81, 84, 57, 20, 49, 18, 9, 13, 96, 49]))

Если дать в фу-ю выборку без повторяющихся чисел, то все сортирует нормально, но если есть два одинаковые числа, то их она не сортирует (выносит на конец или еще на какие-то места в массиве). не могли бы вы объяснить почему такое происходит и как исправить? пожалуйста

Answer 1

Вот рабочий вариант:

N = int(input())
a = [int(i) for i in input().split()]
k = 0

for i in range(N):
    k = i - 1
    num = a[i]

    while a[k] > num and k >= 0:
        a[k + 1], a[k] = a[k], a[k + 1]
        k -= 1

print(*a)

Удивительно, но на Википедии алгоритм на питоне неверный, как заметил и объяснил участник @MBo, поэтому вот другой:

size = int(input())
a = [int(i) for i in input().split()]

for idx_i in range(size - 1):
  min_idx = idx_i

  for idx_j in range(idx_i + 1, size):
    if a[idx_j] < a[min_idx]:
      min_idx = idx_j

  if min_idx != idx_i:
    a[idx_i], a[min_idx] = a[min_idx], a[idx_i]

print(*a)

Answer 2

а откуда вы взяли этот алгоритм ? в книге грокаем алгоритмы есть вполне рабочий:

def findSmallest(arr):
    smallest = arr[0]
    smallest_index = 0
    for i in range(1, len(arr)):
        if arr[i] < smallest:
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr):
    newArr = []
    for i in range(len(arr)):
        smallest = findSmallest(arr)
        newArr.append(arr.pop(smallest))
    return newArr
print (selectionSort( [81, 84, 57, 20, 9, 49, 18, 9, 13, 96, 49] ))

Answer 3

def selectionSort(sequence):
    start_sequence_len = len(sequence)
    correct_sequence = []
    p = 0

    while p != start_sequence_len:
        min_number = sequence[0]
        index_of_min_num = 0
        for i in sequence:
            if i <= min_number:
                min_number = i
                index_of_min_num = sequence.index(i)

        correct_sequence.append(min_number)
        sequence[index_of_min_num] = sequence[0]
        if p != start_sequence_len:
            del sequence[0]
        p += 1

    return correct_sequence

ВСЕ РЕШИЛ, ВСЕМ СПАСИБО ЗА ПОМОЩЬ

Answer 4

def selection(data):
    for i, e in enumerate(data):
        mn = min(range(i, len(data)), key=data.__getitem__)
        data[i], data[mn] = data[mn], e
    return data

print(selection([81, 84, 57, 20, 9, 49, 18, 9, 13, 96, 49]))

БЛОГ НА HUSL

Не работает алгоритм сортировки выбором

Ответы (4 шт):