Моя вставка сортировки Python всегда помещает второе число в начале - PullRequest
Новая
       30

Моя вставка сортировки Python всегда помещает второе число в начале

0 голосов
/ 26 мая 2019

мой код работает в основном нормально, за исключением небольшой ошибки, когда он помещает второй элемент в начало независимо от значения, например, 1,6,2,9,3,8,4,7,5,06,0,1,2,3,4,5,7,8,9

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

def InsertionSort(array):
    for i in range(len(array)):
        for j in range(len(array)):
            if array[i] <= array[j+1]:
                new = array.pop(i)
                array.insert(j+1,new)
                break
            elif array[i] > array[j+1]:
                continue
        print (array)

Ответы [ 2 ]

0 голосов
/ 26 мая 2019

Проблема в том, что вы переключаете положение второго элемента с первым, но позже не сравниваете его.

Здесь реализация, которая близка к вашей, с небольшими изменениями, чтобы позаботиться обо всех записях 

ar =[1,6,2,9,3,8,4,7,5,0]
def InsertionSort(array):
    for i in range(len(array)):
            val = array[i]
            while( i > 0 and array[i-1] > val):
                array[i] = array[i-1]
                i = i - 1
            array[i] = val
    print (array)

InsertionSort(ar)
0 голосов
/ 26 мая 2019

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

Вот пример, который просто меняет порядок элементов (а также печатает отладочную информацию по пути, чтобы вы могли точно видеть, что происходит): 

def insertionSort(my_list):
    # for every element in our array
    for index in range(1, len(my_list)):
        current = my_list[index]
        position = index

        while position > 0 and my_list[position-1] > current:
            print("Swapped {} for {}".format(my_list[position], my_list[position-1]))
            my_list[position] = my_list[position-1]
            print(my_list)
            position -= 1

        my_list[position] = current

    return my_list

my_list = [8,2,1,3,5,4]

print(insertionSort(my_list))
...