병합 정렬
- 정렬되지 않은 리스트를 절반으로 잘라 비슷한 두 리스트로 나눈다.
- 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다
- 두 리스트를 다시 하나의 리스트로 합병한다.
- 시간 복잡도는 O(n log n)
출처: [위키피디아]
나의 정의
- 리스트를 0또는 1이 될 때까지 반으로 나누고, 그것들을 두 리스트씩 포인터를 가지고 하나의 리스트로 정렬하는 것
- 즉 재귀적으로 길이가 0또는 1까지 나누고 결국 합치는 것
- 함수는 2개가 필요
if문을 이용한 병합 정렬
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
def split(li):
if len(li) <= 1:
return li
mid_idx = len(li)//2
left_list = split(li[:mid_idx])
right_list = split(li[mid_idx:])
return merge(left_list, right_list)
def merge(left_list, right_list):
total = []
lp = 0
rp = 0
for _ in range(len(left_list) + len(right_list)):
if lp == len(left_list):
total.append(right_list[rp])
rp += 1
elif rp == len(left_list):
total.append(left_list[lp])
lp += 1
elif left_list[lp] > right_list[rp]:
total.append(right_list[rp])
rp += 1
elif left_list[lp] < right_list[rp]:
total.append(left_list[lp])
lp += 1
return total
print(split([3,2,5,4,1,6,9]))
1
[1, 2, 3, 4, 5, 6, 9]
while문을 이용한 병합 정렬
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
31
32
33
34
def merge(left_list, right_list):
merged = list()
left_point, right_point = 0, 0
#왼쪽 오른쪽 둘다 있을 때
while len(left_list) > left_point and len(right_list) > right_point:
if left_list[left_point] < right_list[right_point]:
merged.append(left_list[left_point])
left_point += 1
else:
merged.append(right_list[right_point])
right_point += 1
#왼쪽 데이터만 있을 때 >> 넣기
while len(left_list) > left_point:
merged.append(left_list[left_point])
left_point += 1
#오른쪽 데이터만 남았을 때 >> 넣기
while len(right_list) > right_point:
merged.append(right_list[right_point])
right_point += 1
return merged
def mergesplit(data):
if len(data) <= 1:
return data
mid_point = len(data)//2
left_list = mergesplit(data[:mid_point])
right_list = mergesplit(data[mid_point:])
return merge(left_list,right_list)