0

正しくループしてリストをソートする方法を見つけようとしています。

私はこれまでのところこれを持っています：

def min_sorted(xs):
    Min= xs[0]
    minsorted= list()
    for x in xs:
        if x < (Min):
            Min= x
            minsorted.append(Min)
            remove_val_once(x,xs)
    return minsorted

これを使用してテストすると、xs=[5,3,4,2,1]次のようになります。

>>> min_sorted([5,3,4,2,1])
[3, 2, 1]

5と4に何が起こっているのか

minval(xs) の私のコード:

def minval(xs):
min_= xs[0]
for x in xs[1:]:
    if x < min_:
        min_=x      
return min_

remove_val_once の私のコード:

def remove_val_once(val,xs):
    for i in range(len(xs)):
        if val==xs[i]:
            del(val)
            return True
            break
    if val!=xs[i]:
        return False
4

8 に答える 8

3

まず第一に、あなたのアルゴリズムには根本的な欠陥があります。この方法でリストをソートすることはできません。

次の 2 つの理由から、リストを処理するときに要素をスキップします。

  1. Minの以前の値を追加せずに破棄します。これがスキップする理由です5。

  2. 繰り返しながらリストを変更しています。を処理するとき3、リストから削除します。ループはリストの 2 番目の項目を調べていましたが、削除するとリストが からに3変更され、その後ループは3 番目の項目である nowに続きます。あなたはそこをスキップしました。[5, 3, 4, 2, 1][5, 4, 2, 1]24

アルゴリズムが機能しない理由について: のように、開始時に最小値を持つリストをアルゴリズムがどのように処理するかを考えてみてください[1, 5, 4, 3, 2]。

于 2013-11-10T01:42:13.987 に答える
2

ループ内でリスト xs を操作しているため、ループが奇妙な動作をします。xs を一時リストにコピーして操作することをお勧めします。コードを参照してください：

def min_sorted(xs):
    Min= xs[0]
    minsorted= list()
    t = xs[:]
    while t:
        Min = min(t)
        minsorted.append(Min)
        remove_val_once(t,Min)
    return minsorted

min 関数自体が O(n) であり、元の入力リストをループしているため、これは O(n^2) アルゴリズムです。

にもバグがありますremove_val_once。 の使い方delが間違っています。次のようになります。

del xs[i]
于 2013-11-10T01:41:12.933 に答える
1

5 と 4 は、「ソート」アルゴリズムによって破棄されています。コードで行うことは、 の最初の要素xsが よりも小さい場合xs[0]、次にそれよりも小さいリストの次の要素を取得し、次にそれよりも小さい次の要素をリストの最後まで取得することです。スキップされた値に対しては何もしません。

于 2013-11-10T01:42:27.333 に答える
0

.sort() を使用せずに並べ替える簡単な方法があります。挿入ソートを紹介します：

def insertionSort(unsortedList):
    # copy list
    length = len(unsortedList)
    sortedList = [None] * length
    for i in range(length):
    sortedList[i] = unsortedList[i];
    for i in range(1, length):
        j = i-1
        value = sortedList[i]
        while j >= 0 and value < sortedList[j]:
            sortedList[j+1] = sortedList[j]
            j = j-1
        sortedList[j+1] = i
于 2013-11-10T01:47:59.187 に答える
0 
def min_sorted(values):
    result = []
    while values:
        m = min(values)
        result.append(m)
        values.remove(m)
    return result
于 2013-11-10T01:39:20.910 に答える
0

シンプルで素朴なバブルソート:

import random

def bubble_sort(unsorted):
    length = len(unsorted) - 1
    sorted = False
    while not sorted:
        sorted = True
        for i in range(length):
            if unsorted[i] > unsorted[i+1]:
                sorted = False
                unsorted[i], unsorted[i+1] = unsorted[i+1], unsorted[i]

li = [random.randint(-100,100) for i in range(20)]
bubble_sort(li)
print li
于 2013-11-10T02:04:33.203 に答える