[Python] Sort 뽀개기

Python sort문서 (파이썬 3.8버전) 를 보면서 Sort를 살펴보겠습니다. 

 

[1] list.sort()  vs sorted() 

 

우선 파이썬 리스트는 두가지의 built-in function이 있는데

list.sort() 와 sorted() 입니다. 

 

 

1) list.sort() 

 

오직 list에서만 사용할 수 있는 function.

 

list를 제자리(in-place)에서 sort 합니다.

즉 original list를 수정합니다.

 

 

2) sorted()

 

iterable 객체 (list, tuple, 딕셔너리 등등)에 모두 사용할 수 있는 function.

 

list에 sorted를 해주면, 새로운 list를 만들어서 반환해줍니다. 

 

 

=> ' list.sort() 는 sorted() 보다 덜 편하지만, 만약 너가 original list가 필요없다면 list.sort() 가 약간 더 효율적이다'  라고 문서에 적혀있습니다. 

 

 

[2] ascending sort, descending sort

 

1) ascending

 

기본은 ascending sort 입니다. 

 

# list.sort

some_list = [5, 2, 3, 1, 4]
some_list.sort()
print(some_list)

// 결과
[1, 2, 3, 4, 5]

 

# sorted

some_list = [5, 2, 3, 1, 4]
new_list = sorted(some_list)

print(some_list)
print(new_list)


// 결과
[5, 2, 3, 1, 4]
[1, 2, 3, 4, 5]

 

some_word = 'banna'
print(sorted(some_word))

// 결과
['a', 'a', 'b', 'n', 'n']

 

 

2) descending

 

descending sort를 하고 싶다면 reverse=True 를 해주면 됩니다. 

 

# list.sort

some_list = [5, 2, 3, 1, 4]
some_list.sort(reverse=True)
print(some_list)

// 결과
[5, 4, 3, 2, 1]

 

# sorted

some_list = [5, 2, 3, 1, 4]
new_list = sorted(some_list, reverse=True)
print(new_list)

// 결과
[5, 4, 3, 2, 1]

 

some_word = 'banna'
print(sorted(some_word, reverse=True))

// 결과
['n', 'n', 'b', 'a', 'a']

 

[3] Key functions 

 

list.sort() 와 sorted() 는 모두 key parameter를 가집니다. 

key parameter에는 'single argument를 받으며 sort 목적으로 사용할 key를 반환해주는 function'을 넘겨주면 됩니다. 

 

예를 들어 아래와 같은 tuple list가 있는데 age를 기준으로 ascending sort하고 싶다!! 라고 할 때

key로  age값을 리턴해주는 function을 넘겨주면 됩니다. 

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]

def key_func(student):
    return student[2]

sorted_tuples = sorted(student_tuples, key=key_func)
print(sorted_tuples)


// 결과
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

 

따로 function을 정의하지 않고 람다 표현식을 사용하면 더 간단해집니다.

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]

sorted_tuples = sorted(student_tuples, key=lambda student: student[2])
print(sorted_tuples)


// 결과
[('dave', 'B', 10), ('jane', 'B', 12), ('john', 'A', 15)]

 

만약 age를 기준으로 descending sort하고 싶다!! 하면 reverse=True를 추가해주면 되겠습니다. 

student_tuples = [
    ('john', 'A', 15),
    ('jane', 'B', 12),
    ('dave', 'B', 10),
]

sorted_tuples = sorted(student_tuples, key=lambda student: student[2], reverse=True)
print(sorted_tuples)


// 결과 
[('john', 'A', 15), ('jane', 'B', 12), ('dave', 'B', 10)]

 

[3.1] Key functions > 후순위 key를 넘겨주기 

 

 

이런 학생 데이터가 있을 때

위처럼 age를 기준으로 asceding sort해주는 코드입니다. 

class Student:
    def __init__(self, name, grade, age):
        self.name = name
        self.grade = grade
        self.age = age

    def __repr__(self):
        return repr((self.name, self.grade, self.age))

student_objects = [
    Student('john', 'A', 10),
    Student('jane', 'B', 10),
    Student('dave', 'A', 10),
    Student('auggie','A', 12),
]

sorted_objects = sorted(student_objects, key=lambda student: student.age)
print(sorted_objects)


// 결과
[('john', 'A', 10), ('jane', 'B', 10), ('dave', 'A', 10), ('auggie', 'A', 12)]

 

만약 1순위 age, 2순위 grade 로  ascending sort하고 싶다면...?

(즉 age를 기준으로 ascending sort 하되, 만약 age가 같다면 grade를 기준으로 ascending sort하고 싶다!!)

 

 

이럴 때는 후순위 key로 grade를 넘겨주면 됩니다. 

sorted_objects = sorted(student_objects, key=lambda student: (student.age, student.grade))
print(sorted_objects)

// 결과
[('john', 'A', 10), ('dave', 'A', 10), ('jane', 'B', 10), ('auggie', 'A', 12)]

 

 

[3.2] Key functions > convenience functions 

 

 key-function patterns은 파이썬에서 매우 흔한 것이므로 파이썬은 convienience functions를 제공합니다. 

 operator module에 있는  itemgetter(), attrgetter(),  methodcaller() function 입니다. 

 

 

예를 들어 바로 위의 예제를 attrgetter로 더 간단하게 표현할 수 있습니다.  (1순위  age,  2순위 grade로 ascending sort)

from operator import attrgetter

student_objects = [
    Student('john', 'A', 10),
    Student('jane', 'B', 10),
    Student('dave', 'A', 10),
    Student('auggie','A', 12),
]

sorted_objects = sorted(student_objects, key=attrgetter('age', 'grade'))
print(sorted_objects)


// 결과
[('john', 'A', 10), ('dave', 'A', 10), ('jane', 'B', 10), ('auggie', 'A', 12)]

 

itemgetter도 attrgetter랑 동일한 방식으로 쓰면 됩니다. 

from operator import itemgetter

data = [('red', 1), ('blue', 1), ('red', 2), ('blue', 2)]
print(sorted(data, key=itemgetter(0)))

// 결과 
[('blue', 1), ('blue', 2), ('red', 1), ('red', 2)]

 

methodcaller는 문서에 따로 예제가 없네요,, 

 

 

[3.3] Key functions > Built-in functions

 

그리고 key로 파이썬의 built-in function을 물론 넘겨줄 수 있습니다. 

('single argument를 받으며 sort 목적으로 사용할 key를 반환해주는 function' 이라는 조건을 만족시키는 function이라면)

 

 

예를 들어 key로 len함수를 넘겨주면 

letters = ["aaa", "bb", "c"]
print(sorted(letters, key=len))

// 결과 
['c', 'bb', 'aaa']

 

이렇게 len function은 각 str의 length를 리턴해주고 이 length가 sort key가 되어서 위와 같은 결과가 나오게 됩니다. 

https://www.freecodecamp.org/news/the-python-sort-list-array-method-ascending-and-descending-explained-with-examples/

 

 

 

대, 소문자를 구분하지 않고 정렬하기 위해 

str.lower 함수를 key로 전달할 수도 있습니다. 

str의 소문자(lowercase) 버전을 sort 하는데 key로 사용하기 때문에 

대, 소문자 구분이 안된 채로 알파벳 순으로만 정렬된 것을 볼 수 있습니다.

 

names = ["Emma", "emily", "Amy", "Jason"]
print(sorted(names))
print(sorted(names, key=str.lower))


// 결과
['Amy', 'Emma', 'Jason', 'emily']
['Amy', 'emily', 'Emma', 'Jason']

 

 

[4] Tim Sort

 

파이썬의 sorted는 어떤 sort 알고리즘을 사용할까요?

2002년에 팀 피터스가 구현한 팀 소트를 사용합니다 (창안자의 이름을 따서 팀 소트라고 한다고 합니다.)

팀소트는 '실제 데이터는 대부분 이미 정렬되어있을 것이다' 라고 가정하고 (실제로는 데이터가 엉망으로 뒤죽박죽 섞여있는 일은 거의 일어나지 않을 것..!) 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘 입니다.

insertion sort 와 merge sort를 적절히 조합해서 사용하는 하이브리드 정렬 알고리즘입니다. 

 

퀵 정렬은 빠른 알고리즘이지만 최악의 경우 O(n**2)이 될 수 있고 

병합 정렬은 항상 일정한 속도를 보이지만 O(nlogn) 이상 빠르게 처리할 수는 없습니다.

하지만 Tim Sort는 이미 정렬되어있는 경우 비교를 건너뛰기 때문에 O(n)까지 가능하다고 합니다. 

 

 

실용적인 고성능으로 주목을 받은 팀소트는 다른 쪽 진영에도 영향을 끼쳐서

 java, android, swift 에서 공식 정렬 알고리즘으로 사용되게 됩니다. 

(Swift는 Swift5 이전에는 intro sort, Swift5부터는 tim sort를 사용했다고 하네요
참고: https://swiftrocks.com/introsort-timsort-swifts-sorting-algorithm.html )

 

 

 

위의 내용은 파이썬 알고리즘 인터뷰 책을 참고했으며

팀소트 관련 더 보면 좋을 블로그 첨부합니다. 

https://d2.naver.com/helloworld/0315536

https://ssungkang.tistory.com/entry/python-파이썬의-정렬-Tim-Sort