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

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

★프로그래밍/Ruby :: 2016.08.24 17:22

정렬 알고리즘에 대해 공부하다 보면 안정 정렬(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 메소드로 안정 정렬을 구현하는 방법에 대한 설명을 마칩니다.

많은 도움 되셨나요?

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

Today 12    Yday 63    Tot 65,494
Juwan Park
Juwan Park's blog is powered by Daum and TISTORY.
Contemporary Blue for TISTORY.
Designed by Juwan Park. Creative Commons License
▲ TOP