7

これは簡単な質問のように思えるかもしれませんが、Pythonで選択ソートを実装しようとすると、ソートされたリストが表示されません。私の実装に何か問題がありますか？サブセット化が問題になる可能性があります。

source = [4,2,1,10,5,3,100]
for i in range(len(source)):
  mini = min(source[i:]) #find minimum element
  min_index = source[i:].index(mini)-1 #find index of minimum element
  source[i:][min_index]= source[i:][0] #replace element at min_index with first element
  source[i:][0] = mini                  #replace first element with min element
print source
4

14 に答える 14

4

これが私があなたのコードを書き直す方法です。もちろん、Python ではlist.sort()リストをソートするために使用するだけですが、ここでは Python での選択ソートを示します。

(value, i)リストから値とそのインデックスのタプルを返すジェネレータ式を作成します。次に、min()最小値を見つけるために評価するときに、最小のタプル値を見つけます。値はインデックスの前のタプルで最初に来るため、値は重要な部分になりmin()、最小値を見つけます。(同点の場合はmin()、タプルの 2 番目の部分であるインデックスをタイブレーカーとして使用します。ただし、並べ替えの場合、タイがどのように壊れたかは気にしません。)

ここで、サブリストを検索して最小値を見つけ、次にサブリストを再度検索してインデックスを見つける代わりに、一度検索して最小値とインデックスの両方を取得します。

しかし、実際には最小値は気にしません。私たちはインデックスを気にします。そのmin()ため、完了したら、実際の値を破棄してインデックスを保持します。リスト全体（リストのスライスではなく）でインデックスが正しくなるように調整すると、交換できます。

2 つの値を交換するために、標準の Python イディオムを使用します。Python は、中間となるタプル オブジェクトを構築し、このタプルを左側にアンパックします。

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    genexp = ((n, i) for i, n in enumerate(lst[i_sortpos:]))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)

編集：そして、これは上記の改良です。リストからのスライスは、実際には新しいリストを割り当てます。ここでのコードには新しいリストは必要ありません。サブリストを調べるための便利な方法が必要なだけです。このitertoolsモジュールはislice()、リストのスライスを反復処理する反復子を返す関数 を提供します。これにより、各サブリストを調べるときにリストの作成と破棄を繰り返す必要がなくなります。

これは、Python で選択ソートを行う最も効率的な方法だと思います。genexp(ジェネレータ式を名前にバインドし、数マイクロ秒を節約する部分を取り除くことができます...min()長いワンライナーを呼び出すだけです。しかし、読みやすさを失う価値はありません。)

import itertools as it

lst = [4,2,1,10,5,3,100]

for i_sortpos in range(len(lst)):
    # Make a generator expression to return (value, i) pairs.
    # Use it.islice() for to look at sublist.
    genexp = ((n, i) for i, n in enumerate(it.islice(lst, i_sortpos, len(lst))))
    # Use genexp with min() to find lowest and its index.
    # (Use '_' for variable name for the actual value; we don't use it.)
    _, i_min = min(genexp)
    # Adjust index to be correct in full list.
    i_min += i_sortpos
    # Swap the number at i_sortpos with the lowest found.
    lst[i_sortpos], lst[i_min] = lst[i_min], lst[i_sortpos]

print(lst)
于 2013-03-05T23:01:20.367 に答える
0 
def selSort(L):
    """
    Find the smallest element in the list and put it (swap it) in the first location, 
    Find the second element and put it (swap it) in the second locaiton, and so on. 

    """
    for i in range(len(L) - 1):
        minIndx = i
        minVal= L[i]
        j = i + 1
        while j < len(L):
            if minVal > L[j]:
                minIndx = j
                minVal= L[j]
            j += 1
        temp = L[i]
        L[i] = L[minIndx]
        L[minIndx] = temp 
    return L

電話：

print( selSort([120,11,0,1,3,2,3,4,5,6,7,8,9,10]) )

出力

[0, 1, 2, 3, 3, 4, 5, 6, 7, 8, 9, 10, 11, 120]
于 2017-01-03T20:07:20.510 に答える
0

位置（最初と最後）を見つけ、最後が低い場合は要素を交換します。

nums = [4,2,1,10,5,3,100]
def sort(nums):
     ###Find the position and now first 0th element is sorted and rest is unsorted
    #Second iteration first 2 element is sorted
    for i in range(len(nums)-1):
        miniposition = i
        for j in range(i,len(nums)):
            if nums[j] < nums[miniposition]:
                miniposition = j
        temp = nums[i]
        nums[i] = nums[miniposition]
        nums[miniposition] = temp
sort(nums)
print (nums)

最初の反復 (4 と 1 を交換) [1, 2, 4, 10, 5, 3, 100]

[1, 2, 4, 10, 5, 3, 100]
[1, 2, 3, 10, 5, 4, 100]
[1, 2, 3, 4, 5, 10, 100]
[1, 2, 3, 4, 5, 10, 100]
[1, 2, 3, 4, 5, 10, 100]

他の方法

nums = [4,2,1,10,5,3,100]
i = 0
while i<len(nums):
    #smallest element in the sublist
    smallest = min(nums[i:])
    #index of smallest element
    index_of_smallest = nums.index(smallest)
    #swapping
    nums[i],nums[index_of_smallest] = nums[index_of_smallest],nums[i]
    i=i+1
print (nums)
于 2019-09-27T05:13:39.290 に答える
0

提供されるソリューションのわずかなバリエーション

def selection_sort(l):
i = 0
while i < len(l):
    minium_value = min(l[i:]) # minium value at ith iteration
    minium_value_index = l[i:].index(minium_value) # minium value index at i th iteration

    if minium_value < l[i]: # if the current value already min, skip
        l[i + minium_value_index] = l[i] # put current value in min value's index - swap 1
        l[i] = minium_value # set current value with min value- swap 2
    i += 1

return l
于 2021-07-17T17:47:24.217 に答える
0 
def ss(l):    
    for i in range(0,len(l)):
        d=l.index(min(l[i:]))        
        c=l[i]
        l[i]=min(l[i:])
        l[d]=c
        print(l)  #it prints each step of selection sort
y=[10,9,1,5,0,6]
ss(y)
于 2015-10-18T21:05:04.563 に答える
-1

これは、数字のリストをソートする良い方法だと私が思うものであり、それが役立つことを願っています:

list=[5,4,3,1,6,8,10,9]
listsorted=[]
for i in range(len(list)):
    x=min(list)
    list.remove(x)
    listsorted.append(x)
print listsorted

結果は [1, 3, 4, 5, 6, 8, 9, 10] になります。

于 2016-02-19T21:36:25.117 に答える
-2 
def selectSort(L):
  for i in range(len(L)):
    print L
    minIndex = i
    minValue = L[i]
    j = i + 1
    while j < len(L):
        if minValue > L[j]:
            minIndex = j
            minValue = L[j]  
        j +=1
    temp = L[i]
    L[i] = L[minIndex]
    L[minIndex] = temp
于 2015-08-25T05:07:04.880 に答える
-2

MIT オンライン コースからの選択ソートのコード。

def selSort(L):
    for i in range(len(L) - 1):
        minIndx = i
        minVal = L[i]
        j = i+1
        while j < len(L):
            if minVal > L[j]:
                minIndx = j
                minVal = L[j]
            j += 1
        if minIndx != i:
            temp = L[i]
            L[i] = L[minIndx]
            L[minIndx] = temp
于 2015-07-16T08:35:53.437 に答える