참고: 이 글은 Ruby로 다양한 정렬 알고리즘을 살펴보는 시리즈의 2부입니다. 1부에서는 버블 정렬을 다루었습니다.
이번 글에서는 Ruby로 선택 정렬(selection sort) 알고리즘을 구현하는 방법을 단계별로 살펴보겠습니다. 선택 정렬은 제자리(in-place) 비교 정렬 알고리즘으로, 정렬된 요소들이 원래 배열과 동일한 저장 공간을 사용한다는 의미입니다. 본격적으로 들어가기에 앞서 한 가지 짚고 넘어갈 점이 있습니다. 선택 정렬은 데이터셋이 작은 경우(예: 10~20개 요소)를 제외하면 실무에서 거의 사용되지 않습니다. 하지만 자전거에 오르기 전에 세발자차를 배우듯, 정렬 알고리즘의 기초를 익히기에는 아주 훌륭한 출발점입니다. 코딩 테스트나 기술 면접에서 선택 정렬 구현을 요구받거나, "대용량 데이터셋에서 이 알고리즘이 왜 비효율적인가?"라는 질문을 받을 수도 있습니다. 참고로 선택 정렬은 이 시리즈의 첫 번째 주제였던 버블 정렬보다 대체로 더 나은 성능을 보입니다.
선택 정렬의 핵심 개념을 간단히 설명하면 다음과 같습니다. 배열을 '정렬된 부분'과 '정렬되지 않은 부분', 두 영역으로 나눕니다. 시작 시점에는 정렬된 부분이 비어 있고, 모든 요소가 정렬되지 않은 부분에 속합니다. 선택 정렬은 두 개의 반복문을 사용합니다. 바깥쪽 루프는 배열의 요소 개수인 n번만큼 순회하고, 각 회차마다 '최소 인덱스(min index)'를 현재 위치의 첫 번째 요소로 설정합니다. 그다음 안쪽 루프로 나머지 요소들을 비교하면서, 현재 최솟값보다 작은 요소를 발견하면 최소 인덱스를 갱신합니다.
글로만 설명해서 잘 와닿지 않으셔도 걱정하지 마세요. 바로 실제 예제를 통해 하나씩 살펴보겠습니다.
단계별 예제
다음 요소들을 가진 배열로 시작해 보겠습니다: [10, 30, 27, 7, 33, 15, 40, 50]
1회차: 가장 작은 숫자 찾기
이 배열에서 가장 작은 숫자는 7입니다. 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]
이후에도 같은 과정을 배열이 완전히 정렬될 때까지 반복합니다. 다음 회차들의 결과는 아래와 같습니다.
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]
짜잔! 배열이 완전히 정렬되었습니다!
시각적인 학습을 선호하신다면, 아래 이미지처럼 선택 정렬의 전체 진행 과정을 한눈에 파악할 수 있습니다.
사진 출처
Ruby 구현
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번째 요소까지 아래 내용을 수행하라"는 의미입니다. .. 연산자가 익숙하지 않다면, 시작점부터 끝점까지 포함하는 범위(range)를 만든다는 점을 기억하세요. 예를 들어 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와 같은지 확인합니다. 다르다면 요소들의 위치를 교환(swap)해야 합니다. 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 notation)'을 확인하는 것입니다. 빅오 표기법은 최악의 경우 성능을 나타내며, 이를 통해 여러 알고리즘을 공정하게 비교할 수 있습니다. 예를 들어 O(1)인 알고리즘은 요소 개수 n이 증가해도 최악의 경우 실행 시간이 일정하게 유지되는 반면, O(n)인 알고리즘은 n이 커질수록 실행 시간이 선형적으로 증가합니다. 따라서 100개의 요소를 가진 배열을 정렬할 때 O(n) 알고리즘과 O(1) 알고리즘 중 하나를 골라야 한다면, 당연히 O(1) 알고리즘을 선택해야 합니다.
버블 정렬과 마찬가지로 선택 정렬도 중첩 루프(nested loop) 구조 때문에 최악의 경우와 평균 복잡도가 모두 O(n²)입니다. 이는 요소 개수가 늘어날수록 효율성이 급격히 떨어진다는 의미입니다.
마치며
정리하자면, 선택 정렬은 실무에서 자주 쓰이지는 않지만 코딩 테스트에 등장할 수 있는 흥미로운 알고리즘입니다. 또는 선택 정렬 함수를 제공받고 "이 코드의 빅오 표기법은 무엇이며, 그 이유는 무엇인가?"라는 질문을 받을 수도 있습니다. 이 글의 예제들이 두 시나리오 모두에 대비하는 데 도움이 되기를 바랍니다.