[Python] 파이썬의 sort,sorted에 대해 알아보자(feat.문자열 정렬)

📕 1. 글을 작성하는 이유

  : 코테 준비를 위해 정렬 알고리즘을 풀이하다가 내가 생각한 정렬 방식대로 되지 않아서 알아보다가 정리해야겠다고 결심했음. 또한 빅데이터분석기사를 준비할 때도 파이썬이 주력 언어임에도 불구하고 하고 완벽하게 이해하고 사용하는 느낌이 들지 않아서 이번 기회에 한 번 깊게 파보려고 한다. 

 

 

📕 2. 파이썬에서의 정렬 ( sort와 sorted )

  :  파이썬에서 정렬하는 방법으로는 리스트를 제자리에서(in-place) 수정하는 내장 list.sort() 메서드와 이터러블로부터 새로운 정렬된 리스트를 만드는 sorted() 내장함수 2개가 존재함.

 

sort와 sorted의 차이를 간략하게 설명하자면,

sort는 리스트를 제자리에서 수정함. ( 즉, 원본을 조작하며 'None'을 반환함. ) + 리스트에서만 사용가능함.

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

 

 

반면에, sorted는 기존 리스트를 정렬해 새로운 리스트를 반환함. ( 원본을 그대로 둘 수 있음. )

그리고 sort()와 달리, 리스트뿐만 아니라 모든 iterable을 받아들임.

lst = [3,4,2,1,5]
sorted_lst = sorted(lst)
print(sorted_lst) # [1, 2, 3, 4, 5] 
print(lst) # [3, 4, 2, 1, 5] -> sort()에 비해 원본이 그대로 남아있음.

 

---

 

📕 3. 정렬 순서 정하기

 

sort와 sorted는 기본값이 오름차순 정렬이다. 

만약 내림차순으로 정렬하고 싶다면, reverse=True 옵션을 주면 됨.

lst = [3,4,2,1,5]
sorted_lst = sorted(lst,reverse = True) # 내림차순
print(sorted_lst) # [1, 2, 3, 4, 5]
print(lst) # [3, 4, 2, 1, 5]

 

단순 내림차순, 오름차순이 아닌 기준을 정하여 정렬하고 싶다면 익명함수인 람다함수를 이용하여 가능함.

➡ 여기서 람다 함수란 이름이 없는 함수로, 일반적으로 함수를 한 번만 사용하거나 함수를 인자로 전달해야 하는 경우에         유용하게 사용됨. 보통 'lambda 인자 : 표현식'의 형태로 정의됨.

lst = [['서울',100],['부산',200],['광주',300],['대구',250],['대전',170]]
lst = sorted(lst,key=lambda x:x[1]) # 원소의 두 번째 기준으로 오름차순 정렬.
print(lst) # [['서울', 100], ['대전', 170], ['부산', 200], ['대구', 250], ['광주', 300]]

 

위에서 언급하지 않았지만 sort 또한 람다함수를 이용하여 특정 기준으로 정렬이 가능하며,

'lambda x:-x[1]' 이런 식으로 작성 시에는 내림차순으로 정렬도 가능함.

 

또한, 여러 개의 정렬 조건을 동시에 적용시킬 수도 있음.

lst = [[1,2], [1,3],[0,5],[5,1],[4,3]]
lst = sorted(lst,key=lambda x:(-x[0], x[1])) # 첫 번째 기준은 내림차순, 같은 값일 경우 두 번째 값은 오름차순
print(lst)

 

 

그리고 key 변수를 사용하여 다양한 정렬 기준을 사용 가능함.

 

1. 문자열 길이를 기준으로 정렬

my_list = ['apple', 'banana', 'cherry', 'date']
sorted_list = sorted(my_list, key=len)
print(sorted_list)
# 결과: ['date', 'apple', 'banana', 'cherry']

 

2. 단어의 마지막 글자를 기준으로 정렬

def last_letter(word):
    return word[-1]

my_list = ['apple', 'banana', 'cherry', 'date']
sorted_list = sorted(my_list, key=last_letter)
print(sorted_list)
# 결과: ['banana', 'date', 'apple', 'cherry']

 

3. 대소문자 무시하고 사전순으로 정렬

my_list = ['apple', 'Banana', 'cherry', 'Date']
sorted_list = sorted(my_list, key=lambda x: x.lower())
print(sorted_list)
# 결과: ['apple', 'Banana', 'cherry', 'Date']

 

4. 사용자 정의 클래스 객체를 속성 기준으로 정렬

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

people = [Person('Alice', 30), Person('Bob', 25), Person('Charlie', 35)]
sorted_people = sorted(people, key=lambda x: x.age)
for person in sorted_people:
    print(person.name, person.age)
# 결과:
# Bob 25
# Alice 30
# Charlie 35

---

 

 

📕 4. 문자열 정렬하기

 

정렬 알고리즘 관련 문제를 풀다가 발견한 의문.

lst = ['1','2','22','3','100']
lst.sort()
print(lst)

 

문자열로 이루어진 리스트를 오름차순 정렬했을 때, '1 - 2 - 3 - 22 - 100' 숫자 크기 순서대로 정렬될 것이라 예측하고 풀이했는데, 실제 정렬된 리스트를 출력해 보니 ['1', '100', '2', '22', '3'] 이 나왔다. 

 

의아해서 문자열 정렬에 관해 찾아보니,

파이썬의 문자열 정렬은 유니코드 코드 포인트를 기반으로 이루어진다는 사실을 알게 됐다.

문자열의 비교는 첫 번째 문자부터 순서대로 이루어지며, 첫 번째 문자가 같다면 두 번째 문자를 비교하고, 계속해서 진행됨. 그러므로 숫자의 크기 비교가 아니라 문자열의 사전순 비교로 이해하면 된다.

 

[ 참고 : 각 유니코드 ]

숫자 (0-9):

• 유니코드에서 숫자는 U+0030에서 U+0039까지의 코드 포인트를 가짐.

대문자 알파벳 (A-Z):

• 대문자 알파벳은 U+0041에서 U+ 005A까지의 코드 포인트를 가짐.

소문자 알파벳 (a-z):

• 소문자 알파벳은 U+0061에서 U+007 A까지의 코드 포인트를 가짐.
  16진수이기 때문에 1~F로 표현됨.

결론 : 숫자 < 대문자 < 소문자이므로 오름차순으로 정렬하는 경우에는 대문자가 소문자보다 앞에 정렬됨.

 

---

 

 

📕 5. 파이썬의 sort와 sorted 뜯어보기

• 파이썬의 'sort' 메서드는 Tim sort라는 알고리즘을 기반으로 정렬을 수행함.
• Tim sort는 Merge Sort(합병 정렬)과 Insertion Sort(삽입 정렬)를 결합한 하이브리드 알고리즘.
• Tim sort는 Run이라는 단위로 배열을 분할하고 이 분할된 단위에 대해 삽입 정렬을 수행한 뒤, 이를 합병 정렬을 통해 합친 뒤 정렬을 수행함.
• Tim sort에서 사용하는 삽입 정렬은 Binary Insertion sort. 삽입해야 할 위치를 찾을 때까지 비교하는 것이 아닌, 앞의 원소들은 모두 정렬되어 있음을 전제로 이분 탐색을 진행하며 위치를 찾음.
• 작은 크기의 부분 리스트에 대해 삽입 정렬을 사용하고, 그다음 이러한 작은 부분 리스트를 합치기 위해 합병 정렬을 사용함. 삽입 정렬은 작은 크기의 리스트에 효과적이고, 합병 정렬은 큰 리스트를 효과적으로 정렬하기 때문에 이 둘을 하이브리드.
• Timsort는 최악의 경우에도 O(n log n)의 시간 복잡도를 가지며, 이미 정렬된 데이터나 부분 정렬 데이터에 대해서는 높은 효율성을 보임. ( 최선의 경우 O(n), 평균은 O(n log n) )
• 안정적인 두 정렬을 결합했기에 안정적이며, 추가 메모리를 사용하긴 하지만 기존의 Merge sort에 비해 적은 추가 메모리 사용.

 

📕 6. 글을 마치며

프로그래밍을 공부하며 가장 먼저 배운 언어가 파이썬이었기에 'sort' 나 'sorted'에 대해 깊게 생각하지 않고 sum(), min() 등의 내장 함수를 사용하듯 가볍게 사용했었는데 이번 기회에 sort 메서드가 어떤 방식으로 동작하는지 깊게 이해할 수 있었다. 추후에 기억 속에서 희미한 삽입, 병합 등 다양한 정렬들에 대해 한 번 짚고 넘어가야겠다.