1

次のコードでは、for ループの最後で assert 関数を使用して、a[i+1] が a[i] 以上であることをテストしますが、次のエラーが発生します (以下のコードの後)。また、C ++では、次のアサートは正常に機能しているようですが、Python(次のコード)では機能していないようです...誰もが理由を知っていますか?

import random

class Sorting:
    #Precondition: An array a with values.
    #Postcondition: Array a[1...n] is sorted.
    def insertion_sort(self,a):
        #First loop invariant: Array a[1...i] is sorted.
        for j in range(1,len(a)):
            key = a[j]
            i = j-1
            #Second loop invariant: a[i] is the greatest value from a[i...j-1]
            while i >= 0 and a[i] > key:
                a[i+1] = a[i]
                i = i-1
            a[i+1] = key
            assert a[i+1] >= a[i]
        return a

    def random_array(self,size):
        b = []
        for i in range(0,size):
            b.append(random.randint(0,1000))
        return b


sort = Sorting()
print sort.insertion_sort(sort.random_array(10))

エラー:

Traceback (most recent call last):
File "C:\Users\Albaraa\Desktop\CS253\Programming 1\Insertion_Sort.py", line 27, in          <module>
  print sort.insertion_sort(sort.random_array(10))
File "C:\Users\Albaraa\Desktop\CS253\Programming 1\Insertion_Sort.py", line 16, in insertion_sort
    assert a[i+1] >= a[i]
AssertionError
4

3 に答える 3

3

あなたのコードは問題ありません。の場合、アサーションは失敗しi==-1ます。Python では、a[-1]はリストの最後の要素であるため、この場合、最初の要素 ( a[-1+1]) が最後の要素 ( ) より大きいか等しいかどうかを確認していますa[-1]

于 2012-09-10T21:14:40.423 に答える
0

を挿入する場所をよく見てくださいkey

于 2012-09-10T21:13:18.543 に答える
0

これはどう:

import random

class Sorting:
    def insertion_sort(self,a):
        for i in range(1,len(a)):
            key = a[i]
            j = i
            while j > 0 and a[j-1] > key:
                a[j] = a[j-1]
                j-=1
            a[j] = key
        return a

    def random_array(self,size):
        b = []
        for i in range(0,size):
            b.append(random.randint(0,1000))
        print b
        return b


sort = Sorting()
print sort.insertion_sort(sort.random_array(10))

出力:

$ ./sort.py 
[195, 644, 900, 859, 367, 57, 534, 635, 707, 224]
[57, 195, 224, 367, 534, 635, 644, 707, 859, 900]
于 2012-09-10T21:19:28.677 に答える