버블 정렬

버블 정렬은 컴퓨터 과학에서 일반적으로 사용되는 정렬 알고리즘입니다. 버블 정렬은 인접한 요소 쌍을 반복적으로 비교하고 잘못된 순서로 존재하는 경우 위치를 바꾸는 아이디어를 기반으로 합니다.

다른 말로 하면 더 큰 요소는 끝으로 '거품'이 되고 더 작은 요소는 모든 요소가 올바른 위치에 있을 때까지 시작 부분으로 '거품'됩니다.

순진한 구현:

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

  swap = true

  while swap
    swap = false
    (array.length - 1).times do |i|
      if array[i] > array[i+1]
        array[i], array[i+1] = array[i+1], array[i]
        swap = true
      end
    end
  end
  array
end

메서드는 단일 배열 매개변수를 사용합니다.

비어 있거나 하나의 요소로 구성된 경우 배열을 반환합니다

.

swap은 배열의 주어진 패스 동안 스왑이 발생했는지 여부를 나타내는 변수(플래그)입니다. 초기에 true로 설정

스왑이 true인 동안 실행되는 while 루프를 생성합니다

.

루프 시작 직후 스왑이 없었기 때문에 스왑을 false로 설정합니다.

루프에서 배열을 반복하고 요소의 값이 다음 요소의 값보다 크면 교환하고 교환을 true로 설정합니다.

모든 항목이 순서대로 지정되고 스왑 값이 false에 유지될 때까지 루프가 반복되며 루프는 종료되고 정렬된 배열을 반환합니다.

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

추신. 영감을 준 Michelle에게 감사합니다.