반응형
250x250
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- union
- 계정계
- 렌탈스튜디오창업
- fastapi
- 컴퓨터공학학사취득
- DB
- 인강빨리듣기
- 코어뱅킹
- 은행IT
- 오라클
- jdk17
- 디렉토리계층구조
- 학점은행제
- 맥북셋팅
- 모놀리식
- 맥북
- 프로그래머스
- 학점은행제무료강의
- jdk
- 코딩테스트
- 개인프로필스튜디오창업
- 맥북환경설정
- it자격증
- Pass By Value
- python
- 채널계
- oracleapex
- Homebrew
- MSA
- SQL
Archives
- Today
- Total
개발머해니
[파이썬] 합병정렬 (2) merge_sort 함수 - 분할정복 ★ 본문
728x90
반응형
실습 설명
Divide and Conquer 방식으로 merge_sort 함수를 써 보세요.
merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴합니다.
실습 결과
def merge_sort(my_list):
# base case
if len(my_list) < 2:
return my_list
# my_list를 반씩 나눈다(divide)
left_half = my_list[:len(my_list)//2] # 왼쪽 반
right_half = my_list[len(my_list)//2:] # 오른쪽 반
# merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
# merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
return merge(merge_sort(left_half), merge_sort(right_half))
# 테스트 코드
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))
[1]
[1]
[1, 2]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 4, 6, 7, 8, 9, 10]
합병정렬 모범답안 : merge함수 + merge_sort함수
def merge(list1, list2):
i = 0
j = 0
# 정렬된 항목들을 담을 리스트
merged_list = []
# list1과 list2를 돌면서 merged_list에 항목 정렬
while i < len(list1) and j < len(list2):
if list1[i] > list2[j]:
merged_list.append(list2[j])
j += 1
else:
merged_list.append(list1[i])
i += 1
# list2에 남은 항목이 있으면 정렬 리스트에 추가
if i == len(list1):
merged_list += list2[j:]
# list1에 남은 항목이 있으면 정렬 리스트에 추가
elif j == len(list2):
merged_list += list1[i:]
return merged_list
def merge_sort(my_list):
# base case
if len(my_list) < 2:
return my_list
# my_list를 반씩 나눈다(divide)
left_half = my_list[:len(my_list)//2] # 왼쪽 반
right_half = my_list[len(my_list)//2:] # 오른쪽 반
# merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
# merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
return merge(merge_sort(left_half), merge_sort(right_half))
# 테스트 코드
print(merge_sort([1, 3, 5, 7, 9, 11, 13, 11]))
print(merge_sort([28, 13, 9, 30, 1, 48, 5, 7, 15]))
print(merge_sort([2, 5, 6, 7, 1, 2, 4, 7, 10, 11, 4, 15, 13, 1, 6, 4]))
728x90
반응형
'알고리즘' 카테고리의 다른 글
[파이썬] 퀵정렬 (2) quicksort 함수 - 분할정복 ★ (0) | 2023.09.17 |
---|---|
[파이썬] 퀵정렬 (1) partition 함수 - 분할정복 ★ (0) | 2023.09.17 |
[파이썬] 합병정렬 (1) merge 함수 - 분할정복 ★ (0) | 2023.09.16 |
[파이썬] 1부터 n까지의 합 - 분할 정복 ★ (0) | 2023.09.16 |
[파이썬] 런던 폭우 - 브루트 포스 (0) | 2023.09.16 |