挿入ソートアルゴリズムを増加させないように修正する

Question

挿入ソートの出力を増加しない順序に変更する方法を知りたいですか？たとえば、537は753になります。また、ランタイムは、増加する（最高と最悪の両方）場合と同じになりますか？

擬似コード：

INSERTION-SORT(A) 
    for j = 2 to A.length 
     key = A[j] 
     // Insert A[j] into the sorted sequence A[1..j] 
     i = j - 1 
     while i > 0 and A[i] > key 
      A[i +1] = A[i] 
      i = i - 1 
     A[i + 1] = key 

Answer 1

ランタイムは、変更によって影響を受けません。コンピュータサイエンスで数値を話すときがの代わりにの代わりにと言う方が良いでしょう。 が増加すると、は、になります。つまり、あなたが探している変更については、以下のコードを参照してください（特にwhileループに注意してください）。

for j = 2 to A.length 
    key = A[j] 
    i = j - 1 
    while i > 0 and A[i] < key 
     A[i + 1] = A[i] 
     i = i - 1 
    A[i + 1] = key