Python 기본 정렬과 커스텀 정렬

1. 기본 정렬 (오름차순, 내림차순)
2. 커스텀한 정렬
   • 람다식을 사용한 정렬
   • functools.cmp_to_key를 사용한 정렬
   • comparator 함수를 직접 사용하여 정렬

---

1. 기본 정렬 (오름차순, 내림차순)

단순하게 숫자나 문자열의 대소를 따지는 정렬은 python에서 지원하는 sort(), sorted()를 사용하여 처리할 수 있다. 기본 오름차순으로 정렬된다.

nums = [4, 2, 5, 3, 1]

# num을 정렬한 내용의 새로운 리스트를 생성하려면
sorted_num = sorted(nums)

# num을 정렬된 내용으로 변경하려면
nums.sort()

 

내림차순으로 정렬하려면 reverse 파라미터를 True로 지정한다.

nums = [4, 2, 5, 3, 1]

# num을 정렬한 내용의 새로운 리스트를 생성하려면
sorted_num = sorted(nums, reveres=True)


# num을 정렬된 내용으로 변경하려면
nums.sort(reverse=True)

 

2개 이상의 정보가 묶인 data의 경우 기본 정렬 사용 시 모든 정보들을 고려하여 정렬 되므로 주의한다. 예를 들어 다음과 같이 학생 번호와 점수가 주어지는 경우에 기본 정렬을 수행하면

data = [(3, '영어'), (3, '수학'), (3, '국어'), (2, '영어'), (2, '국어')]
data.sort(reverse=False)
print(data)

data[0]과 data[1]을 모두 고려하여 정렬이 진행된다. data[0]에 대해서만 정렬을 진행하고 data[1]에 대해서는 순서가 유지되도록 정렬하고 싶은 경우에는 아래에 소개된 커스텀 정렬을 사용하도록 하자.

---

2. 커스텀한 정렬

커스텀한 정렬을 위해서는 sort(), sorted()의 key 파라미터의 값에 정렬에 필요한 키를 지정할 수 있다. key에는 가공된 key value를 반환하는 함수 또는 comparator를 지정한다. key 파라미터에 함수를 전달하기 위해 람다식^[각주:1]을 사용하면 된다.

 

comparator^[각주:2]를 전달하려면 functools.cmp_to_key()를 사용한다.

 

혹은 comparator를 직접 사용하여 정렬 알고리즘을 작성할 수도 있다.

 

[람다식을 사용하여 정렬]

# list.sort()는 list 원본을 정렬한다.
# sorted()는 원본 list를 정렬한 결과를 새로운 list로 반환한다.

students = [("John", 70), ("Mike", 60), ("Andrew", 80)]

# 1. 정렬 키 반환 함수를 lambda로 작성하여 정렬하는 방법
students.sort(key=lambda student: student[1])
sorted_students = sorted(students, key=lambda student: student[1])


# 2. 정렬에 사용할 키를 반환하는 함수를 정의하여 정렬하는 방법
def getKey(e):
    return e[1]


students.sort(key=getKey)  # key parameter에 키를 반환하는 함수명을 argument로 대입한다.
sorted_students = sorted(students, key=getKey)

# 3. 내림차순 정렬
# list.sort(), sorted() 모두 기본 정렬 순서는 오름차순 정렬이다.
# 내림차순 정렬을 하기 위해 reverse parameter를 True로 지정한다.
sorted_students = sorted(students, key=lambda students: students[1], reverse=True)

students.sort(key=lambda students: students[1], reverse=True)

key 파라미터를 사용하여 내림차순 정렬도 가능하다. (하지만 reverse가 제공되므로 이렇게 할 이유는 없다.)

lst = [4, 3, 6, 5, 1]
lst.sort(key=lambda x: -x)

 

 

[functools.cmp_to_key()를 사용하여 정렬]

별도의 comparator 함수를 작성해두고 cmp_to_key()를 사용하여 comparator 함수를 key 파라미터에 지정하는 것으로 커스텀 정렬을 할 수 있다.

from functools import cmp_to_key


def comparator_by_name(a, b):
    # 앞의 피연산자가 뒤의 피연산자보다 크면 양의 정수를 반환
    if a[0] > b[0]:
        return 1
    # 앞의 피연산자와 뒤의 피연산자가 같으면 0을 반환
    elif a[0] == b[0]:
        return 0
    # 앞의 피연산자가 뒤의 피연산자보다 작으면 음의 정수를 반환
    else:
        return -1
    
    # 위의 코드를 간략하게 다음과 같이 표현할 수도 있다.
    # return a[0] - a[1]


def comparator_by_grade(a, b):
    if a[1] > b[1]:
        return 1
    elif a[1] == b[1]:
        return 0
    else:
        return -1


# cmp_to_key()를 사용하여 이름 기준으로 오름차순 정렬
students = [("John", 70), ("Mike", 60), ("Andrew", 80)]
sorted_students = sorted(students, key=cmp_to_key(comparator_by_name))
students.sort(key=cmp_to_key(comparator_by_name))

# cmp_to_key()를 사용하여 점수 기준으로 오름차순 정렬
students = [("John", 70), ("Mike", 60), ("Andrew", 80)]
sorted_students = sorted(students, key=cmp_to_key(comparator_by_grade))
students.sort(key=cmp_to_key(comparator_by_grade))

 

 

[직접 정렬 알고리즘을 작성하여 정렬]

직접 정렬 알고리즘을 작성하고 정렬할 데이터 간의 대소 비교에 comparator를 사용하여 정렬 할 수 있다. python의 기본 정렬을 사용할 수 없는 환경일 경우 이 방법을 사용하면 되겠다. (구현의 편의를 위해 삽입 정렬을 사용하였다.)

다만, 시간복잡도 O(n log n)의 merge sort나 quick sort를 사용하더라도 빌트인으로 제공되는 sort(), sorted()보다 성능이 떨어지므로 sort() 또는 sorted()를 사용할 수 있는 환경이라면 사용하도록 하자.

def comparator_by_name(a, b):
    if a[0] > b[0]:
        return 1
    elif a[0] == b[0]:
        return 0
    else:
        return -1


def comparator_by_grade(a, b):
    if a[1] > b[1]:
        return 1
    elif a[1] == b[1]:
        return 0
    else:
        return -1


# 삽입정렬과 comparator를 사용하여 이름 기준으로 정렬
students = [("John", 70), ("Mike", 60), ("Andrew", 80)]
i = 1
while i < len(students):
    j = i
    while j > 0 and comparator_by_name(students[j - 1], students[j]) == 1:
        students[j], students[j - 1] = students[j - 1], students[j]
        j -= 1
    i += 1
print(students)


# 삽입정렬과 comparator를 사용해 점수 기준으로 정렬
students = [("John", 70), ("Mike", 60), ("Andrew", 80)]
i = 1
while i < len(students):
    j = i
    while j > 0 and comparator_by_grade(students[j - 1], students[j]) == 1:
        students[j], students[j - 1] = students[j - 1], students[j]
        j -= 1
    i += 1
print(students)

1.  

   람다식

   lambda [param1, param2 ...]:[식1 if 조건 else 식2]

   람다식을 사용하면 익명의 함수를 인스턴트 하게 생성해준다. lambda 키워드 뒤에 단순히 매개변수를 지정하고 매개변수를 가지고 어떤 연산을 할지 명시해주면 된다. if 조건을 넣어 여러 가지 식 가운데 하나를 선택하게 할 수 있다. if 조건은 생략 가능하다.

   다만 if를 사용하여 람다식이 너무 복잡해진다 싶으면 comparator 함수를 따로 정의하여 사용하는 편이 낫다. [본문으로]

2.  

   comparator

   두 비교 요소 a, b를 받아 기준에 따른 대소 연산 이후 a > b 이면 1을, a == b 이면  0을, a < b 이면 -1을 반환하는 함수이다.

   comparator에 대한 개념과 정렬과의 관계를 알고 싶으면 이 블로그 글을 참고하자. https://st-lab.tistory.com/243 [본문으로]