News for hackers. Stuff that matters.
Re:Is this the simplest (and most surprising) sorting algori... by edflsafoiewq on Tuesday October 05, 2021 @10:29AM (#28759972)
Break the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps.

  for i = 1 to n do
    - Inserts A[i] into A[1 to i-1], using the A[i]
    - spot as a temp variable.
    for j = 1 to i-1 do
      if A[i] < A[j] then
        swap A[i] and A[j]

    - Does nothing.
    for j = i do
      if A[i] < A[j] then
        swap A[i] and A[j]

    - Permutes A[i to n], placing the maximum into
    - A[i]. Since A[i] already has the max after the
    - first iteration, it won't change, and we don't
    - care how A[i+1 to n] is permuted since it gets
    - sorted anyway.
    for j = i+1 to n do
      if A[i] < A[j] then
        swap A[i] and A[j]

There are no comments on this comment yet.