- 정렬 개념과 목적
- Python 내장 정렬 함수
- key 파라미터 활용
- Dict 정렬
- Lambda와 정렬
- 정렬 알고리즘 종류
- 실전 문제 예시
- 핵심 정리
정렬(Sorting) 이란 사용자가 정의한 특정한 순서로 데이터를 나열하는 과정이다.
| 목적 |
설명 |
| 데이터 검색 최적화 |
정렬된 데이터에서 이진 탐색 가능 (O(log N)) |
| 데이터 분석 |
최댓값, 최솟값, 중앙값 쉽게 파악 |
| 중복 제거 |
연속된 중복 값을 쉽게 식별 |
| 효율적인 알고리즘 |
많은 알고리즘이 정렬된 데이터를 전제 |
정렬 방향
├── 오름차순 (Ascending): 작은 값 → 큰 값
│ 예: [1, 2, 3, 4, 5]
│
└── 내림차순 (Descending): 큰 값 → 작은 값
예: [5, 4, 3, 2, 1]
| 구분 |
안정 정렬 (Stable) |
불안정 정렬 (Unstable) |
| 정의 |
같은 값의 원래 순서 유지 |
같은 값의 순서가 바뀔 수 있음 |
| 예시 |
병합 정렬, 삽입 정렬 |
퀵 정렬, 힙 정렬 |
| Python |
sort(), sorted()는 안정 정렬 |
- |
# 안정 정렬 예시
data = [('A', 2), ('B', 1), ('C', 2)]
# 두 번째 요소로 정렬 시 같은 값(2)의 순서 유지
# 결과: [('B', 1), ('A', 2), ('C', 2)] # A가 C보다 먼저
| 구분 |
sort() |
sorted() |
| 호출 방식 |
리스트.sort() |
sorted(iterable) |
| 반환값 |
None (원본 변경) |
새로운 정렬된 리스트 |
| 원본 데이터 |
변경됨 |
유지됨 |
| 적용 대상 |
리스트만 |
모든 iterable |
| 메모리 |
추가 메모리 불필요 |
새 리스트 생성 |
# 기본 사용법 (원본 변경)
data = [5, 3, 8, 1, 2]
data.sort() # 오름차순 정렬
print(data) # [1, 2, 3, 5, 8]
# 내림차순 정렬
data = [5, 3, 8, 1, 2]
data.sort(reverse=True)
print(data) # [8, 5, 3, 2, 1]
# 반환값 확인
result = data.sort()
print(result) # None (반환값 없음!)
# 기본 사용법 (원본 유지)
data = [5, 3, 8, 1, 2]
sorted_data = sorted(data)
print(sorted_data) # [1, 2, 3, 5, 8]
print(data) # [5, 3, 8, 1, 2] (원본 유지!)
# 내림차순 정렬
sorted_data = sorted(data, reverse=True)
print(sorted_data) # [8, 5, 3, 2, 1]
# 다양한 iterable에 적용
# 튜플
sorted(('c', 'a', 'b')) # ['a', 'b', 'c'] (리스트 반환)
# 문자열
sorted("python") # ['h', 'n', 'o', 'p', 't', 'y']
# 딕셔너리 (키 정렬)
sorted({'b': 2, 'a': 1, 'c': 3}) # ['a', 'b', 'c']
# 집합
sorted({3, 1, 2}) # [1, 2, 3]# sort() 사용: 원본을 직접 정렬하고 싶을 때
numbers = [3, 1, 2]
numbers.sort() # 원본 변경
# sorted() 사용: 원본을 유지하고 싶을 때
original = [3, 1, 2]
sorted_nums = sorted(original) # 원본 유지
# sorted() 사용: 리스트가 아닌 iterable 정렬
text = "hello"
sorted_text = ''.join(sorted(text)) # "ehllo"
key 파라미터는 정렬 기준을 지정하는 함수를 받는다.
# 구문
list.sort(key=함수)
sorted(iterable, key=함수)
# 문자열 길이로 정렬
words = ['banana', 'pie', 'apple', 'fig']
words.sort(key=len)
print(words) # ['pie', 'fig', 'apple', 'banana']
# 절댓값으로 정렬
numbers = [-5, -1, 3, -2, 4]
sorted_nums = sorted(numbers, key=abs)
print(sorted_nums) # [-1, -2, 3, 4, -5]
# 소문자로 변환하여 정렬 (대소문자 무시)
words = ['Banana', 'apple', 'Cherry']
sorted_words = sorted(words, key=str.lower)
print(sorted_words) # ['apple', 'Banana', 'Cherry']
# 2차원 리스트 정렬
students = [
['홍길동', 90],
['김철수', 85],
['이영희', 95]
]
# 점수(인덱스 1)로 정렬
students.sort(key=lambda x: x[1])
print(students)
# [['김철수', 85], ['홍길동', 90], ['이영희', 95]]
# 점수로 내림차순 정렬
students.sort(key=lambda x: x[1], reverse=True)
print(students)
# [['이영희', 95], ['홍길동', 90], ['김철수', 85]]
# 튜플 리스트 정렬
data = [(1, 'b'), (2, 'a'), (1, 'a')]
# 첫 번째 요소로 정렬
sorted(data, key=lambda x: x[0])
# [(1, 'b'), (1, 'a'), (2, 'a')]
# 두 번째 요소로 정렬
sorted(data, key=lambda x: x[1])
# [(2, 'a'), (1, 'a'), (1, 'b')]# 여러 기준으로 정렬 (튜플 반환)
students = [
('홍길동', 3, 90),
('김철수', 2, 85),
('이영희', 3, 95),
('박지민', 2, 90)
]
# 1순위: 학년(오름차순), 2순위: 점수(내림차순)
students.sort(key=lambda x: (x[1], -x[2]))
print(students)
# [('박지민', 2, 90), ('김철수', 2, 85), ('이영희', 3, 95), ('홍길동', 3, 90)]
# 1순위: 점수(내림차순), 2순위: 이름(오름차순)
students.sort(key=lambda x: (-x[2], x[0]))
print(students)
# [('이영희', 3, 95), ('박지민', 2, 90), ('홍길동', 3, 90), ('김철수', 2, 85)]from operator import itemgetter, attrgetter
# itemgetter: 인덱스로 접근
data = [('a', 3), ('b', 1), ('c', 2)]
sorted(data, key=itemgetter(1)) # [('b', 1), ('c', 2), ('a', 3)]
# 다중 키 정렬
data = [('a', 3, 2), ('b', 1, 3), ('a', 2, 1)]
sorted(data, key=itemgetter(0, 1)) # 첫 번째, 두 번째 요소 순으로 정렬
# attrgetter: 객체 속성으로 접근
class Student:
def __init__(self, name, grade):
self.name = name
self.grade = grade
students = [Student('Kim', 3), Student('Lee', 1), Student('Park', 2)]
sorted(students, key=attrgetter('grade'))
# 딕셔너리
data = {'c': 3, 'a': 1, 'b': 2}
# 키로 정렬
sorted(data) # ['a', 'b', 'c'] (키만 반환)
# 키로 정렬된 딕셔너리 생성
dict(sorted(data.items())) # {'a': 1, 'b': 2, 'c': 3}data = {'banana': 3, 'apple': 1, 'cherry': 2}
# 방법 1: sorted + dict
sorted_by_key = dict(sorted(data.items()))
print(sorted_by_key) # {'apple': 1, 'banana': 3, 'cherry': 2}
# 방법 2: items()를 리스트로 변환 후 정렬
items = list(data.items())
items.sort(key=lambda x: x[0]) # 키로 정렬
print(items) # [('apple', 1), ('banana', 3), ('cherry', 2)]data = {'banana': 3, 'apple': 1, 'cherry': 2}
# 값으로 오름차순 정렬
sorted_by_value = dict(sorted(data.items(), key=lambda x: x[1]))
print(sorted_by_value) # {'apple': 1, 'cherry': 2, 'banana': 3}
# 값으로 내림차순 정렬
sorted_by_value_desc = dict(sorted(data.items(), key=lambda x: x[1], reverse=True))
print(sorted_by_value_desc) # {'banana': 3, 'cherry': 2, 'apple': 1}
# operator.itemgetter 사용
from operator import itemgetter
sorted_by_value = dict(sorted(data.items(), key=itemgetter(1)))# 패턴 1: 빈도수 세기 후 정렬
from collections import Counter
words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
counter = Counter(words)
# Counter({'apple': 3, 'banana': 2, 'cherry': 1})
# 빈도수 내림차순 정렬
most_common = counter.most_common()
# [('apple', 3), ('banana', 2), ('cherry', 1)]
# 패턴 2: 딕셔너리 값의 합/평균으로 정렬
scores = {
'Kim': [90, 85, 88],
'Lee': [75, 80, 82],
'Park': [95, 92, 90]
}
# 평균 점수로 정렬
sorted_by_avg = sorted(scores.items(), key=lambda x: sum(x[1])/len(x[1]), reverse=True)
# [('Park', [95, 92, 90]), ('Kim', [90, 85, 88]), ('Lee', [75, 80, 82])]
# 패턴 3: 중첩 딕셔너리 정렬
students = {
'Kim': {'grade': 3, 'score': 90},
'Lee': {'grade': 2, 'score': 85},
'Park': {'grade': 3, 'score': 95}
}
# score로 정렬
sorted_students = dict(sorted(students.items(), key=lambda x: x[1]['score'], reverse=True))
# lambda 구문
# lambda 매개변수: 반환식
# 일반 함수
def square(x):
return x ** 2
# lambda 함수
square_lambda = lambda x: x ** 2
# 바로 사용
(lambda x: x ** 2)(5) # 25# 예제 1: 절댓값으로 정렬
numbers = [-5, -2, 1, 3, -4]
sorted(numbers, key=lambda x: abs(x))
# [1, -2, 3, -4, -5]
# 예제 2: 문자열 특정 위치로 정렬
words = ['abc', 'bac', 'cab', 'acb']
sorted(words, key=lambda x: x[1]) # 두 번째 문자로 정렬
# ['cab', 'bac', 'acb', 'abc']
# 예제 3: 복잡한 조건
data = [(1, 'b', 3), (2, 'a', 1), (1, 'a', 2)]
# 첫 번째 오름차순, 두 번째 오름차순
sorted(data, key=lambda x: (x[0], x[1]))
# [(1, 'a', 2), (1, 'b', 3), (2, 'a', 1)]
# 첫 번째 오름차순, 세 번째 내림차순
sorted(data, key=lambda x: (x[0], -x[2]))
# [(1, 'b', 3), (1, 'a', 2), (2, 'a', 1)]
# 짝수를 먼저, 그 다음 홀수 (각각 오름차순)
numbers = [5, 2, 8, 1, 9, 4, 7, 6, 3]
# 방법 1: 튜플 키
sorted(numbers, key=lambda x: (x % 2, x))
# [2, 4, 6, 8, 1, 3, 5, 7, 9]
# x % 2: 짝수=0, 홀수=1 → 짝수가 먼저
# x: 같은 그룹 내에서 오름차순
# 방법 2: 양수를 먼저, 음수를 나중에
numbers = [3, -1, 2, -5, 4, -3]
sorted(numbers, key=lambda x: (x < 0, abs(x)))
# [2, 3, 4, -1, -3, -5]
# 숫자가 포함된 문자열 자연스럽게 정렬
files = ['file10.txt', 'file2.txt', 'file1.txt', 'file20.txt']
# 기본 정렬 (사전순)
sorted(files)
# ['file1.txt', 'file10.txt', 'file2.txt', 'file20.txt']
# 자연스러운 정렬 (숫자 추출)
import re
sorted(files, key=lambda x: int(re.search(r'\d+', x).group()))
# ['file1.txt', 'file2.txt', 'file10.txt', 'file20.txt']
# 문자열 내 숫자 기준 정렬
strings = ['apple3', 'banana1', 'cherry2']
sorted(strings, key=lambda x: int(x[-1]))
# ['banana1', 'cherry2', 'apple3']
| 알고리즘 |
최선 |
평균 |
최악 |
공간 |
안정성 |
| 버블 정렬 |
O(N) |
O(N^2) |
O(N^2) |
O(1) |
안정 |
| 선택 정렬 |
O(N^2) |
O(N^2) |
O(N^2) |
O(1) |
불안정 |
| 삽입 정렬 |
O(N) |
O(N^2) |
O(N^2) |
O(1) |
안정 |
| 병합 정렬 |
O(NlogN) |
O(NlogN) |
O(NlogN) |
O(N) |
안정 |
| 퀵 정렬 |
O(NlogN) |
O(NlogN) |
O(N^2) |
O(logN) |
불안정 |
| 힙 정렬 |
O(NlogN) |
O(NlogN) |
O(NlogN) |
O(1) |
불안정 |
| 팀 정렬 |
O(N) |
O(NlogN) |
O(NlogN) |
O(N) |
안정 |
팀 정렬(Timsort): Python의 기본 정렬 알고리즘 (병합 + 삽입 정렬 하이브리드)
def bubble_sort(arr):
"""
인접한 두 원소를 비교하여 교환
시간: O(N^2), 공간: O(1)
"""
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
# 교환이 없으면 이미 정렬됨
if not swapped:
break
return arr
# 테스트
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# [11, 12, 22, 25, 34, 64, 90]def selection_sort(arr):
"""
최솟값을 찾아 맨 앞으로 이동
시간: O(N^2), 공간: O(1)
"""
n = len(arr)
for i in range(n - 1):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 테스트
print(selection_sort([64, 25, 12, 22, 11]))
# [11, 12, 22, 25, 64]def insertion_sort(arr):
"""
정렬된 부분에 새 원소를 적절한 위치에 삽입
시간: O(N^2), 거의 정렬된 경우 O(N)
"""
n = len(arr)
for i in range(1, n):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 테스트
print(insertion_sort([12, 11, 13, 5, 6]))
# [5, 6, 11, 12, 13]def quick_sort(arr):
"""
피벗을 기준으로 분할하여 정렬
시간: 평균 O(NlogN), 최악 O(N^2)
"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 테스트
print(quick_sort([3, 6, 8, 10, 1, 2, 1]))
# [1, 1, 2, 3, 6, 8, 10]def merge_sort(arr):
"""
분할 후 병합하면서 정렬
시간: O(NlogN), 공간: O(N)
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 테스트
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]데이터 크기가 작은가? (N < 1000)
├── YES → 아무거나 (삽입 정렬 권장)
└── NO
└── 거의 정렬되어 있는가?
├── YES → 삽입 정렬 O(N)
└── NO → 퀵 정렬 또는 내장 sort()
코딩테스트에서는:
→ 무조건 Python 내장 sort() / sorted() 사용!
→ 직접 구현은 면접용 또는 이해용
"""
문제: N개의 수를 내림차순으로 정렬
"""
n = int(input())
numbers = [int(input()) for _ in range(n)]
numbers.sort(reverse=True)
print(' '.join(map(str, numbers)))"""
문제: 학생 이름과 성적이 주어질 때
성적이 낮은 순서대로 이름 출력
"""
n = int(input())
students = []
for _ in range(n):
name, score = input().split()
students.append((name, int(score)))
students.sort(key=lambda x: x[1])
for name, _ in students:
print(name, end=' ')"""
문제: 배열 A, B가 있을 때
최대 K번 A와 B의 원소를 교체하여
A의 합을 최대로 만들기
"""
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort() # A는 오름차순
b.sort(reverse=True) # B는 내림차순
# A의 작은 값과 B의 큰 값을 교체
for i in range(k):
if a[i] < b[i]:
a[i], b[i] = b[i], a[i]
else:
break
print(sum(a))"""
문제: 국어, 영어, 수학 점수로 학생 정렬
조건:
1. 국어 점수 내림차순
2. 국어 같으면 영어 점수 오름차순
3. 국어, 영어 같으면 수학 점수 내림차순
4. 모두 같으면 이름 오름차순
"""
n = int(input())
students = []
for _ in range(n):
data = input().split()
students.append((data[0], int(data[1]), int(data[2]), int(data[3])))
# 다중 조건 정렬
students.sort(key=lambda x: (-x[1], x[2], -x[3], x[0]))
for student in students:
print(student[0])"""
문제: N개의 집 위치가 주어질 때
모든 집까지의 거리 합이 최소가 되는 안테나 위치
(여러 개면 가장 작은 위치)
"""
n = int(input())
houses = list(map(int, input().split()))
houses.sort()
# 중앙값이 거리 합을 최소화
print(houses[(n - 1) // 2])"""
문제: 각 스테이지의 실패율을 구하고
실패율이 높은 스테이지부터 정렬
"""
def solution(N, stages):
# 각 스테이지에 머무는 사람 수
count = [0] * (N + 2)
for stage in stages:
count[stage] += 1
# 실패율 계산
result = []
total = len(stages) # 아직 클리어하지 못한 사람
for i in range(1, N + 1):
if total == 0:
fail_rate = 0
else:
fail_rate = count[i] / total
result.append((i, fail_rate))
total -= count[i]
# 실패율 내림차순, 스테이지 오름차순
result.sort(key=lambda x: (-x[1], x[0]))
return [stage for stage, _ in result]
# 원본 변경 (리스트만)
list.sort()
list.sort(reverse=True)
list.sort(key=func)
# 원본 유지 (모든 iterable)
sorted(iterable)
sorted(iterable, reverse=True)
sorted(iterable, key=func)
# 단일 기준
sorted(data, key=len) # 길이
sorted(data, key=abs) # 절댓값
sorted(data, key=str.lower) # 소문자 변환
sorted(data, key=lambda x: x[1]) # 특정 인덱스
# 다중 기준 (튜플 반환)
sorted(data, key=lambda x: (x[0], x[1])) # 오름차순, 오름차순
sorted(data, key=lambda x: (-x[0], x[1])) # 내림차순, 오름차순
sorted(data, key=lambda x: (x[0], -x[1])) # 오름차순, 내림차순
d = {'b': 2, 'a': 1, 'c': 3}
# 키로 정렬
dict(sorted(d.items()))
# 값으로 정렬
dict(sorted(d.items(), key=lambda x: x[1]))
# 값으로 내림차순
dict(sorted(d.items(), key=lambda x: x[1], reverse=True))Python 내장 sort(): O(N log N) - 팀 정렬
항상 내장 함수 사용!
| 상황 |
해결 방법 |
| 단순 정렬 |
sort() 또는 sorted() |
| 특정 기준 정렬 |
key 파라미터 + lambda |
| 다중 조건 정렬 |
튜플 반환 lambda |
| 내림차순 숫자 |
-x (음수 변환) |
| 내림차순 문자열 |
reverse=True 별도 사용 |
- Python의
sort()와 sorted()는 팀 정렬(Timsort) 사용
- 팀 정렬은 안정 정렬이므로 같은 값의 순서가 유지됨
- 코딩테스트에서는 직접 정렬 구현보다 내장 함수 활용 권장
- 정렬 후 이진 탐색을 함께 사용하는 문제 빈출