Python-2751-수 정렬하기2

수 정렬하기2

 

Python의 sort함수를 사용해 문제를 풀고, Quick_sort와 Merge_sort를 추가로 구현해 보았다.
sort함수를 사용했을 때 시간이 가장 빨랐고, Merge_sort가 다음, Quick_sort는 시간초과가 발생했다. 어찌 되었든, 목적은 정렬 알고리즘들을 한 번 구현해보는 것이었다.

Merge sort를 살펴보자.

---

 

Merge sort

Merge sort(합병 정렬)은 분할 정복을 사용해 정렬하는 방식이다.

분할 정복은 어떤 문제를 더 작은 문제들로 나눠서 해결해 나가는 방식이다.
문제를 분할해 작게 만들고, 작은 문제들을 정복한 후에 이들을 조합해서 원래 문제에 대한 결과를 이끌어 낸다.

6 2 4 1 5 3 을 정렬하는 과정을 그림으로 나타내 보았다.

• 분할 - 먼저 6개의 숫자를 2개 이하의 숫자쌍으로 분할한다.

• 정복 - 분할된 숫자쌍들을 정렬한다. 위의 그림에서는 (6,2)가 (2,6)으로 정렬되었다.

• 조합 - 숫자쌍들을 합쳐나간다. 이 과정에서 숫자쌍들은 모두 정렬된 상태로 합병된다.

조합 단계에서 숫자쌍들이 합쳐지며 숫자들이 정렬되게 된다.

 

a = merge_sort(arr[:mid])
b = merge_sort(arr[mid:])
l_a, l_b = len(a), len(b)

save_arr = []
cnt_a,cnt_b=0,0
#merge
#더 작은 원소들 부터 차례차례 save에 넣어준다.
while cnt_a < l_a and cnt_b < l_b:
        if a[cnt_a]>b[cnt_b]:
                save_arr.append(b[cnt_b])
                cnt_b+=1
        else:
                save_arr.append(a[cnt_a])
                cnt_a+=1
#병합하고 아직 a or b에 남아있는 원소들을 추가해준다.
#현재 a,b둘중 적어도 하나의 배열은 비어있는 상태이다.
save_arr += a[cnt_a:]
save_arr += b[cnt_b:]

merge_sort함수의 일부분을 가져왔다.

리스트arr를 mid를 기준으로 두 리스트로 나누고, 이들을 다시 함수의 인자로 넣어 리스트의 원소 갯수가 2 이하가 될 때 까지 나눠준다.
나뉜 리스트들이 다시 조합되어 a와 b에 입력되면 이들을 merge시켜줘야 한다.

배열을 저장할 'save' 리스트를 만들어주고, a와 b를 비교하며 두 리스트의 값들 중 작은 값 먼저 'save'에 추가시킨다. a와 b둘 중 한 리스트의 모든 원소가 save로 옮겨지면, while을 탈출하고 a와 b에 아직 save에 추가되지 못하고 남아있는 원소가 있을 수도 있음으로, 이들을 'save'에 추가시킨다.

위와 같이 합병을 진행할 수도 있고, heapq모듈의 merge를 사용해도 배열 두개를 정렬상태를 유지하며 합칠 수 있다.

list(merge(a,b))

위의 코드로도 a와 b를 병합할 수 있다. 이때 주의할 점은 a, b둘다 정렬되어있는 상태여야 한다는 것이다.

CODE

import sys
read=sys.stdin.readline

def merge_sort(arr):
    if len(arr) == 1:
        return arr

    mid = len(arr)//2
        #mid를 기준으로 두개의 배열로 분할한다.
    a= merge_sort(arr[:mid])
    b= merge_sort(arr[mid:])
    l_a, l_b = len(a), len(b)

    save_arr = []
    cnt_a,cnt_b=0,0
        #merge
        #더 작은 원소들 부터 차례차례 save에 넣어준다.
    while cnt_a < l_a and cnt_b < l_b:
        if a[cnt_a]>b[cnt_b]:
            save_arr.append(b[cnt_b])
            cnt_b+=1
        else:
            save_arr.append(a[cnt_a])
            cnt_a+=1
        #병합하고 아직 a or b에 남아있는 원소들을 추가해준다.
        #현재 a,b둘중 적어도 하나의 배열은 비어있는 상태이다.
    save_arr += a[cnt_a:]
    save_arr += b[cnt_b:]

    return save_arr
num= list(int(read()) for _ in range(int(read())))
for x in merge_sort(num):
    print(x)

틀린 부분이 있을 수 있습니다. 피드백 주시면 고치도록 하겠습니다! 감사합니다.👍

[꼭 다시 풀어보기]