Pythonの選択ソートアルゴリズムは、最小値のリストのみを返します

Question

def sortList(self, list): 
    for i in range(len(list)): 
     min = list[i] 
     for j in range(i+1, len(list)): 
      if list[j] < min: 
       min = list[j] 
     list[i] = min 
    return list 

上記のアルゴリズムは最小値のリストを返します。たとえば、サンプルリストがlist = [4,7,9,2]の場合、アルゴリズムは[2,2,2,2]を返します。

アルゴリズムの欠陥はどこですか？

Answer 1

は、まあ、いくつかのミスがここにあります：すべての

1. は、まずあなたがlist[i]にそれをするたびに割り当てているので、あなたは、奇妙な方法でminを計算します。
2. "スワップ"しないと、リストのその部分に最小値を割り当てるだけです。

は何が基本的に必要なのは、それぞれの時間は、その後i間の最小とリストの最後、および「シフト」の右に他の要素、または占有している要素とのスワップを行うのいずれかを計算するアルゴリズムでありますその要素を配置したい場所。

私は最小値を見つけることO（N） opeationあることO（1）操作（ただし、心であるので（スワッピング）後者は、ほんの少しより効率的であると思う。

だから、使用することができます。

def sort_list(self,data): 
    n = len(data) # obtain the length of the list 
    for i in range(n): 
     min, minj = data[i], i # we use data[i] as the running min 
           # i as index of the smallest item 
     for j in range(i+1,n): # iterate over the remainder of the list 
      if data[j] < min: # if we find a smaller item 
       min, minj = data[j], j # update min and minj 

     # perform a swap between i and minj 
     t = data[i] 
     data[i] = min 
     data[minj] = t 
    return data 

をあなたがより良い組み込みを使用し、挿入ソートは間違いない最も効率的なソートアルゴリズムで言われていること0メソッド、またはsorted関数で、Python用に最適化されています。