리스트 안에 여러 개의 하위 리스트(서브리스트)가 포함되어 있을 때, 각 하위 리스트의 두 번째 요소를 기준으로 전체 리스트를 정렬해야 하는 경우가 자주 있습니다. 이번 글에서는 가장 기본적인 정렬 알고리즘인 버블 정렬(Bubble Sort)을 활용하여 이 문제를 해결하는 방법을 알아보겠습니다.
예제
다음과 같은 입력 리스트가 주어졌을 때, 각 하위 리스트의 두 번째 요소(숫자)를 기준으로 오름차순 정렬한 결과를 확인할 수 있습니다.
입력
[['CCC', 15], ['AAA', 10], ['RRRR', 2], ['XXXX', 150]]
출력
[['RRRR', 2], ['AAA', 10], ['CCC', 15], ['XXXX', 150]]
알고리즘
버블 정렬은 인접한 두 요소를 반복적으로 비교하고, 순서가 잘못되어 있으면 서로 교환하는 방식으로 동작합니다. 이 문제에 적용한 알고리즘의 단계는 다음과 같습니다.
- 정렬할 리스트가 주어집니다.
- 중첩 반복문(nested loop)을 사용하여 각 하위 리스트의 두 번째 요소에 접근합니다.
- 배열의 모든 요소를 처음부터 끝까지 순회합니다.
- 각 패스(pass)가 끝날 때마다 마지막 i개의 요소는 이미 제자리에 정렬된 상태입니다.
- 배열의 0번째 인덱스부터 n-i-1번째 인덱스까지 순회합니다.
- 현재 요소의 두 번째 값이 다음 요소의 두 번째 값보다 크면 두 요소를 교환(swap)합니다.
예제 코드
아래 코드는 세 번째 변수(tempo)를 사용하여 요소를 교환하는 제자리(in-place) 정렬 방식으로 구현되었습니다.
# Python program to sort the lists using the second element of sublist
# In place way to sort, use of third variable.
def sortlist(A):
l = len(A)
for i in range(0, l):
for j in range(0, l-i-1):
if (A[j][1] > A[j + 1][1]):
tempo = A[j]
A[j] = A[j + 1]
A[j + 1] = tempo
return A
# Driver Code
A = [['AAA', 10], ['CCC', 15], ['RRRR', 2], ['XXXX', 150]]
print(sortlist(A))
실행 결과
코드를 실행하면 두 번째 요소를 기준으로 오름차순 정렬된 리스트가 출력됩니다.
[['RRRR', 2], ['AAA', 10], ['CCC', 15], ['XXXX', 150]]
참고: 더 간단한 방법
실무에서는 버블 정렬 대신 파이썬 내장 함수 sorted()와 람다(lambda) 표현식을 사용하면 한 줄로 같은 결과를 얻을 수 있습니다.
A = [['AAA', 10], ['CCC', 15], ['RRRR', 2], ['XXXX', 150]]
sorted_list = sorted(A, key=lambda x: x[1])
print(sorted_list) # [['RRRR', 2], ['AAA', 10], ['CCC', 15], ['XXXX', 150]]
내장 함수는 시간 복잡도 O(n log n)의 Timsort 알고리즘을 사용하기 때문에, 버블 정렬(O(n²))보다 성능 면에서 훨씬 유리합니다. 다만 학습 목적으로 정렬 원리를 이해하고자 할 때는 버블 정렬 구현이 좋은 연습이 됩니다.