.sort 메소드로 안정 정렬 구현하기

정렬 알고리즘에 대해 공부하다 보면 안정 정렬(stable sort)과 불안정 정렬(unstable sort)에 대해 들어 보신 적이 있을 것입니다.

이 둘의 차이가 무엇인지를 일단 간단히 설명드리자면,

정렬 키 값이 같은 데이터들에 대해 정렬 전의 순서가 정렬 후에도 유지될 것이 보장되면 안정 정렬이라고 하고, 키 값이 같은 데이터들의 순서가 정렬 후 서로 바뀔 가능성이 있으면 불안정 정렬이라고 합니다.
예를 들어, 배열이 [4, 4, 1, 6, 7, 9, 5, 8, 3, 2] 이렇게 처음에 똑같은 4가 두 개 있을 때 첫 번째 4가 정렬 후에도 항상 두 번째 4보다 앞에 있게 되면 안정 정렬이고, 첫 번째 4가 정렬 후에 두 번째 4보다 뒤로 갈 가능성이 있으면 불안정 정렬입니다.

그러면, 루비의 .sort 메소드는 안정 정렬일까요, 불안정 정렬일까요? 한 번 봅시다.

gfriend = Array.new
gfriend << ["신비", 1998]
gfriend << ["예린", 1996]
gfriend << ["소원", 1995]
gfriend << ["은하", 1997]
gfriend << ["엄지", 1998]
gfriend << ["유주", 1997]
 
gfriend.sort_by! { |name, byear| byear }

gfriend.each_index do |x|
  puts sprintf("%s", gfriend[x])
end

순서가 뒤섞여 있는데 생년월일 순서로 정렬합니다. 어떻게 될까요?

["소원", 1995]
["예린", 1996]
["유주", 1997]
["은하", 1997]
["엄지", 1998]
["신비", 1998]

이렇게 나옵니다.

정렬 대상인 생년월일의 값이 중복되는 두 쌍을 보면, 정렬 전에는 은하가 유주보다 앞이었는데 정렬 결과 유주가 앞으로 갔으며, 신비가 엄지보다 앞이었는데 정렬하고 나니까 엄지가 앞으로 갔습니다. 이것으로 보아 .sort 메소드는 기본적으로 불안정 정렬임을 알 수 있습니다.

그러면 정렬 알고리즘 없이 배열을 안정 정렬이 되게 할 방법은 없을까요? 있습니다.

gfriend = Array.new
gfriend << ["신비", 1998]
gfriend << ["예린", 1996]
gfriend << ["소원", 1995]
gfriend << ["은하", 1997]
gfriend << ["엄지", 1998]
gfriend << ["유주", 1997]
 
gfriend.sort_by!.with_index { |(name, byear), idx| [byear, idx] }

gfriend.each_index do |x|
  puts sprintf("%s", gfriend[x])
end

앞의 코드에서 9번 줄 한 줄만 바꾸었을 뿐인데 결과는 과연 어떻게 될까요?

["소원", 1995]
["예린", 1996]
["은하", 1997]
["유주", 1997]
["신비", 1998]
["엄지", 1998]

생년월일 순으로 정렬이 제대로 이루어지면서도 생년월일이 같은 은하-유주, 신비-엄지의 순서가 서로 바뀌지 않았습니다.

이것은 .sort_by 메소드 뒤에 추가로 붙은 .with_index 메소드 덕분입니다. .with_index 메소드를 이용함으로써 정렬 전 원소들의 순서를 기억한 다음 정해진 기준대로 정렬을 끝내고 나면 정렬 키 값이 같은 원소들끼리만 기억된 정렬 전 순서대로 재정렬함으로써 정렬을 마무리합니다. 이렇게 함으로써 안정 정렬 알고리즘을 쓴 것과 같은 효과를 얻게 되는 것입니다.

참고로 .sort_by 메소드 뒤에 .with_index 메소드를 쓸 때는 중괄호 안 왼쪽 부분을 |x, y, idx| 식으로 쓰면 제대로 작동하지 않으므로 |(x, y), idx| 식으로 써야 합니다. 또한, .with_index 메소드 뒤에는 느낌표를 붙일 수 없습니다.

# 다음 두 줄은 정상적으로 실행됩니다.
  arr.sort_by.with_index { |(x, y), z| [x, z] }
  arr.sort_by!.with_index { |(x, y), z| [y, z] }

# 다음 두 줄은 제대로 작동하지 않습니다.
  arr.sort_by.with_index { |x, y, z| [x, z] }
  arr.sort_by!.with_index { |x, y, z| [y, z] }

# 다음 두 줄은 오류를 일으킵니다.
  arr.sort_by.with_index! { |(x, y), z| [x, z] }
  arr.sort_by!.with_index! { |(x, y), z| [y, z] }

여기서 sort 메소드로 안정 정렬을 구현하는 방법에 대한 설명을 마칩니다.

많은 도움 되셨나요?

유용한 정보로 활용하시기를 바랍니다.