アルゴリズム - シングルエンドのものよりもダブルエンドの選択の方が実際に高速ですか？

Question

minとmaxの両方をスワップするダブルエンド選択ソートは、比較の数が同じであっても、通常の選択ソートより高速であると主張されています。私はそれがループのいくつかを取り除くことを理解しますが、比較の数が同じであれば、どのように速くなりますか？事前

Answer 1

で

おかげで、ここで選択ソートと比較を行っカウントダブルエンド選択ソートの実装です。

実行すると、ダブルエンド選択ソートは常により多く、の比較を通常の選択ソートよりも実行することがわかります。定期的な選択ソートのための比較の数であるためだ

import random 

def selsort(xs): 
    N = len(xs) 
    comparisons = 0 
    for i in xrange(N): 
     m = i 
     for j in xrange(i+1, N): 
      comparisons += 1 
      if xs[j] < xs[m]: m = j 
     xs[i], xs[m] = xs[m], xs[i] 
    return comparisons 

def deselsort(xs): 
    N = len(xs) 
    comparisons = 0 
    for i in xrange(N//2): 
     M = m = i 
     for j in xrange(i+1, N-i): 
      comparisons += 2 
      if xs[j] < xs[m]: m = j 
      if xs[j] >= xs[M]: M = j 
     xs[i], xs[m] = xs[m], xs[i] 
     if M == i: M = m 
     xs[N-i-1], xs[M] = xs[M], xs[N-i-1] 
    return comparisons 


for rr in xrange(1, 30): 
    xs = range(rr) 
    random.shuffle(xs) 
    xs0 = xs[:] 
    xs1 = xs[:] 
    print len(xs), selsort(xs0), deselsort(xs1) 
    assert xs0 == sorted(xs0), xs0 
    assert xs1 == sorted(xs1), xs1 

：

(n-1) + (n-2) + ... + 1 = n(n-1)/2 

ダブルエンド選択ソートの場合は、比較の数は（nが奇数のために - でもケースが似ている）であります

2(n-1) + 2(n-3) + 2(n-5) + ... + 2 
= (n-1)+(n-2)+1 + (n-3)+(n-4)+1 + ... 2+1+1 
= ((n-1) + (n-2) + ... + 1) + (n-1)/2 
= n(n-1)/2 + (n-1)/2