삽입 정렬

삽입 정렬에 대한 가장 좋은 비유는 카드 한 벌입니다. 그리고 그것들을 가장 작은 것부터 가장 큰 것까지 올바른 순서로 배치해야 합니다. 모든 것을 순서대로 정렬하기 위해 카드 주위에 다른 카드를 이동하는 동안 적어도 하나의 카드를 일정하게 유지합니다. 고려 중인 요소는 한 지점 또는 여러 지점으로 이동할 수 있습니다.

def insertion_sort(array)
  return array if array.size <= 1

  (array.length).times do |i|
    while i > 0
      if array[i-1] > array[i]
        array[i], array[i-1] = array[i-1], array[i]
      else
        break
      end
      i-=1
    end
  end
  array
end

비어 있거나 하나의 요소를 포함하는 경우 배열을 반환합니다

.

(array.length).times로 배열을 반복하고, i는 배열

의 인덱스를 나타냅니다.

요소의 인덱스 > 0일 때 루프에서

if/else 조건을 설정하고 이전 값이 현재보다 크면 교환하고, 그렇지 않으면 루프를 종료합니다

.

루프가 종료되지 않으면 배열의 인덱스를 줄이고 계속합니다.

Time Complexity: О(n^2)
Space Complexity: О(n)