정렬 안정성과 Python sorted, Lambda 함수를 활용한 구현
정렬에서 안정성(Stability)
키-값 쌍을 가진 데이터 시퀀스에서
같은 키를 가진 데이터들의 순서가
정렬 작업 이후와 정렬 작업 이전이 같은 정렬 알고리즘을
안정적인 정렬(Stable sort),
그렇지 않은 정렬 알고리즘을 불안정 정렬이라고한다.
키-값 쌍이 아닌 단일값 배열의 경우
키-값 구분이 무의미하기 때문에
굳이 안정성을 논하지 않는다.
Python에서 2개 이상의 키를 기준으로 정렬할 때
python의 sort 또는 sorted는
Tim sort 정렬을 사용하며
이는 안정 정렬이다.
Python Tim sort
sort()
- 원본 자체를 수정한다.
- list 객체에서 사용한다.
<list>.sort(key=<lambda f>, reverse=<bool>)
sorted()
- 원본 내용을 바꾸지 않고 정렬된 새 객체를 반환한다.
- list, tuple, dict, str에서 사용 가능하다.
sorted(<tuple>, key=<lambda f>, reverse=<bool>)
안정적인 정렬
버블 정렬, 삽입 정렬, 병합 정렬, 계수 정렬
불안정 정렬
선택 정렬, 퀵 정렬, 힙 정렬
2개 이상의 key를 기준으로 정렬할 때
sorted()함수의 key 인자에 lambda함수를 적용해서 구현 가능하다.
a = [(20,'app'), (108,'ddc'), (121,'zfk'), (17,'nok'), (22,'poc'), (47,'vpp'), (35,'atf'), (96,'pos'),]
sorted(a, key=lambda x: (x[0], x[1]) )
여러 개의 키값을 기준으로 정렬할 때는
lambda x : 에 기준이 될 키의 위치를 tuple로 감싸서 넣으면 된다.
위 예시의 경우 정수 오름차순, 문자열 오름차순으로 정렬하는 셈이다.
정수는 오름차순, 문자열은 내림차순으로 정렬하고싶다면
sorted(a, key=lambda x: (x[0], -x[1]) )
로 사용하면 된다.
댓글
댓글 쓰기