정렬과 기준 선택
점수는 낮은 순서로, 파일은 수정한 날짜순으로 정리할 수 있습니다. 이것이 정렬입니다. 먼저 무엇을 기준으로 비교할지 정해야 합니다. 점수가 같을 때 원래 순서를 유지할지도 결정해야 합니다.
삽입 정렬 따라가기
손에 든 카드를 정리하듯, 왼쪽의 정렬된 부분에 다음 항목을 끼워 넣습니다.
시작 [7, 3, 5, 2]
3 삽입 [3, 7, 5, 2]
5 삽입 [3, 5, 7, 2]
2 삽입 [2, 3, 5, 7]
def insertion_sort(values):
for i in range(1, len(values)):
value = values[i]
j = i - 1
while j >= 0 and values[j] > value:
values[j + 1] = values[j]
j -= 1
values[j + 1] = value
numbers = [7, 3, 5, 2]
insertion_sort(numbers)
print(numbers)
출력은 [2, 3, 5, 7]입니다. 반복을 시작할 때 i의 왼쪽은 이미 정렬되어 있습니다. 다음 값을 넣어도 그 규칙이 유지되므로 마지막에는 전체가 정렬됩니다.
방법마다 다른 비용
- 선택 정렬: 남은 값 중 최솟값을 골라 앞에 둡니다. 비교는
O(n²)입니다. - 삽입 정렬: 최악에
O(n²)이지만, 이미 정렬된 입력은 위 구현에서O(n)입니다. - 합병 정렬: 나누어 정렬한 뒤 합칩니다. 시간은
O(n log n), 일반적인 배열 구현은O(n)의 추가 공간을 씁니다. - 퀵 정렬: 기준값을 정해 나눈 뒤 각 부분을 정렬합니다. 평균은
O(n log n), 분할이 계속 한쪽으로 치우치면 최악에O(n²)입니다. - 힙 정렬: 힙의 꺼내기 규칙을 이용해
O(n log n)에 정렬합니다.
기수 정렬은 자릿수별로 분류합니다. 비교 정렬과 전제가 달라 자릿수와 사용할 기호의 범위까지 비용에 포함해야 합니다.
같은 값의 순서도 중요합니다
동일한 키를 가진 항목의 원래 순서를 유지하면 안정 정렬입니다. 위 삽입 정렬은 >일 때만 밀어서 같은 값의 순서를 유지합니다. Python의 sorted()와 list.sort()도 안정 정렬을 보장합니다.
확인 문제
위 코드의 >를 >=로 바꾸면 같은 점수를 받은 사람들의 접수 순서가 유지될까요?
해설 보기
보장하지 않습니다. 같은 값도 오른쪽으로 밀면서 나중에 온 항목을 앞에 넣게 됩니다. 숫자만 보면 같아 보여도 사람 이름처럼 함께 붙어 있는 정보의 순서가 바뀝니다.