Ruby를 사용하여 정렬 선택 이해

본고는 최초Julie Kent에 의해 Honeybadger Developer Blog에 작성되었다.
본고에서 루비를 사용하여 정렬 알고리즘을 선택하는 방법을 소개하겠습니다.정렬을 선택하는 것은 현지에서 정렬을 비교하는 알고리즘이다.이것은 정렬된 항목이 원시 항목과 같은 저장 공간을 차지한다는 것을 의미한다.우리가 한층 더 토론하기 전에 주의해야 할 것은 정렬 알고리즘을 선택하는 것이 실천에서 자주 사용되지 않는다는 것이다. 데이터 집합이 매우 작지 않은 경우(즉 10-20개의 요소).그러나 당신이 원한다면 이것은 자전거를 타기 전에 어떻게 삼륜차를 타는지 배우는 것과 같은 좋은 입문 알고리즘이다.이 실현은 구직 면접의 인코딩 도전에 나타날 수도 있고, 왜 정렬 선택 같은 알고리즘이 대형 데이터 집합에서 실용적이지 않은지 설명해 달라는 요청을 받을 수도 있습니다.정렬을 선택하는 것은 일반적으로 거품 정렬보다 낫다. 이것은 우리가 본 시리즈에서 연구한 첫 번째 알고리즘이다.
높은 단계에서 정렬을 선택하여 그룹을 두 부분으로 나눈다. 일부는 정렬되었고, 다른 일부는 정렬되지 않았다.시작할 때 정렬 부분은 비어 있고 정렬되지 않은 부분은 모든 요소를 포함합니다.정렬을 선택하여 두 개의 순환을 이용한다.외부 순환은 n번으로 교체되며, 그 중에서 n은 수조의 원소수이다.우리는 즉시'최소 인덱스'를 첫 번째 요소로 설정하고 다른 순환을 사용하여 요소를 비교합니다. 인접 요소가 현재 최소 값보다 작으면 최소 인덱스를 교환합니다.
만약 이것이 매우 어렵다면 걱정하지 마라!다음은 실제 예제입니다.)

차근차근

다음 요소를 포함하는 그룹부터 시작합니다. [10, 30, 27, 7, 33, 15, 40, 50]반복일: 최소수 구하기
이 예에서 가장 작은 숫자는 7 이기 때문에 우리는 그것을 처음에 놓고 10 를 7 있는 위치로 이동한다.우리 그룹은 지금 이렇게 보인다. [7, 30, 27, 10, 33, 15, 40, 50]교체 2: 다음 가장 작은 수를 찾습니다
색인 위치 1의 원소부터 시작하여 다음 가장 작은 원소를 찾으십시오
이 경우 10. 는 10 을 패턴의 두 번째 위치로 이동하고 30 을 10 에 있는 위치로 이동합니다.결과 그룹은 다음과 같습니다. [7, 10, 27, 30, 33, 15, 40, 50]여기서부터 우리는 우리의 수조가 완전히 정렬될 때까지 이 정확한 과정을 계속한다.다음은 다음에 교체된 수조를 볼 수 있습니다.
반복 3:[7, 10, 15, 30, 33, 27, 40, 50]반복 4:[7, 10, 15, 27, 33, 30, 40, 50]반복 5:[7, 10, 15, 27, 30, 33, 40, 50]맞히다우리 분류됐어!
만약 당신이 시각 학습을 더욱 좋아한다면, 다음은 정렬이 어떻게 수조[]와 함께 작업하는지 선택하는 예이다

Photo credit

루비 구현

다음은 루비로 작성된 선택 정렬 함수입니다.

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

어떻게 작동하는지 봅시다.
우선, 우리는 n 를 원소수와 동일하게 설정할 것이다.수조가 0 인덱스이기 때문에, 우리는 하나를 빼야 한다는 것을 명심해라.
다음으로 외부 순환을 만듭니다. 이 순환은 n 번 실행됩니다.

min_index = i

여기, 우리는 첫 번째 위치의 요소를 위한 최소 인덱스를 설정합니다.

for j in (i + 1)..n

다음은 내부 순환을 만듭니다.이 줄은'두 번째 위치에서 두 번째 요소로 이동하는 요소에 대해 다음 작업을 수행합니다'를 나타냅니다... 연산자에 익숙하지 않으면 시작에서 끝까지의 범위가 생성됩니다.예를 들어, 1..10 1부터 10까지 (1과 10 포함) 범위를 만듭니다.

min_index = j if array[j] < array[min_index]

이 순환에서 min_index 가 현재 값min_index 보다 작으면 새 요소로 설정합니다.

array[i], array[min_index] = array[min_index], array[i] if min_index != i

내환 밖에서 우리는 전류min_index가 i와 같은지 관찰한다.만약 이것이 사실이라면, 우리는 우리의 요소를 씻어야 한다.우리는 array[i] 를 array[min_index], array[min_index] 를 array[i] 로 설정합니다.여기서 우리가 실행하는 교환은 우리가 예시에서 한 것과 같다.
마지막으로, 완성된 후, 우리는 수조를 출력합니다. 현재 이미 정렬되었습니다!

그것들을 한데 모으다

다음은 내 전체 계획입니다.

def selection_sort(array)
  n = array.length - 1
  n.times do |i|
    min_index = i
    for j in (i + 1)..n
      min_index = j if array[j] < array[min_index]
    end
    array[i], array[min_index] = array[min_index], array[i] if min_index != i
  end
  puts array
end

array = [10, 30, 27, 7, 33, 15, 40, 50]

selection_sort(array)

터미널 실행ruby ruby-selection-sort.rb에서 다음 내용을 출력합니다.

7
10
15
27
30
33
40
50

차갑다

정렬 효율이 낮은 이유를 이해하다

알고리즘의 효율을 평가하는 방법의 하나는'큰 O 기호'를 보는 것이다.이것은 최악의 상황에서의 성능을 대표하기 때문에 알고리즘을 비교할 수 있다.예를 들어 큰 O가 O(1)인 알고리즘은 최악의 상황에서의 운행 시간이 원소수'n'의 증가에 따라 일정하다는 것을 의미하고, 큰 O가 O(n)인 알고리즘은 최악의 상황에서의 운행 시간이 n의 증가에 따라 선형적으로 증가하는 것을 의미한다.이것은 100개의 요소를 포함하는 수조가 있고 O(n)와 O(1)의 정렬 알고리즘 사이에서 선택해야 한다면 O(1) 알고리즘을 선택할 것입니다. 왜냐하면 O(1)가 O(100)보다 우수하기 때문입니다.
거품 정렬과 마찬가지로 플러그인 순환으로 인해 정렬을 선택하는 최악의 상황과 평균 복잡도는 O(n^2)이다.이것은 원소의 수가 증가함에 따라 그 효율이 급격히 떨어진다는 것을 의미한다.

끝내다

위에서 말한 바와 같이 정렬을 선택하는 것은 여전히 재미있는 알고리즘으로 인코딩 도전에 나타날 수 있다.또는 정렬 함수를 선택하고 큰 O 기호가 무엇인지, 왜 그런지 물어볼 수도 있습니다.본고의 예시가 당신이 이 두 가지 상황을 처리할 준비를 하는 데 도움을 줄 수 있기를 바랍니다.