Как работает сортировка вставки Python?

Ответ 1

Или это:

def ins_sort(k):
    for i in range(1,len(k)):    #since we want to swap an item with previous one, we start from 1
        j = i                    #bcoz reducing i directly will mess our for loop, so we reduce its copy j instead
        temp = k[j]              #temp will be used for comparison with previous items, and sent to the place it belongs
        while j > 0 and temp < k[j-1]: #j>0 bcoz no point going till k[0] since there is no seat available on its left, for temp
            k[j] = k[j-1] #Move the bigger item 1 step right to make room for temp
            j=j-1 #take k[j] all the way left to the place where it has a smaller/no value to its left.
        k[j] = temp
    return k

Ответ 2

Рассмотрим [3, 2, 1]

Цикл начинается с 3. Поскольку это первый элемент в списке, нечего делать.

[3, 2, 1]

Следующий элемент - 2. Он сравнивает от 2 до 3 и, поскольку 2 меньше 3, он меняет их, сначала помещая 3 во второе положение, а затем помещая 2 в первую позицию.

[2, 3, 1]

Последний элемент равен 1. Так как 1 меньше 3, он перемещается на 3.

[2, 3, 3]

Так как 1 меньше 2, то свопы перемещаются на 2.

[2, 2, 3]

Затем он вставляет 1 в начале.

[1, 2, 3]

Ответ 3

Чтобы увидеть, как работает эта реализация, просмотрите ее здесь: http://goo.gl/piDCnm

Однако здесь менее сложная реализация сортировки вставки:

def insertion_sort(seq):
    for i in range(1, len(seq)):
        j = i
        while j > 0 and seq[j - 1] > seq[j]:
            seq[j - 1], seq[j] = seq[j], seq[j - 1]
            j -= 1

Ответ 4

рекурсивная реализация

def insert(x, L):
    if [] == L:      return [x]
    elif x <= L[0]:  return [x] + L
    else:            return [L[0]] + insert(x,L[1:])

def insertion_sort(L):
    if [] == L:  return []
    else:        return insert(L[0], insertion_sort(L[1:]))

# test
import random

L = [random.randint(1,50) for _ in range(10)]

print L
print insertion_sort(L)

Ответ 5

Если мы рассмотрим массив слева направо [LeftMost,..., RightMost], сортировка вставки выполняет следующую процедуру для каждого элемента:

• Получить текущее значение i.
• Получить значение j (где j = i-1 в первой итерации или в основном первый элемент слева от i). В первой итерации массива while [i] и array [j] находятся последовательные элементы. Например, если array = [... 60, 100, 50,...] и array [i] равно 50, тогда массив [j] равен 100.
• Если предыдущее значение больше текущего, то оно меняет местами два значения. В основном, если у вас есть что-то вроде [..., 60, 100, 50,...] до этой операции, вы получите [..., 60, 50, 100,...]. Идея состоит в том, что вы перемещаете каждый элемент, который я оставил, пока есть элементы слева от него, которые ниже.

  Это ключ алгоритма сортировки. После того, как вы закончите обработку в элементе i, у вас есть отсортированный массив, из которого он первоначально был полностью в начале (осталось больше всего).

• Уменьшите значение j на единицу. и вернемся к шагу 1 (В этом примере это приведет к тому, что вы сравните 50 и 60 и замените их).

Sidenote (не важно понимать алгоритм, но может быть полезно): имея в виду, вы можете сделать вывод, что эта сложность алгоритма (измеренная в худшем случае сравнения) равна O (N ^ 2), где N = len (s). Это похоже на наличие двух вложенных операторов.

Это видео отлично справляется с этим, и вы знаете, что говорят, изображение стоит 1000 слов.

Ответ 6

Есть несколько кусочков информации, которые помогут разобраться в сортировке вставок.

Прежде всего, i никогда не становлюсь больше, чем len(s). На самом деле, это никогда не равно ему. range(1, len(s)) создает неизменяемую последовательность, по которой вы можете выполнять итерации. Что вы будете иметь под следующим утверждением (предположим, что len(s) = 3):

for i in range(1, len(s)):
    ...

это что-то вроде этого:

for i in (1, 2):
    ...

Вы можете убедиться в этом сами:

>>> list(range(1, 3))
>>> [1, 2]

Таким образом, вы будете повторять два раза, первый раз с i = 1, а второй раз с i = 2.

Во-вторых, это помогает напомнить себе, что сортируемый вами список состоит, по сути, из двух частей: сортируемой части (list[0:i-1]) и части, которая еще не отсортирована ([list[i:]). То, чего вы пытаетесь достичь с помощью вставки сортировки на каждой итерации, - это найти место для помещения текущего значения в отсортированный список. Мы вернемся к этому в ближайшее время.

В-третьих, алгоритм можно рассматривать как выполняющий две совершенно разные задачи. Первый - перебрать все элементы в списке и убедиться, что список отсортирован. То, чем занимается этот внешний цикл (конечно, внутренний цикл участвует в реальных проверках, но это помогает сделать это упрощение). Другой - найти подходящие позиции для элементов в списке, чтобы список был отсортирован. То есть, если у вас есть список letters = ['a', 'b', 'd', 'c'], 'c' очевидно, должен идти на letters[2] а 'd' должен занимать 'c' прежнее место если список должен быть отсортирован в порядке возрастания. То есть та часть, которая внутренние в while цикл делает.

То, как цикл while (и оператор s[j+1] = val) гарантирует, что список отсортирован, на самом деле довольно умно. Во-первых, он гарантирует, что мы не перегружены (условие j >= 0). То есть мы не s[-1] элемент s[-1], который в Python будет последним элементом в списке, и другие языки, такие как Java, исключение ArrayIndexOutOfBounds. Затем он спрашивает: номер, который я держу, ниже, чем предыдущий? Если это так, это означает, что список не отсортирован, и нам нужно переместить большее число на одну позицию ближе к концу списка (если хотите, вправо). Обратите внимание, что элемент, с которым мы сравниваем другие элементы, остается тем же. Мы держим его в переменной val. Поэтому нам не нужно беспокоиться о случайной потере, перезаписывая его при перемещении значений.

Теперь, когда мы переместим большее значение вправо, мы уменьшим j и снова зададим тот же вопрос: больше ли значение в s[j] чем то, которое мы имеем в val? Мы продолжаем делать это до тех пор, пока не найдем значение, которое ниже, чем у нас в val, или пока не достигнем s[0] не найдя более низкого значения. Это означает, что то, что у нас есть, является самым низким номером в списке. В любом случае, мы нарушаем из в while циклы и перезапись s[j+1] со значением, которое мы имеем, так что мы не обесцениваться val.

Чтобы увидеть, как это выглядит на практике, рассмотрим список: [2, 3, 4, 5, 1]. Допустим, мы повторяем, пока не достигнем числа 1, и в этот момент мы входим в цикл while, поскольку 5 > 1. Предпринятые шаги будут:

2, 3, 4, 5, 1   # val = 1, s[j] = 5, j = 3       5 > 1
2, 3, 4, 5, 5   # val = 1, s[j] = 4, j = 2       4 > 1
2, 3, 4, 4, 5   # val = 1, s[j] = 5, j = 1       3 > 1
2, 3, 3, 4, 5   # val = 1, s[j] = 5, j = 0       2 > 1
2, 2, 3, 4, 5   # val = 1, s[j] = 5, j = -1      break out of while
1, 2, 3, 4, 5   # val = 1, s[j] = 5, j = -1      put val into s[0]

И это в основном это. Выполните итерацию по циклу, убедитесь, что значения перед текущим меньше, чем то, которое мы храним, и, если нет, переместите эти значения вправо, чтобы освободить место для нашего значения. И вот оно у вас есть - сортировка вставок.

Изменение: есть очень хорошее, наглядное объяснение при просмотре кода, если вам все еще трудно понять, как он работает.

Ответ 7

def insertionsort(list):
    for i in range(1,len(list)):
        temp=list[i]
        j=i-1
        while temp<+list[j] and j>=0:
            list[j+1]=list[j]
            j=j-1
        list[j+1]=temp
    return list
list=eval(raw_input('Enter a list:'))
print insertionsort(list)

Это поможет вам.

Ответ 8

Функция python range(start, end) начинает отсчет от start до end - 1. То есть, end никогда не будет частью значений range(). Итак, если у вас есть, например, range(len(A)), а A - массив (в Python, список) из 10 целых чисел, len(A) будет 10, а range(len(A)) вернет (0,1,2,3,4,5,6,7,8,9), чтобы вы могли индексировать каждый элемент в A.

В вашем случае я никогда не становлюсь больше len(s) - 1.

После вашего кода на бумаге может быть полезно, но вы должны убедиться, что язык программирования делает именно то, что вы думаете, что он делает, а иногда реализация не интуитивно понятна. Быстрый и простой способ отслеживания ваших значений программы - использовать операторы print. Например:

def sort_numbers(s):
    for i in range(1, len(s)):

        # let see what values i takes on
        print "i = ", i

        val = s[i]
        j = i - 1
        while (j >= 0) and (s[j] > val):
            s[j+1] = s[j]
            j = j - 1
        s[j+1] = val

Ответ 9

def insertionSort(alist):
    for index in range(1, len(alist)):

        currentvalue = alist[index]
        position = index

        while position > 0 and alist[position-1] > currentvalue:
            alist[position] = alist[position-1]
            print(alist)
            position -= 1

        alist[position] = currentvalue

alist = [int(i) for i in input().split()]       
insertionSort(alist)

Ответ 10

__author__ = 'Dharmjit'  
def InsertionSort(list):  
    for index in range(1,len(list)):  
        curr = list[index]  
        position = index  

        while position > 0 and list[position-1] > curr:  
            list[position] = list[position-1]  
            position = position - 1  

        list[position] = curr  
    return list  

l = [2,1,5,3,9,6,7]  
print(InsertionSort(l))  
[1,2,3,5,6,7,9]  

Вы можете увидеть всю концепцию здесь - http://pythonplanet.blogspot.in/2015/07/sorting-algorithm-1-insertion-sort.html

Ответ 11

def insertion(x):
    for i in range(1, len(x)):
        while x[i - 1] > x[i] and i >= 0:
            x[i - 1], x[i] = x[i], x[i - 1]
            i -= 1
    return x

Что-то вроде этого

Ответ 12

Простая комбинация сортировки списка и сортировки пузырьков

s = [54,26,93,17,77,31,44,55,20]

for i in range(1,len(s)+1):
    b = s[0:i]
    a = b
    count = 0

    while count<len(a):                  # while loop to perform the for loop len(a) number of times-like in bubble sort
        for j in range(len(a)-1):        # for loop compares every j'th element with next element
            if a[j] >= a[j+1-len(a)]:
                temp = a[j]
                a[j] = a[j+1-len(a)]
                a[j+1-len(a)] = temp

        count = count+1
print a    

Ответ 13

+ Альтернатива с двумя для петель и описательных имен.

def insertionSort(list):
  for outerIndex in range(len(list)):
    for innerIndex in range(outerIndex, 0, -1):
      if list[innerIndex] >= list[innerIndex - 1]:
        break
      list[innerIndex], list[innerIndex - 1] = list[innerIndex - 1], list[innerIndex]
  return list

print insertionSort([3, 1e-10, 7e5, 2.3, 100, -2.5, 12.1])
# => [-2.5, 1e-10, 2.3, 3, 12.1, 100, 700000.0]

Ответ 14

Вставка Сортировка через рекурсию:

k=1# def insertionsort(a): # should be written before k=1
c=a[:]
def swap(k,c,a):
    if c[k-1] > c[k]:
        c[k-1] = a[k]
        c[k] = a[k-1]
        a = c[:]
        if max(c[:k])!= c[k-1]:
            swap(k-1,c,a)
    if k < len(a)-1:
       return swap(k + 1, c,a)
    return c
return swap(k,c,a)

print(insertionsort(b))

Ответ 15

Простой способ сортировки массива.

# Mutate the constant input 
# loop into the array
# check if the array[j] have to be greater than 0 and a[j] is less than a[j - 1] 
# then swap values and decrease the value swapped.

def insertionSort(array):
  a = array
  for i in range(0,len(a)):
    j = i
    while j > 0 and a[j] < a[j - 1]:
      a[j], a[j - 1] = a[j - 1], a[j]
      j -= 1
  return a

# input-> [2,1,3] then array[j] > 0 and array[j] < array[j - 1] -> swap -> decrease j

Ответ 16

Попробуйте это, работает как для увеличения, так и для уменьшения порядка:

import operator

def insertion_sort(arr, reverse=False):
    # check if array is empty or not
    if arr is None:
        raise TypeError("Data cannot be none")

    n = len(arr)
    # if length of array is less than two it is already sorted
    if n < 2:
        return arr

    lgt = operator.gt if reverse else operator.lt

    # Traverse through 1 to len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i-1
        while j >= 0 and lgt(key, arr[j]):
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = key
    return arr

li = [1, 4, 8, 9, 42, 0, 36]
print(insertion_sort(li))

Ответ 17

def ins(l):
    for i in range(1, len(l)):
        current_index = i
        current_value = l[i]
        while current_index > 0 and current_value < l[current_index - 1]:
            l[current_index] = l[current_index - 1]
            current_index -= 1
        l[current_index] = current_value
    print(l)

Ответ 18

def insertSort(list):
  for i in range(0, len(list)):
    index = list[i] // index holder for swapAt position
    while i > 0 and index < list[i - 1]:
      list[i] = list[i - 1]
      i = i - 1
      list[i] = index
  return list

print(insert([3,3,6,1,7,2,8])) -> [1, 2, 3, 3, 6, 7, 8]

Ответ 19

def sort_numbers(list):
    for i in range(1, len(list)):
        val = list[i]
        j = i - 1
        while (j >= 0) and (list[j] > val):
            list[j+1] = list[j]
            j = j - 1
        list[j+1] = val

n = int(input("Enter the no. of elements"))
list = []
for i in range(0,n):
  t = int(input())
  list.append(t)

sort_numbers(list)

print list

Ответ 20

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

def insert(L): # this creates the definition and assines the list that you input to L
    for i in range(len(L)): # this then loops the next code for the length of the list
        while i > 0 and L[i] < L[i-1]: # this is the main part of the code where it checks
        # if the value from the list is less than the one before it and if it is then it 
        # swaps them around 
            L[i-1], L[i] = L[i], L[i-1] # this code just swaps round the values
            print (L)# prints the list out at the end of each part



L = [5,2,3,7,6,9,7]
insert(L)

Используя это, он выдает:

[2, 5, 3, 7, 6, 9, 7]
[2, 3, 5, 7, 6, 9, 7]
[2, 3, 5, 6, 7, 9, 7]
[2, 3, 5, 6, 7, 7, 9]

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

[2, 3, 5, 6, 7, 7, 9]

Ответ 21

    def insertie(x):
    nrc=0
    nrm=0
    for i in range(0,len(x)):
        aux=x[i]
        nrm=nrm+1
        j=i-1
        while j >= 0 and aux < x[j]:
            nrc=nrc+1
            x[j+1]=x[j]
            nrm=nrm+1
            j=j-1
        nrc=nrc+1
        x[j+1]=aux
        nrm=nrm+1
    return x

x=[7,5,4,9,1,4,0,1]
print insertie(x)