16

これは挿入ソートの Python 実装です。紙の値をたどろうとしましたが、カウント変数 i が len(s) よりも大きくなると、何をすべきかわかりません。どのように/なぜまだ実行されますか?

def sort_numbers(s):
    for i in range(1, len(s)):
        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

def main():
    x = eval(input("Enter numbers to be sorted: "))
    x = list(x)
    sort_numbers(x)
    print(x)
4

22 に答える 22

25

または、これ：

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                    #create i's copy (or not)
        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
于 2015-02-25T19:13:40.200 に答える
11

[3、2、1] を検討してください。

ループは 3 から始まります。これはリストの最初の項目なので、他に何もすることはありません。

[3, 2, 1]

次の項目は 2 です。2 と 3 を比較し、2 は 3 より小さいため、最初に 3 を 2 番目の位置に置き、次に 2 を最初の位置に置きます。

[2, 3, 1]

最後の項目は 1 です。1 は 3 より小さいので、3 つ移動します。

[2, 3, 3]

1 は 2 より小さいので、2 回の移動を入れ替えます。

[2, 2, 3]

次に、先頭に 1 を挿入します。

[1, 2, 3]
于 2012-10-06T01:02:55.770 に答える
3

再帰的な実装

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)
于 2015-11-12T05:22:06.677 に答える
2

左から右へ [LeftMost, ..., RightMost] 配列を考えると、挿入ソートは各項目に対して次の手順を実行します。

  1. 現在の値 i を取得します。
  2. 値 j を取得します (ここで、最初の反復で j = i-1、または基本的に i の左にある最初の要素)。while array[i] と array[j] の最初の反復では、連続する要素が対象です。たとえば、array = [... 60, 100, 50, ...] で、array[i] が 50 の場合、array[j] は 100 です。
  3. 前の値が現在の値より大きい場合は、2 つの値を交換します。基本的に、この操作が行われる前に [..., 60, 100, 50, ...] のようなものがあった場合、[..., 60, 50, 100, ...] になります。アイデアは、左に低い要素がある限り、私が残した各アイテムを移動することです。

    これがソートアルゴリズムの鍵です。アイテム i での処理が完了すると、元の場所から最初 (一番左) までの並べ替えられた配列が得られます。

  4. j の値を 1 減らします。ステップ 1 に戻ります (この例では、50 と 60 を比較して交換します)。
コードを注意深く見てみると、 i >= len(s) となるポイントは得られません ( rangeはリストを作成する関数であり、値 i はループ内で変更されません)。変数 i は、並べ替えられたすべての要素が左側にある配列内の位置を指す想像上の矢印と考えることができます。変数 j は、i を固定したまま単純に左に移動し、元の array[i] 値を、それ以下の別の値が見つかるまでスワップします。

サイドノート (アルゴリズムを理解することは重要ではありませんが、役立つ可能性があります): このことを念頭に置いて、このアルゴリズムの複雑さ (最悪の場合の比較で測定) は O(N^2) であると推測できます。ただし、N = len(s) です。これは、2 つの for ステートメントを入れ子にすることに似ています。

このビデオは、上記のことをうまく説明しています。

于 2012-10-06T04:15:09.613 に答える
1 
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)

これはあなたを助けるでしょう。

于 2014-10-30T18:52:30.090 に答える
0

python関数は からまでrange(start, end)カウントを開始します。つまり、値の一部になることはありません。たとえば、とが 10 個の整数の配列 (Python ではリスト) である場合、は 10 になり、が返されるため、A のすべての要素にインデックスを付けることができます。startend - 1endrange()range(len(A))Alen(A)range(len(A))(0,1,2,3,4,5,6,7,8,9)

あなたの場合、私は より大きくなることはありませんlen(s) - 1。

紙に書かれたコードに従うことは役に立つ場合がありますが、プログラミング言語が思ったとおりに動作することを確認する必要があり、実装が直感的でない場合もあります。プログラムの値をすばやく簡単に追跡する方法は、printステートメントを使用することです。例えば：

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

        # let's 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
于 2013-03-31T18:32:44.943 に答える
0 
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)
于 2015-08-31T19:41:06.713 に答える
0

リストのスライスとバブル ソートの単純な組み合わせ 

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
于 2017-02-13T13:28:06.933 に答える
0 
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

そんな感じ

于 2016-09-25T05:39:52.223 に答える
0 
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)
于 2019-08-28T02:01:20.413 に答える
0

再帰による挿入ソート:

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))
于 2018-05-19T04:15:21.773 に答える
0

配列をソートする簡単な方法。

# 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
于 2019-03-15T14:11:03.743 に答える
-5 
    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)
于 2016-01-27T14:18:13.223 に答える