참고:이것은 Ruby를 사용한 다양한 정렬 알고리즘을 살펴보는 시리즈의 2부입니다. 1부에서는 버블 정렬을 살펴보았습니다.
이 포스트에서는 Ruby로 선택 정렬 알고리즘을 구현하는 방법을 살펴보겠습니다. 선택 정렬은 내부 비교 정렬 알고리즘입니다. 이는 정렬된 항목이 원래 항목과 동일한 저장소를 차지함을 의미합니다. 더 진행하기 전에 데이터 세트가 작은 경우(즉, 10-20개 요소)가 아니면 선택 정렬 알고리즘이 실제로 일반적으로 사용되지 않는다는 점에 유의하는 것이 중요합니다. 그러나 원한다면 자전거보다 먼저 세발자전거를 타는 방법을 배우는 것과 유사하게 배우고 이해할 수 있는 훌륭한 스타터 알고리즘입니다. 구현은 면접을 위한 코딩 챌린지에 나타나거나 이유를 설명하라는 요청을 받을 수 있습니다. 선택 정렬과 같은 알고리즘은 큰 데이터 세트에서 그다지 실용적이지 않습니다. 선택 정렬은 일반적으로 이 시리즈에서 살펴본 첫 번째 알고리즘인 버블 정렬보다 성능이 뛰어납니다.
높은 수준에서 선택 정렬은 배열을 두 부분으로 나눕니다. 절반은 정렬되고 다른 하나는 정렬되지 않습니다. 처음에는 정렬된 섹션이 비어 있고 정렬되지 않은 부분에는 모든 요소가 포함됩니다. 선택 정렬은 두 개의 루프를 사용합니다. 외부 루프는 n번 반복합니다. 여기서 n은 배열의 요소 수입니다. "최소 인덱스"를 첫 번째 요소로 즉시 설정한 다음 다른 루프를 사용하여 요소를 비교하고 인접 요소가 현재 최소값보다 작으면 최소 인덱스를 교체합니다.
따라하기 어렵다면 걱정하지 마세요! 다음에는 실제 예를 살펴보겠습니다. :)
단계별
다음 요소가 있는 배열로 시작하겠습니다. [10, 30, 27, 7, 33, 15, 40, 50]
1번 반복:가장 작은 수 찾기
이 경우 가장 작은 숫자는 7입니다. , 그래서 우리는 그것을 시작 부분에 놓고 10을 이동합니다. 7 였다. 배열은 이제 다음과 같습니다. [7, 30, 27, 10, 33, 15, 40, 50]
반복 2:다음으로 작은 수 찾기
인덱스 위치 1의 요소에서 시작하여(배열은 0부터 인덱스됨) 다음으로 가장 작은 요소를 찾습니다.
이 경우 10.입니다. 10 이동 배열의 두 번째 위치로 이동하고 30 10 였다. 결과 배열은 다음과 같습니다. [7, 10, 27, 30, 33, 15, 40, 50]
여기에서 배열이 완전히 정렬될 때까지 이 정확한 프로세스를 계속합니다. 아래에서 다음 반복 후에 결과 배열을 볼 수 있습니다.
세 번째 반복:
[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]
빙고! 정렬되었습니다!
시각적 학습자라면 다음은 [] 배열에서 선택 정렬이 작동하는 방식의 예입니다.
사진 제공
루비 구현
다음은 Ruby로 작성된 선택 정렬 기능입니다.
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이므로 1을 빼야 한다는 것을 기억하십시오.
다음으로 n을 실행할 외부 루프를 만듭니다. 배.
min_index = i
여기서는 첫 번째 위치에 있는 요소의 최소 인덱스를 설정합니다.
for j in (i + 1)..n
다음으로 내부 루프를 만듭니다. 이 줄은 "n번째 요소의 두 번째 위치에 있는 요소에 대해 다음을 수행하십시오"라고 말합니다. ..에 익숙하지 않은 경우 연산자를 사용하여 시작점에서 끝점까지의 범위를 생성합니다. 예: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
멋지다!
선택 정렬이 비효율적인 이유 이해
알고리즘의 효율성을 측정하는 한 가지 방법은 "Big-O 표기법"을 살펴보는 것입니다. 이것은 알고리즘을 비교할 수 있도록 최악의 성능을 나타냅니다. 예를 들어 Big-O가 O(1)인 알고리즘은 최악의 경우 실행 시간이 요소 수 "n"이 증가함에 따라 일정함을 의미하는 반면 Big-O 표기법이 O(n)인 알고리즘은 )은 최악의 경우 실행 시간이 n이 증가함에 따라 선형적으로 증가함을 의미합니다. 이것은 100개의 요소가 있는 배열이 있고 O(n) 및 O(1)인 정렬 알고리즘 중에서 선택해야 하는 경우 O(1)이 O(100)보다 확실히 우수하기 때문에 O(1) 알고리즘을 선택한다는 것을 의미합니다.
버블 정렬과 마찬가지로 선택 정렬은 중첩 루프로 인해 최악의 경우 평균 복잡성이 O(n^2)입니다. 이는 요소 수가 증가함에 따라 효율성이 급격히 감소한다는 것을 의미합니다.
마무리
모든 것을 고려할 때 선택 정렬은 여전히 코딩 문제에서 나타날 수 있는 흥미로운 알고리즘입니다. 또는 선택 정렬 기능이 제공되고 Big-O 표기법이 무엇이며 그 이유를 물을 수 있습니다. 이 문서의 예가 두 시나리오를 모두 처리하는 데 도움이 되기를 바랍니다.