Python 329제] 병합 정렬(Merge Sort)

출처 : 반크_독도2023

 

문제]

아래의 조건에 맞는 프로그램을 작성하시오.

조건]
1. 임의의 3자리수 N개를 무작위로 산출하시오.(3<=N<=100)
2. 임의의 수는 중복되지 않게 산출하시오.
3. 병합정렬을 사용하여 오름차순으로 정렬하시오.
4. 정렬 전 값과 정렬 후 값을 출력하시오.
5. 한라인에 10개씩 출력하시오.
6. 기타사항은 프로그램의 전반적인 로직과 사용 프로그램의 특성을 고려하여
    프로그램을 작성하시오.

입력 예)
3

출력 예)
병합 정렬 전]
111 555 333

병합 정렬 후]
111 333 555

 

참고풀이]

import random

#리스트에 있는 데이터를 오름차순 정렬합니다.
def MergeSort(list):
    if len(list)>1:
        mid=len(list)//2
        left=list[:mid]
        right=list[mid:]

        #나뉜 부분의 크기가 1이될 때까지 재귀호출로 반복한다.
        MergeSort(left)
        MergeSort(right)

        #병합 처리하기
        a=b=c=0
        while a<len(left) and b<len(right):
            if left[a]<right[b]:
                list[c]=left[a]
                a+=1
            else:
                list[c]=right[b]
                b+=1
            c+=1

        while a<len(left):
            list[c]=left[a]
            a+=1
            c+=1

        while b<len(right):
            list[c]=right[b]
            b+=1
            c+=1

        return list

#100~999 사이의 임의의 수 N개를 입력받는다.
data = []

N=int(input())
if 3<=N<=100:
    for i in range(20):
        n=random.randint(100,999)
        if n not in data:
            data.append(n)

    print("병합 정렬 전]")
    for i in range(20):
        if(i+1)%10 != 0:
            print(data[i],end=" ")
        else:
            print(data[i])
    print()

    MergeSort(data)

    print("병합 정렬 후]")
    for i in range(20):
        if(i+1)%10 != 0:
            print(data[i],end=" ")
        else:
            print(data[i])
    print()
     

 

참고풀이 결과]

 

 

 

 

 

대한민국의 아름다운 영토, 독도의 봄