복잡한 기준을 사용해 정렬할 때는 key parameter를 사용하라

08 Nov 2021

[Effective Python] Better way 14: 복잡한 기준을 사용해 정렬할 때는 key parameter를 사용하라

sort 메서드의 key parameter를 사용하면 리스트의 각 원소 대신 비교에 사용할 객체를 반환하는 helper function(보통 람다 함수)을 제공할 수 있습니다.
key 함수에서 tuple을 반환하면 여러 정렬 기준을 하나로 엮을 수 있습니다.
단항 부호 반전 연산자 혹은 reverse=True 를 통해 정렬 순서를 반대로 바꿀 수 있습니다.

책 내용을 보기전에 sort() 내장함수의 시간복잡도를 보겠습니다. c++에서는 STL library의 sort는 퀵소트로 구현되어 있으며, $O(nlogn)$의 시간복잡도를 가집니다.

당연히 파이썬에서도 sort()는 퀵소트로 구현되어 있을꺼라 생각했지만, 초기 버전에서만 퀵소트 였고, 현재는 adaptive mergesort인 tim sort를 사용한다고 합니다. 안정적인 merge sort버전이라고 합니다. 나중 포스트에 sort 알고리즘을 정리할때 같이 정리해 보겠습니다. (merge sort, quick sort, tim sort 모두 시간복잡도는 $O(nlogn)$이며 메모리와 안정성인 부분에서 다릅니다.)

(다음 link 를 보면 tim sort에 대해 잘 정리되어 있습니다.)

list 내장 타입에는 리스트의 원소를 여러 기준에 따라 정렬 할 수있는 sort 메서드가 들어가 있습니다. 기본적으로 오름차순 및 natural order로 정렬합니다.
```
  numbers =[93,86,11,68,70]
  numbers.sort()
  print(numbers)
  # [11, 68, 70, 86, 93]
```

클래스에서 인스턴스를 출려할 수 있는 __repr__ 메서와 함께 정의하여 다음과 같이 사용할 수 있습니다. sort 메서드가 호출하는 객체 비교 특별 메서드에 대한 정의 혹은 정렬에 사용하고싶은 attirbute에 대한 key함수를 sort인자에 설정해주지 넣지 않으면 에러가 납니다.

  class Person:
      def __init__(self,name,weight):
          self.name = name
          self.weight = weight

      def __repr__(self):
          return f'(이름:{self.name!r},무게:{self.weight})'

  people =[
      Person('철수',65.7),
      Person('미애',56),
      Person('덕구',83),
  ]

  people.sort()
  # TypeError: '<' not supported between instances of 'Person' and 'Person'

다음과 같이 name, weight에 대한 람다함수를 정의하여 정의할 수 있습니다.

  print("미정렬: ",repr(people))
  people.sort(key=lambda x:x.weight)
  print("\n정렬: ",repr(people))
  # 정렬: [(이름:'미애',무게:56), (이름:'철수',무게:65.7), (이름:'덕구',무게:83)]

문자열과 같은 경우 key 함수를 사용하여 원소값을 변형할 수 있습니다.

  places = ['home','work','New York','Paris']
  places.sort()
  print('대소문자 구분:',places)
  # 대소문자 구분: ['New York', 'Paris', 'home', 'work']
  places.sort(key=lambda x:x.lower())
  print('대소문자 무시:',places)
  # 대소문자 무시: ['home', 'New York', 'Paris', 'work']

여러 기준을 사용해 정렬해야 할 수 도 있습니다. 파이썬에서 가장 쉬운 해법은 tuple 타입을 사용하는 것입니다. tuple class 내에는 sort에 필요한 __lt__ (객체 비교 특별 메서드)가 정의되어 있습니다. 이 특별 비교 메서드는 튜플의 각 위치를 이터레이션하면서 각 인덱스에 해당하는 원소를 한번에 한번씩 비교하는 방식으로 구현되어 있습니다.
```
  drill = (4,'드릴')
  sander =(4,'연마기')
  assert drill[0] == sander[0]
  assert drill[1] <sander[1]
  assert drill < sander
```
위의 코드처럼 튜프의 첫번째 위치에 값이 같으면 튜플의 비교메서드는 두번째 위치에 있는 값을 비교하고, 두번째 위치에 있는 값도 같으면 세번째 이후 위치 등의 비교를 반복합니다.

튜플 비교의 동작 방식을 활용해서 전동 공구 리스트를 먼저 weigth로 정렬하고 그 후 name으로 정렬할 수 있습니다.

  fat_people = [
      Person('민수',97),
      Person('인호',103),
      Person('종원',92),
      Person('형섭',92)
  ]
  fat_people.sort(key=lambda x:(x.weight,x.name))
  print("fat people:",repr(fat_people))
  # fat people: [(이름:'종원',무게:92), (이름:'형섭',무게:92), (이름:'민수',무게:97), (이름:'인호',무게:103)]

튜플을 반환하는 key 함수의 한가지 제약 사항은 모든 비교 기준의 정렬 순서가 한 방향입니다. (오름 차순 혹은 내림차순) 그래서 해결 방법으로, 숫자 값의 경우 단항 부호 반전(-) 연산자를 활용해 정렬 방향을 혼합할 수 있습니다.
```
  fat_people.sort(key=lambda x:(-x.weight,x.name))
  print("fat people:",repr(fat_people))
  # fat people: [(이름:'인호',무게:103), (이름:'민수',무게:97), (이름:'종원',무게:92), (이름:'형섭',무게:92)]
```
하지만 모든 타입에 부호 반전을 사용할 수 없습니다.
```
  fat_people.sort(key=lambda x:(x.weight,-x.name))
  # TypeError: bad operand type for unary -: 'str'
```
파이썬에서 이런 상황을 위해 안정적인(stable) 정렬 알고리즘을 제공합니다. 리스트 타입의 sort 메서드는 key함수가 반환하는 값이 서로 같은 경우 리스트에 들어 있던 원래 순서를 유지 해줍니다.
```
  fat_people.sort(key=lambda x:x.name)
  print("fat people:",repr(fat_people))
  # fat people: [(이름:'민수',무게:97), (이름:'인호',무게:103), (이름:'종원',무게:92), (이름:'형섭',무게:92)]

  fat_people.sort(key=lambda x:x.weight,reverse=True)
  print("fat people:",repr(fat_people))
  # fat people: [(이름:'인호',무게:103), (이름:'민수',무게:97), (이름:'종원',무게:92), (이름:'형섭',무게:92)]
```
위의 코드는 weight 기준으로 내림차순, name 기준으로 오름차순으로 정렬을 수행합니다. 즉, 최종적으로 리스트에서 얻어 내고싶은 정렬 기준 우선순위의 역순으로 정렬을 수행해야 합니다. (weigth으로 내림차순이 원하는 우선순위) sort를 여러번 호출하는 방법은 꼭 필요할때만 사용하고, key함수에 tuple을 반환하여 정렬하는 것이 더 가독성이 좋습니다.

ChangHyeon Nam's Blog notes and thoughts

복잡한 기준을 사용해 정렬할 때는 key parameter를 사용하라

[Effective Python] Better way 14: 복잡한 기준을 사용해 정렬할 때는 key parameter를 사용하라